首先可以发现$2^k$模3意义下有循环节，也就是1,-1,1,-1……
考虑对于x个1，y个0，判断是否存在3的倍数
1.x为偶数时一定可以，选择等量的1和-1即可
2.x为奇数，要满足$x\ge 3$且$y\ge 2$，这是可以用3个0*(-1)和3个1*1来抵消掉（如果y=2时也可以，因为此时总共有奇数位），同时$x-3$显然为偶数
看上去难以维护，考虑反过来，求不是3的倍数的区间个数，那么即要求$x=1$或x为奇数且$y=0/1$
线段树维护区间，对于每一个区间维护0的数量，1的数量和一个三维数组a[3][4][3]表示在任意/以左端点为开头/右端点为结尾的区间中，x为0/1/非0偶数/非1奇数，y为0/1/(>1)的数量，转移详见代码（比较丑陋）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 #define ll long long 8 struct ji{ 9 int s[2]; 10 ll a[3][4][3]; 11 }o,f[N<<2]; 12 int n,m,p,x,y,a[N]; 13 int fx(int x){ 14 if (x<2)return x; 15 return ((x&1)+2); 16 } 17 int fy(int y){ 18 return min(y,2); 19 } 20 ji up(ji x,ji y){ 21 if (x.s[0]<0)return y; 22 if (y.s[0]<0)return x; 23 for(int i=0;i<2;i++)o.s[i]=x.s[i]+y.s[i]; 24 memset(o.a[0],0,sizeof(o.a[0])); 25 memcpy(o.a[1],x.a[1],sizeof(o.a[1])); 26 memcpy(o.a[2],y.a[2],sizeof(o.a[2])); 27 for(int i1=0;i1<4;i1++) 28 for(int j1=0;j1<3;j1++){ 29 o.a[0][i1][j1]+=x.a[0][i1][j1]+y.a[0][i1][j1]; 30 o.a[1][fx(i1+x.s[1])][fy(j1+x.s[0])]+=y.a[1][i1][j1]; 31 o.a[2][fx(i1+y.s[1])][fy(j1+y.s[0])]+=x.a[2][i1][j1]; 32 for(int i2=0;i2<4;i2++) 33 for(int j2=0;j2<3;j2++) 34 o.a[0][fx(i1+i2)][fy(j1+j2)]+=x.a[2][i1][j1]*y.a[1][i2][j2]; 35 } 36 return o; 37 } 38 void update(int k,int l,int r,int x,int y){ 39 if (l==r){ 40 f[k].s[y]=1; 41 f[k].s[y^1]=0; 42 memset(f[k].a,0,sizeof(f[k].a)); 43 for(int i=0;i<3;i++)f[k].a[i][y][y^1]=1; 44 return; 45 } 46 if (x<=mid)update(L,l,mid,x,y); 47 else update(R,mid+1,r,x,y); 48 f[k]=up(f[L],f[R]); 49 } 50 ji query(int k,int l,int r,int x,int y){ 51 if ((l>y)||(x>r))return f[0]; 52 if ((x<=l)&&(r<=y))return f[k]; 53 return up(query(L,l,mid,x,y),query(R,mid+1,r,x,y)); 54 } 55 int main(){ 56 scanf("%d",&n); 57 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 58 for(int i=1;i<=n;i++)update(1,1,n,i,a[i]); 59 f[0].s[0]=-1; 60 scanf("%d",&m); 61 for(int i=1;i<=m;i++){ 62 scanf("%d%d",&p,&x); 63 if (p==1)update(1,1,n,x,a[x]^=1); 64 else{ 65 scanf("%d",&y); 66 ll ans=(y-x+2LL)*(y-x+1)/2; 67 o=query(1,1,n,x,y); 68 for(int j=0;j<3;j++)ans-=o.a[0][1][j]; 69 for(int j=0;j<2;j++)ans-=o.a[0][3][j]; 70 printf("%lld\n",ans); 71 } 72 } 73 }
原文：https://www.cnblogs.com/PYWBKTDA/p/12056616.html
