[Codeforces1058E][分治]Vasya and Good Sequences

翻译

给你一些数 你可以把这些数二进制表示中的1任意移动
问有多少个区间满足 你做完上面的操作后他们的异或和为0

题解

显然是给你一些数
你要把每个数分成两半 加入两个集合
要求这两个集合的数值相同
大概就是结论吧…
你会发现
这一段区间满足条件的话
当且仅当区间权值和>=区间MAX*2
然后分治就好了…

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline LL read() {
     LL f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} int n,a[310000]; LL bin[65]; int s[2][250]; int lowbit(int x){
     return x&-x;} void change(int x,int c,int op){
     for(int i=x;i<=200;i+=lowbit(i))s[op][i]+=c;} int findsum(int x,int op){
     int ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=s[op][i];return ret;} LL sol(int l,int r) {
     if(l>=r)return 0;int mid=(l+r)/2;LL ret=0;int mx=0;int u=mid,u1=0,u2=0;for(int i=mid;i>=l;i--){
     mx=max(mx,a[i]);u1+=a[i];while(a[u+1]<=mx&&u<r){
     u2+=a[++u];int po=u2>200?200:u2;if(u2&1)change(po,1,1);else change(po,1,0);}ret+=((u1&1)?findsum(200,1)-findsum(max(2*mx-1-u1,0),1):findsum(200,0)-findsum(max(2*mx-1-u1,0),0));}u=mid+1,u1=u2=mx=0;memset(s,0,sizeof(s));for(int i=mid+1;i<=r;i++){
     mx=max(mx,a[i]);u1+=a[i];while(a[u-1]<mx&&u>l){
     u2+=a[--u];int po=u2>200?200:u2;if(u2&1)change(po,1,1);else change(po,1,0);}ret+=((u1&1)?findsum(200,1)-findsum(max(2*mx-1-u1,0),1):findsum(200,0)-findsum(max(2*mx-1-u1,0),0));}memset(s,0,sizeof(s));return ret+sol(l,mid)+sol(mid+1,r); } int main() {
     bin[0]=1;for(int i=1;i<=62;i++)bin[i]=bin[i-1]<<1LL;n=read();for(int i=1;i<=n;i++){
     LL x=read();for(int j=0;j<=62;j++)if(x&bin[j])a[i]++;}printf("%lld\n",sol(1,n));return 0; }