传送门: 洛谷 P2574 XOR 的艺术 https://www.luogu.org/problemnew/show/P2574
重题: 洛谷 P2846 光开关 https://www.luogu.org/problemnew/show/P2846 , 洛谷 P3870 开关 https://www.luogu.org/problemnew/show/P3870
算法分析: 对懒标记 \(v[k]\) 取 \(xor\), 且 \([l,r]\) 中 1 的个数取反后即是之后数列中 \(0\) 的个数
- ---
- #include<iostream>
- #include<cstdio>
- #define maxN 200010
- #define in(x) x=read()
- #define ls k<<1
- #define rs k<<1 | 1
- #define mid ((l+r)>>1)
- using namespace std;
- typedef long long rd;
- typedef long long ll;
- ll sum[maxN*4+1],v[maxN*4+1];
- int n,m,op,x,y;
- inline rd read();
- void pushdown(int,int,int),pushup(int);
- void build(int,int,int);
- ll query(int,int,int,int,int);
- void update(int,int,int,int,int);
- int main()
- {
- in(n); in(m); build(1,1,n);
- for(int i=1;i<=m;i++)
- {
- in(op); in(x); in(y);
- if(op==0) update(1,1,n,x,y);
- else printf("%lld\n",query(1,1,n,x,y));
- }
- return 0;
- }
- void pushup(int k) {sum[k]=sum[ls]+sum[rs];}
- void pushdown(int k,int l,int r)
- {
- v[ls]^=1; v[rs]^=1;
- sum[ls]=(mid-l+1)-sum[ls];
- sum[rs]=(r-mid)-sum[rs];
- v[k]=0;
- }
- void update(int k,int l,int r,int ql,int qr)
- {
- if(ql<=l && r<=qr)
- {
- sum[k]=(r-l+1)-sum[k];
- v[k]^=1; return;
- }
- if(v[k]) pushdown(k,l,r);
- if(ql<=mid) update(ls,l,mid,ql,qr);
- if(qr>mid) update(rs,mid+1,r,ql,qr);
- pushup(k);
- }
- long long query(int k,int l,int r,int ql,int qr)
- {
- if(ql<=l && r<=qr) return sum[k];
- long long ans=0;
- if(v[k]) pushdown(k,l,r);
- if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
- if(qr>mid) ans+=query(rs,mid+1,r,ql,qr);
- return ans;
- }
- void build(int k,int l,int r)
- {
- if(l==r) {scanf("%1lld",&sum[k]); return;}
- build(ls,l,mid); build(rs,mid+1,r);
- pushup(k);
- }
- inline rd read()
- {
- rd num=0,f=1;
- char ch=getchar();
- while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
- if(ch=='-') {ch=getchar(); f=-1;}
- while(ch>='0' && ch<='9')
- {
- num=num*10+ch-'0';
- ch=getchar();
- }
- return num*f;
- }
来源: http://www.bubuko.com/infodetail-2949110.html