线段树查询_g32网纹编程

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

我真服了。。这题我能调一天半，最后还是对拍拍出来的。。。脑子还是有病啊

题解: 首先可以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]

然后考虑用线段树+扫描线优化。差分之后推一波发现只需要支持: 单点加、区间覆盖(为0)、区间求和。

扫描线写得还是不熟。注意如果从右往左扫，同一竖列一定要先加入栅栏再删除栅栏！如数据:

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Õ¤À¸ÓҲ࣬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µÄºÍ { 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\)分，心里最大的一块石头终于落地了……