题解 P3870 【[TJOI2009]开关】

Juan_feng

2018-10-06 15:34:36

Solution

### 这道题现在还没有C++的分块题解,~~小蒟蒻就来水一发吧qwq~~ 可能是数据比较弱的原因,这题的分块跑的飞快,小蒟蒻目前是这道题的rank1(马上就要被超过去了各位dalao手下留情QAQ) 小蒟蒻就默认看到这里的dalao都会分块了,不会分块的可以去[hzwer大神的数列分块九讲](http://hzwer.com/8053.html)去学习一下qwq,个人感觉讲的可以说是很棒了 **进入正题,把长度为n的数列分成根号n个块,修改的时候对于散块直接暴力修改,整块把tag数组异或一下1就行了(修改次数为偶数则灯的开关情况不变)。** **但只这样的话查询的时候不好查整块,所以还要维护一个ans数组,用于保存块内目前开着的灯的数量。散块修改的时候好维护,至于整块,修改的时候把ans变为 **块的大小减去ans** 就行了。** **这样一来查询的时候也很简单了,散块直接暴力去查,整块的答案就是我们维护的ans qwq** 相信各位dalao看到这里已经了然于胸了,那么代码如下: ``` #include<iostream> #include<cstdio> #include<cmath> #define maxn 100010 #define re register #define FOR(i,l,r) for(re int i=l;i<=r;i++) using namespace std; int a[maxn],b[maxn],tag[maxn],ans[maxn]; int n,m,c,r,t,x,y,z,sq; inline char nc(){ //快的一批的fread快读 static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int _read(){ char ch=nc(); int sum=0; while(!(ch>='0'&&ch<='9'))ch=nc(); while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc(); return sum; } inline void out(re int a){ if(a>=10)out(a/10); putchar(a%10+'0'); } void change(int x,int y){ //修改操作 FOR(i,x,min(y,b[x]*sq)){//散块直接修改 ans[b[x]]-=(a[i]^tag[b[x]]); //维护ans数组 a[i]^=1; ans[b[x]]+=(a[i]^tag[b[x]]); } if(b[x]!=b[y]) FOR(i,(b[y]-1)*sq+1,y){ ans[b[y]]-=(a[i]^tag[b[y]]); a[i]^=1; ans[b[y]]+=(a[i]^tag[b[y]]); } FOR(i,b[x]+1,b[y]-1){ //整块修改tag,维护ans数组 tag[i]^=1; ans[i]=sq-ans[i]; } } int query(int x,int y){ //查询操作 re int res=0; FOR(i,x,min(y,b[x]*sq)) //散块直接查询 res+=(a[i]^tag[b[x]]); if(b[x]!=b[y]) FOR(i,(b[y]-1)*sq+1,y) res+=(a[i]^tag[b[y]]); FOR(i,b[x]+1,b[y]-1) res+=ans[i]; //整块加上维护的ans return res; } int main(){ n=_read(),m=_read(); sq=sqrt(n); //分块大小默认为根号n,修改也许能变得更快 FOR(i,1,n) b[i]=(i-1)/sq+1; //每个点所在的块 FOR(i,1,m){ t=_read(),x=_read(),y=_read(); if(t==0){ change(x,y); } else{ out(query(x,y)); puts(""); } } return 0;//功德圆满。 } ``` **最后祝大家NOIP RP++!**