题解 P3870 【[TJOI2009]开关】
Juan_feng
2018-10-06 15:34:36
### 这道题现在还没有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++!**