題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=4422

我真服了。。這題我能調(diào)一天半，最后還是對拍拍出來的。。。腦子還是有病啊

題解: 首先可以dp, 分情況討論: 若下面右面都有柵欄則值為零，若僅下面有柵欄則dp值等于右面，若僅右面有柵欄則dp值等于下面，若\((i,j)\)滿足存在一矩形\((i+1,j+1)-(x,y)\)則dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[x+1][y+1]，否則dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]

然后考慮用線段樹+掃描線優(yōu)化。差分之后推一波發(fā)現(xiàn)只需要支持: 單點加、區(qū)間覆蓋(為0)、區(qū)間求和。

掃描線寫得還是不熟。注意如果從右往左掃，同一豎列一定要先加入柵欄再刪除柵欄！如數(shù)據(jù):

5 2 6 6 7 1 9 9 9 8 4 9 5 2 1 3 3 10 2 10 2 10 4 5 10 4 8 10 4 3 1 10 10 3 9 4 8 10 6 6 5 10 1 1 3

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<set> #include<iostream> #include<algorithm> using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 2e5; const int C = 1e6; struct SegmentTree {struct SgTNode{int sum,tag;SgTNode() {sum = 0,tag = -1;}} sgt[(C<<2)+3];void pushdown(int pos,int le,int ri){int mid = (le+ri)>>1;if(sgt[pos].tag>-1){sgt[pos<<1].sum = sgt[pos].tag*(mid-le+1); sgt[pos<<1].tag = sgt[pos].tag;sgt[pos<<1|1].sum = sgt[pos].tag*(ri-mid); sgt[pos<<1|1].tag = sgt[pos].tag;sgt[pos].tag = -1;}}void addval(int pos,int le,int ri,int lrb,int val){if(le==lrb && ri==lrb) {sgt[pos].sum += val; sgt[pos].tag = -1; return;}pushdown(pos,le,ri);int mid = (le+ri)>>1;if(lrb<=mid) addval(pos<<1,le,mid,lrb,val);else addval(pos<<1|1,mid+1,ri,lrb,val);sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;}void modify(int pos,int le,int ri,int lb,int rb,int val){if(le>=lb && ri<=rb) {sgt[pos].sum = (ri-le+1)*val; sgt[pos].tag = val; return;}pushdown(pos,le,ri);int mid = (le+ri)>>1;if(lb<=mid) {modify(pos<<1,le,mid,lb,rb,val);}if(rb>mid) {modify(pos<<1|1,mid+1,ri,lb,rb,val);}sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;}int querysum(int pos,int le,int ri,int lb,int rb){if(le>=lb && ri<=rb) {return sgt[pos].sum;}pushdown(pos,le,ri);int mid = (le+ri)>>1,ret = 0;if(lb<=mid) {ret += querysum(pos<<1,le,mid,lb,rb);}if(rb>mid) {ret += querysum(pos<<1|1,mid+1,ri,lb,rb);}sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;return ret;} } sgt; struct Event {int opt,x,y,xx,yy,ans,id; //1?¤à?×ó2à￡?2?¤à?óò2à￡?3?¨￡?4?￡bool operator <(const Event &arg) const{if(x<arg.x) return true; else if(x>arg.x) return false;if(opt>arg.opt) return true; else if(opt<arg.opt) return false;return y>arg.y;} } qr[(N<<2)+3]; bool cmp_id(Event x,Event y) {return x.id<y.id;} int id[(N<<2)+3]; set<int> s; int n,m,p,q;int getval(int y) //yμ?????μúò????￡à?-1μ?oí {int tmp = *s.upper_bound(y);int ret = sgt.querysum(1,1,C,y,tmp-1);return ret; }int main() {int q = 0;scanf("%d",&p);for(int i=1; i<=p; i++){int lbx,rbx,lby,rby; scanf("%d%d%d%d",&lby,&lbx,&rby,&rbx);q++; qr[q].x = lbx-1; qr[q].y = lby; qr[q].opt = 2; qr[q].id = q;q++; qr[q].x = rbx; qr[q].y = rby; qr[q].opt = 1; qr[q].id = q;}scanf("%d",&m); for(int i=1; i<=m; i++) {int x,y; scanf("%d%d",&y,&x); q++; qr[q].x = x; qr[q].y = y; qr[q].opt = 3; qr[q].id = q;}scanf("%d",&n); for(int i=1; i<=n; i++) {int x,y; scanf("%d%d",&y,&x); q++; qr[q].x = x; qr[q].y = y; qr[q].opt = 4; qr[q].id = q;}sort(qr+1,qr+q+1); int j = q;for(int i=1; i<=q; i++) id[qr[i].id] = i;s.insert(C+1);for(int i=C; i>=1; i--){while(j>0 && qr[j].x==i){if(qr[j].opt==2){int k = id[qr[j].id+1]; int xx = qr[k].x,yy = qr[k].y,x = i,y = qr[j].y;if(y>1){int cur = getval(y-1)-qr[k].ans;sgt.modify(1,1,C,y-1,y-1,cur);}sgt.modify(1,1,C,y,yy,0);s.erase(y); if(yy<C) s.erase(yy+1);}else if(qr[j].opt==1){int k = id[qr[j].id-1]; int x = qr[k].x,y = qr[k].y,xx = i,yy = qr[j].y;if(y>1){int cur = getval(y-1);sgt.modify(1,1,C,y-1,y-1,cur);}if(yy<C) qr[j].ans = getval(yy+1);sgt.modify(1,1,C,y,yy,0);s.insert(y); if(yy<C) s.insert(yy+1);}else if(qr[j].opt==3){sgt.addval(1,1,C,qr[j].y,1);}else if(qr[j].opt==4){qr[j].ans = getval(qr[j].y);}j--;}}sort(qr+1,qr+q+1,cmp_id);for(int i=1; i<=q; i++) {if(qr[i].opt==4) printf("%d\n",qr[i].ans);}return 0; }

中考超QDEZ線\(32\)分，心里最大的一塊石頭終于落地了……

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4422 (线段树、DP、扫描线、差分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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