BJOI的题目感觉有点难写
题目分析：
首先推一波结论。接下来的一切都在模3意义下
现在我们将二进制位重组，不难发现的是2^0≡1,2^1≡2,2^2≡1,2^3≡2....所以我们考虑这样的式子
2*a+b≡0 mod 3
其中a+b为某个区间的1的个数，令它为tot。试着带几个值看看。
2*1+1+3k≡0;
2*2+2+3k≡0;
2*3+0+3k≡0;
可以发现a和b实际上在任何时候都有a≡b。也就是说a≡tot-a。
这等价于2*a≡tot。对于每一个tot，我们把它对应最好的a写出来，会发现当(tot%6)%2==0的时候，这个区间在任何时候都满足它可以通过重组被3整除。
否则它的这个区间至少需要2个0，这是因为你重组之后结果是余1，这时候你需要将一个奇数位换到一个偶数位，所以你需要2个0来新构建一个偶数位。
这里需要注意，1的情况是特殊的，它无论如何也不能被3整除。
接着我们得到了结论，当(tot%6)%2==0或者(tot%6)%2==1且该区间中至少有2个0，那么该区间可以通过重组被3整除。
考虑问题的反面，有多少个区间不可以被3整除，这就等价于找(tot%6)%2==1且该区间只有1个0或没有0的区间的个数，这个问题是线段树的一个基本操作。
该区间的所有子区间的个数等于一个等差数列。线段树通过维护第一个1，第二个1，第一个0，第二个0，最后一个0，倒数第二个0，最后一个1，倒数第二个1的位置和不满足的子区间数。可以很好的合并。
时间复杂度O(nlogn)，由于维护的信息比较多，常数很大。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 105000; struct node{ long long hh; //1,3,5 int l1,l2,r1,r2; int p1,p2,q1,q2; }T[maxn<<2]; int wh[maxn]; int n,q; node ans;//int rl,rr; int dm[6],md[6]; void get_height(int l,int r,int *d,int now = 0){ if(now == 0) for(int i=0;i<6;i++) d[i]=0; if(l > r) return; int len = r-l+1; for(int i=0;i<6;i++){ d[(i+l-1)%6] += (len/6)+(len%6>=i); if(i == 0)d[(i+l-1)%6]--; } } node merge(node a,node b,int l,int mid,int r){ if(l > mid) return b; node z; z.hh = a.hh+b.hh; z.l1 = z.l2 = z.r1 = z.r2 = z.p1 = z.p2 =z.q1 = z.q2 = 0; int mem = mid-a.r1,nen = b.l2-mid-1; int lem = mid-a.r2,len = b.l1-mid-1; if(b.l2==0)nen = r-mid; if(a.r1==0)mem=mid-l+1; if(b.l1 == 0)len = r-mid; if(a.r2==0)lem=mid-l+1; get_height(1,mem,dm);get_height(1,len,md); get_height(1+len,nen-1,md,1); if(b.l1) md[len%6]++; for(int i=0;i<6;i++){ z.hh += 1ll*dm[i]*md[(7-i)%6]; z.hh += 1ll*dm[i]*md[(9-i)%6]; z.hh += 1ll*dm[i]*md[(11-i)%6]; } get_height(mem+1,lem-1,dm);get_height(1,len,md); if(a.r1) dm[mem%6]++; for(int i=0;i<6;i++){ z.hh += 1ll*dm[i]*md[(7-i)%6]; z.hh += 1ll*dm[i]*md[(9-i)%6]; z.hh += 1ll*dm[i]*md[(11-i)%6]; } lem = mid-a.q2-(mid-a.q1),len = b.p1-mid-1; if(a.q2 == 0)lem = (a.q1==0?0:mid-l+1-(mid-a.q1)); if(b.p1 == 0)len = r-mid; z.hh += 1ll*lem*len; if(a.q1==mid&&b.l1==mid+1)z.hh--; lem = mid-a.q1,len = b.p2-mid-1-(b.p1-mid-1); if(a.q1 == 0)lem = mid-l+1; if(b.p2 == 0)len = (b.p1==0?0:r-mid-(b.p1-mid-1)); z.hh += 1ll*lem*len; if(a.r1==mid&&b.p1==mid+1)z.hh--; int num = 0; if(a.l1) dm[++num]=a.l1; if(a.l2) dm[++num]=a.l2; if(b.l1) dm[++num]=b.l1; if(b.l2) dm[++num]=b.l2; if(num>=1) z.l1 = dm[1]; if(num>=2) z.l2 = dm[2]; num = 0; if(b.r1) dm[++num]=b.r1; if(b.r2) dm[++num]=b.r2; if(a.r1) dm[++num]=a.r1; if(a.r2) dm[++num]=a.r2; if(num>=1) z.r1 = dm[1]; if(num>=2) z.r2 = dm[2]; num = 0; if(a.p1) dm[++num]=a.p1; if(a.p2) dm[++num]=a.p2; if(b.p1) dm[++num]=b.p1; if(b.p2) dm[++num]=b.p2; if(num>=1) z.p1 = dm[1]; if(num>=2) z.p2 = dm[2]; num = 0; if(b.q1) dm[++num]=b.q1; if(b.q2) dm[++num]=b.q2; if(a.q1) dm[++num]=a.q1; if(a.q2) dm[++num]=a.q2; if(num>=1) z.q1 = dm[1]; if(num>=2) z.q2 = dm[2]; return z; } void init(int now,int pla){ if(wh[pla] == 0){ T[now].hh = 0; T[now].l1 = T[now].r1 = pla; T[now].l2 = T[now].r2 = 0; T[now].q1 = T[now].q2 = T[now].p1 = T[now].p2 = 0; }else{ T[now].hh=0; T[now].p1 = T[now].q1 = pla; T[now].hh=1; T[now].p2 = T[now].q2 = 0; T[now].l1 = T[now].r1 = T[now].l2 = T[now].r2 = 0; } } void Modify(int now,int l,int r,int pla){ if(l == r){init(now,pla);return;} int mid = (l+r)/2; if(mid >= pla) Modify(now<<1,l,mid,pla); else Modify(now<<1|1,mid+1,r,pla); T[now] = merge(T[now<<1],T[now<<1|1],l,mid,r); } void Query(int now,int tl,int tr,int l,int r){ if(tl >= l && tr <= r){ans = merge(ans,T[now],l,tl-1,tr);return;} if(tr < l || tl > r) return; int mid = (tl+tr)/2; Query(now<<1,tl,mid,l,r); Query(now<<1|1,mid+1,tr,l,r); } void build_tree(int now,int l,int r){ if(l == r){init(now,l);return;} int mid = (l+r)/2; build_tree(now<<1,l,mid); build_tree(now<<1|1,mid+1,r); T[now] = merge(T[now<<1],T[now<<1|1],l,mid,r); } void read(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&wh[i]); build_tree(1,1,n); } void work(){ scanf("%d",&q); for(int i=1;i<=q;i++){ int x; scanf("%d",&x); if(x == 1){ int p; scanf("%d",&p); wh[p] ^= 1; Modify(1,1,n,p); }else{ int l,r; scanf("%d%d",&l,&r); Query(1,1,n,l,r); long long res = 1ll*(2+r-l)*(r-l+1)/2; printf("%lld ",res-ans.hh); } } } int main(){ read(); work(); return 0; }