本题查询区间最多1000个,可离散化(2000坐标排序后,任两个坐标之间的区间可看做一个点处理)
再次阐述线段树的惰性标记,每个区间下只可以存一个惰性标记;下推就要解决矛盾;
本题用1,0分别代表将区间全部该变为1或0; 2代表将区间所有的1改为0,所有0改为1;
如图所示,当一个1,0,下推时,可直接下推; 而2不可,因为他需要依赖该区间的原来的正确状态;需特殊考虑(如,2去直接覆盖1,当2再往下推就不会正确(应先下推1))
本解为暴力解,并未离散化;
#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long LL; #define lson (rt<<1),l,m #define rson (rt<<1|1),m+1,r const int maxn = 1024100; int sum[maxn<<2],col[maxn<<2],st[maxn+100]; void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void push(int rt,int m){ col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1] = (m - (m >> 1)) * col[rt]; sum[rt<<1|1] = (m >> 1) * col[rt]; col[rt]=-1; } void pushdown(int rt,int m){ if(m==1){ col[rt]=-1; return ; } if(col[rt]!=-1){ if(col[rt]==2){ sum[rt<<1]=(m - (m >> 1)) -sum[rt<<1]; sum[rt<<1|1]=(m >> 1)-sum[rt<<1|1]; if(col[rt<<1]==-1) col[rt<<1]=col[rt]; else if(col[rt<<1]==2) col[rt<<1]=-1; else { push(rt<<1,(m - (m >> 1))); col[rt<<1]=col[rt]; } if(col[rt<<1|1]==-1) col[rt<<1|1]=col[rt]; else if(col[rt<<1|1]==2) col[rt<<1|1]=-1; else { push(rt<<1|1,(m >> 1)); col[rt<<1|1]=col[rt]; } } else { sum[rt<<1] = (m - (m >> 1)) * col[rt]; sum[rt<<1|1] = (m >> 1) * col[rt]; col[rt<<1]=col[rt<<1|1]=col[rt]; } col[rt]=-1; } } void build(int rt,int l,int r){ col[rt]=-1; if(l==r){ sum[rt]=st[l]; return ; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } int ql,qr,order; void update(int rt,int l,int r){ if(ql<=l&&r<=qr){ if(order==2){ sum[rt]=r-l+1-sum[rt]; } else sum[rt]=(r-l+1)*order; if(order==2){ if(col[rt]==-1) col[rt]=order; else if(col[rt]==2) col[rt]=-1; else{ push(rt,r-l+1); col[rt]=order; } } else col[rt]=order; return ; } pushdown(rt,r-l+1); int m=(l+r)>>1; if(ql<=m) update(lson); if(qr> m) update(rson); pushup(rt); } int ans; void query(int rt,int l,int r){ if(ql<=l&&r<=qr){ ans+=sum[rt]; return ; } pushdown(rt,r-l+1); int m=(l+r)>>1; if(ql<=m) query(lson); if(qr> m) query(rson); } int n; char str[maxn]; int main() { int T,kase=1; scanf("%d",&T); while(T--){ n=1; int t,a,b; scanf("%d",&t); while(t--){ scanf("%d",&a); scanf("%s",str); int len=strlen(str); for(int i=0;i<a;i++) for(int j=0;j<len;j++) st[n++]=(str[j]=='1'? 1:0); } printf("Case %d:\n",kase++); n--; build(1,1,n); int Q,ca=1; scanf("%d",&Q); while(Q--){ char cmd[5]; scanf("%s %d %d",cmd,&ql,&qr); ql++; qr++; if(cmd[0]=='S'){ ans=0; query(1,1,n); printf("Q%d: %d\n",ca++,ans); continue; } if(cmd[0]=='F') order=1; if(cmd[0]=='E') order=0; if(cmd[0]=='I') order=2; update(1,1,n); } } return 0; }