Description

Pupil 發現對于一個十進制數，無論怎么將其的數字重新排列，均不影響其是不是3 的倍數。他想研究對于二進制，是否也有類似的性質。于是他生成了一個長為n的二進制串，希望你對于這個二進制串的一個子區間，能求出其有多少位置不同的連續子串，滿足在重新排列后（可包含前導 0）是一個3的倍數。兩個位置不同的子區間指開始位置不同或結束位置不同。由于他想嘗試盡量多的情況，他有時會修改串中的一個位置，并且會進行多次詢問。

Input

從文件 binary.in 中讀入數據。
輸入第一行包含一個正整數 n，表示二進制數的長度。
之后一行 n 個空格隔開的整數，保證均是0或1，表示該二進制串。
之后一行一個整數 m，表示詢問和修改的總次數。
之后m行每行為1 i，表示Pupil修改了串的第i個位置（0 變成 1 或 1 變成 0 ），或 2 l r，表示Pupil詢問的子區間是[l,r]。
串的下標從 1 開始。

Output

輸出到文件 binary.out 中。
對于每次詢問，輸出一行一個整數表示對應該詢問的結果。

Sample Input

4
1 0 1 0
3
2 1 3
1 3
2 3 4

Sample Output

2
3

Data Constraint

對于 20% 的數據，1 ≤ n,m ≤ 100。
對于 50% 的數據，1 ≤ n,m ≤ 5000。
對于 100% 的數據，1 ≤ n,m ≤ 100000，l ≤ r。

Hint

對于第一個詢問，區間 [2,2] 只有數字 0，是 3 的倍數，區間 [1,3] 可以重排成011(2) = 3(10) ，是3的倍數，其他區間均不能重排成 3 的倍數。對于第二個詢問，全部三個區間均能重排成 3 的倍數（注意 00 也是合法的）。

Solution

• 我們考慮一個二進制數 a 如何變成十進制數：

• 就是等于 a1?20+a2?21+a3?22+…+an?2n?1 。

• 我們知道一個十進制數如果各位加起來是3的倍數那么它就是3的倍數。

• 而像 1,2,4,8,16,32…… 分別距離3的倍數是相差 ?1,1,?1,1,?1…… 。

• 于是我們得到這樣的結論：先設區間長度為 L ，區間中1的個數為 S 。

• 如果 S 是偶數就能兩兩配對（1配-1），一定能行。

• 而 S 是奇數的話，S=1（只有一個1）肯定不行，而 S>1 可以這樣：

• 前面的1先兩兩配對，剩下三個1，用三個1或-1配對即可，這需要滿足：L≥S+2

• 我們用線段樹維護即可，O(N?log?N) 。

• 什么？這太難維護？確實，這太難維護了。

• 我們考慮正難則反，用線段樹維護區間中不合法的子區間個數，用總區間個數減去就是答案了。

• 兩個區間合并時計算跨兩個區間的子區間個數，這需要維護許多信息。

• 重新看看我們到底要算什么：（設 C0,C1 分別表示區間中 0 和 1 的個數）

• C1是奇數，且 C0<2 的區間個數；
• C1=1，且 C0≥2 的區間個數（C0<2 的之前在第一種中已經算過了）。

• 于是我們維護幾個信息（0同理，即反過來）：

• 區間前后綴 1 的長度；①
• 區間前后綴一串1（可以沒有），接個0（記著位置），再接一串1（也可以沒有）的長度②。

• 什么 C0=0 就是 ① 和 ① 接起來，什么 C0=1 就是 ① 和 ② 接起來……

