题解 P2574 【XOR的艺术】
SuperJvRuo
2018-10-04 15:33:11
就这沙雕题还用得上线段树/分块？
我们可以压位处理，将32个二进制位压入一个```unsigned int```中，暴力修改，开启O2即可AC。
```
#include<cstdio>
#include<cctype>
#include<utility>
#define PII pair<int,int>
//以空间换时间，快速统计一个unsigned int中有多少个1
const unsigned char popcount_tab[]=
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
};
//把数分成4段进行统计
int popcount (register unsigned int x)
{
return popcount_tab[(x>>0)&0xff]+popcount_tab[(x>>8)&0xff]+popcount_tab[(x>>16)&0xff]+popcount_tab[(x>>24)&0xff];
}
int Read()
{
int x=0;char c=getchar();
while(!isdigit(c))
{
c=getchar();
}
while(isdigit(c))
{
x=x*10+(c^48);
c=getchar();
}
return x;
}
using std::pair;
unsigned int arr[10005];
//将序列下标转换为压位下标与位置
PII trans(int pos)
{
return PII(pos/32,pos%32);
}
//整个在一个数里的部分xor-1，零散部分挨个处理
void Rev(PII l,PII r)
{
if(l.first==r.first)
for(int i=l.second;i<=r.second;++i)
arr[l.first]^=(1<<i);
else
{
for(int i=l.first+1;i!=r.first;++i)
arr[i]^=-1;
for(int i=l.second;i<32;++i)
arr[l.first]^=(1<<i);
for(int i=0;i<=r.second;++i)
arr[r.first]^=(1<<i);
}
}
//同上
int Query(PII l,PII r)
{
int res=0;
if(l.first==r.first)
for(int i=l.second;i<=r.second;++i)
res+=(arr[l.first]>>i)&1;
else
{
for(int i=l.first+1;i!=r.first;++i)
res+=popcount(arr[i]);
for(int i=l.second;i<32;++i)
res+=(arr[l.first]>>i)&1;
for(int i=0;i<=r.second;++i)
res+=(arr[r.first]>>i)&1;
}
return res;
}
char str[200005];
int main()
{
int n=Read(),m=Read(),opt;
scanf("%s",str+1);
for(int i=1;i<=n;++i)
{
if(str[i]-'0'==1)
{
PII pos=trans(i);
arr[pos.first]+=1<<pos.second;
}
}
while(m--)
{
opt=Read();
PII l=trans(Read());
PII r=trans(Read());
if(opt==0)
{
Rev(l,r);
}
else
{
printf("%d\n",Query(l,r));
}
}
return 0;
}
```