CF815D?Karen and Cards?

固定一維c，然后(a,b)看成坐標(biāo)，矩形區(qū)域求交

1.Segment tree Beats！

2.改成不合法的區(qū)域就是求并，c反向枚舉，區(qū)域只增不減且完全包含之前的

單調(diào)棧預(yù)處理找到輪廓線，然后兩個指針維護頂頭位置即可

#include<bits/stdc++.h> #define reg register int #define il inline #define int long long #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } namespace Miracle{ const int N=500000+5; int n,A,B,C; ll ans,sum; struct node{int a,b,c; }p[N]; bool cmpa(node a,node b){return a.a<b.a; } bool cmpc(node a,node b){return a.c>b.c; } int sta[N],top; int x[N],y[N]; int main(){rd(n);rd(A);rd(B);rd(C);for(reg i=1;i<=n;++i) rd(p[i].a),rd(p[i].b),rd(p[i].c);sort(p+1,p+n+1,cmpa);for(reg i=1;i<=n;++i){while(top&&p[sta[top]].b<p[i].b) --top;sta[++top]=i;}sum=(ll)A*B;sta[top+1]=0;for(reg i=1;i<=top;++i){//cout<<" ii "<<i<<" "<<p[sta[i]].b<<endl;sum-=(ll)((ll)p[sta[i]].a-p[sta[i-1]].a)*p[sta[i]].b;for(reg j=p[sta[i-1]].a+1;j<=p[sta[i]].a;++j) x[j]=p[sta[i]].b;for(reg j=p[sta[i]].b;j>p[sta[i+1]].b;--j) y[j]=p[sta[i]].a;} // for(reg i=1;i<=A;++i){ // cout<<x[i]<<" "; // }cout<<endl; // for(reg i=1;i<=B;++i){ // cout<<y[i]<<" "; // }cout<<endl; // cout<<" sum "<<sum<<endl;sort(p+1,p+n+1,cmpc);for(reg tx=1,ty=1,j=1,i=C;i>=1;--i){// cout<<" i "<<i<<" tx "<<tx<<" ty "<<ty<<endl;while(j<=n&&p[j].c>=i){// cout<<" p[j] "<<j<<" "<<p[j].c<<endl;for(;tx<=p[j].a;++tx) sum-=B-max(ty-1,x[tx]);// cout<<" sum1 "<<sum<<endl;for(;ty<=p[j].b;++ty) sum-=A-max(tx-1,y[ty]);// cout<<" sum2 "<<sum<<endl;++j;}ans+=sum;}printf("%lld",ans);return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/3/3 15:45:41 */

很套路了

排序，然后偏序想到坐標(biāo)矩形求面積

交和并的轉(zhuǎn)化，容斥。或者大力吉司機線段樹

?

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10483513.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的CF815D Karen and Cards的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。