线段树
/* http://acm.cug.edu.cn/problem.php?cid=1176&pid=1 */ // 区间赋值为0/1,区间的值取反 //线段树动态开点 // 区间翻转0/1+区间赋值0/1+区间求和的双标记动态开点线段树.html #define ml ((l+r)>>1) #define mr (ml+1) const int maxn=5e4+5; int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot; void push_son(int&son,int l,int r,int covrt,int revrt){ if(son==0) { son=++tot; cov[son]=-1; rev[son]=0; sum[son]=0; ls[son]=0; rs[son]=0; } if(covrt!=-1){ sum[son]=(r-l+1)*covrt; cov[son]=covrt; rev[son]=0; } if(revrt!=0){ sum[son]=(r-l+1)-sum[son]; rev[son]^=1; } } void push_down(int rt,int l,int r){ push_son(ls[rt],l,ml,cov[rt],rev[rt]); push_son(rs[rt],mr,r,cov[rt],rev[rt]); cov[rt]=-1; rev[rt]=0; } void push_up(int rt,int l,int r){ sum[rt]=sum[ls[rt]]+sum[rs[rt]]; } void build(int&rt,int l,int r){ rt=tot=0; push_son(rt,l,r,-1,0); } void update(int rt,int l,int r,int ql,int qr,int d,int type){ if(ql<=l&&r<=qr){ if(type==1) push_son(rt,l,r,-1,1);//rev if(type==2) push_son(rt,l,r, d,0);//cover } else{ push_down(rt,l,r); if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type); if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type); push_up(rt,l,r); } } int query(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return sum[rt]; } else{ push_down(rt,l,r); int ret=0; if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr); if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr); return ret; } }
离散化方法线段树
/* 3 6 1 1 1 1 1 4 1 2 2 1 2 4 1 3 3 1 3 4 */ #include<bits/stdc++.h> using namespace std; vector<int>disc; int getid(int x){ return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1; } //hdu 4578 #define ls (rt<<1) #define rs (ls|1) #define ml ((l+r)>>1) #define mr (ml+1) const int maxn=55555*6; int rev[maxn<<2],cov[maxn<<2],sum[maxn<<2],a[maxn]; void push_son(int son,int l,int r,int covrt,int revrt){ if(covrt!=-1){ sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)*covrt; cov[son]=covrt; rev[son]=0; } if(revrt!=0){ sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)-sum[son]; rev[son]^=1; } } void push_down(int rt,int l,int r){ push_son(ls,l,ml,cov[rt],rev[rt]); push_son(rs,mr,r,cov[rt],rev[rt]); cov[rt]=-1; rev[rt]=0; } void push_up(int rt,int l,int r){ sum[rt]=sum[ls]+sum[rs]; } void build(int rt,int l,int r){ cov[rt]=-1; rev[rt]=0; if(l==r){ sum[rt]=0; } else{ build(ls,l,ml); build(rs,mr,r); push_up(rt,l,r); } } void update(int rt,int l,int r,int ql,int qr,int d,int type){ if(l!=r) push_down(rt,l,r); if(ql<=l&&r<=qr){ if(type==1) push_son(rt,l,r,-1,1);//rev if(type==2) push_son(rt,l,r, d,0);//cover } else{ if(ml>=ql) update(ls,l,ml,ql,qr,d,type); if(mr<=qr) update(rs,mr,r,ql,qr,d,type); push_up(rt,l,r); } } int query(int rt,int l,int r,int ql,int qr){ if(l!=r) push_down(rt,l,r); if(ql<=l&&r<=qr){ return sum[rt]; } else{ int ret=0; if(ml>=ql) ret+=query(ls,l,ml,ql,qr); if(mr<=qr) ret+=query(rs,mr,r,ql,qr); return ret; } } int read(){ int ret=0,fu=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') fu=-1; ch=getchar(); } while('0'<=ch&&ch<='9') { ret=(ret<<1)+(ret<<3)+(ch^48); ch=getchar(); } return ret*fu; } int L[maxn],R[maxn],OP[maxn]; int main(){ int n=read(); int q=read(); for(int i=0;i<q;i++) { L[i]=read(); R[i]=read(); OP[i]=read(); disc.push_back(L[i]); disc.push_back(R[i]); disc.push_back(L[i]+1); disc.push_back(R[i]+1); disc.push_back(L[i]-1); disc.push_back(R[i]-1); } sort(disc.begin(),disc.end()); disc.erase(unique(disc.begin(),disc.end()),disc.end()); build(1,1,disc.size()); for(int i=0;i<q;i++){ int l=getid(L[i]); int r=getid(R[i]); int op=OP[i]; if(op==1) update(1,1,disc.size(),l,r,0,2); if(op==2) update(1,1,disc.size(),l,r,1,2); if(op==3) update(1,1,disc.size(),l,r,1,1); if(op==4) printf("%d\n",query(1,1,disc.size(),l,r)); } }