• 那么我們就可以直接分類討論算了，細節和碼量都很多。

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=1e5+5; struct data {LL sum;int l,r;int l1,r1;//11111int l2,r2,pl2,pr2;//11011int l3,r3,pl3,pr3;//00100int l4,r4;//00000 }f[N<<2]; int qx,qy; int a[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline data merge(data f1,data f2) {data g;g.l=f1.l,g.r=f2.r;g.sum=f1.sum+f2.sum;//11111g.l1=f1.l1,g.r1=f2.r1;if(f1.l1==f1.r-f1.l+1) g.l1+=f2.l1;if(f2.r1==f2.r-f2.l+1) g.r1+=f1.r1;g.sum+=(LL)(f1.r1+1)/2*(f2.l1/2)+(LL)(f1.r1/2)*((f2.l1+1)/2);//11011if(f1.l1==f1.r-f1.l+1){g.l2=f1.l1+f2.l2;g.pl2=f2.pl2?f1.l1+f2.pl2:0;}else{g.l2=f1.l2;g.pl2=f1.pl2;if(f1.l2==f1.r-f1.l+1) g.l2+=f2.l1;}if(f2.r1==f2.r-f2.l+1){g.r2=f2.r1+f1.r2;g.pr2=f1.pr2?f2.r1+f1.pr2:0;}else{g.r2=f2.r2;g.pr2=f2.pr2;if(f2.r2==f2.r-f2.l+1) g.r2+=f1.r1;}if(f2.pl2){int ll=f1.r1,rr=f2.l2-f2.pl2+1,odd=(f2.pl2-1)&1;g.sum+=(LL)(ll+(odd^1))/2;if(rr>1) g.sum+=(LL)rr/2*((ll+odd)/2)+(LL)(rr-1)/2*((ll+(odd^1))/2);}if(f1.pr2){int ll=f1.r2-f1.pr2+1,rr=f2.l1,odd=(f1.pr2-1)&1;g.sum+=(LL)(rr+(odd^1))/2;if(ll>1) g.sum+=(LL)ll/2*((rr+odd)/2)+(LL)(ll-1)/2*((rr+(odd^1))/2);}//00000g.l4=f1.l4,g.r4=f2.r4;if(f1.l4==f1.r-f1.l+1) g.l4+=f2.l4;if(f2.r4==f2.r-f2.l+1) g.r4+=f1.r4;//00100if(f1.l4==f1.r-f1.l+1){g.l3=f1.l4+f2.l3;g.pl3=f2.pl3?f1.l4+f2.pl3:0;}else{g.l3=f1.l3;g.pl3=f1.pl3;if(f1.l3==f1.r-f1.l+1) g.l3+=f2.l4;}if(f2.r4==f2.r-f2.l+1){g.r3=f2.r4+f1.r3;g.pr3=f1.pr3?f2.r4+f1.pr3:0;}else{g.r3=f2.r3;g.pr3=f2.pr3;if(f2.r3==f2.r-f2.l+1) g.r3+=f1.r4;}if(f2.pl3 && f1.pr3!=1){int ll=f1.r4,rr=f2.l3-f2.pl3+1;g.sum+=(LL)ll*rr;if(!f2.l4 && f1.r4) g.sum--;}if(f1.pr3 && f2.pl3!=1){int ll=f1.r3-f1.pr3+1,rr=f2.l4;g.sum+=(LL)ll*rr;if(!f1.r4 && f2.l4) g.sum--;}return g; } void make(int v,int l,int r) {f[v].l=l,f[v].r=r;if(l==r){if(a[l]){f[v].l1=f[v].r1=f[v].sum=1;f[v].pl3=f[v].pr3=1;}else{f[v].l4=f[v].r4=1;f[v].pl2=f[v].pr2=1;}f[v].l2=f[v].r2=1;f[v].l3=f[v].r3=1;return;}int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);f[v]=merge(f[v<<1],f[v<<1|1]); } void change(int v,int l,int r) {if(l==r){if(f[v].sum){f[v].l1=f[v].r1=f[v].sum=0;f[v].pl2=f[v].pr2=1;f[v].l4=f[v].r4=1;f[v].pl3=f[v].pr3=0;}else{f[v].l1=f[v].r1=f[v].sum=1;f[v].pl2=f[v].pr2=0;f[v].l4=f[v].r4=0;f[v].pl3=f[v].pr3=1;}return;}int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid); else change(v<<1|1,mid+1,r);f[v]=merge(f[v<<1],f[v<<1|1]); } data find(int v,int l,int r) {if(qx<=l && r<=qy) return f[v];int mid=l+r>>1;data ff;bool pd=false;if(qx<=mid) ff=find(v<<1,l,mid),pd=true;if(qy>mid) ff=pd?merge(ff,find(v<<1|1,mid+1,r)):find(v<<1|1,mid+1,r);return ff; } int main() {freopen("binary.in","r",stdin);freopen("binary.out","w",stdout);int n=read();for(int i=1;i<=n;i++) a[i]=read();make(1,1,n);int m=read();while(m--)if(read()==1){qx=read();change(1,1,n);}else{qx=read(),qy=read();data ans=find(1,1,n);LL all=((LL)qy-qx+1)*(qy-qx+2)>>1;printf("%lld\n",all-ans.sum);}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5689. 【GDOI2018Day2模拟4.25】二进制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。