中国石油大学（华东）暑期集训--二进制（BZOJ5294）【线段树】

问题 C: 二进制

时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

pupil发现对于一个十进制数，无论怎么将其的数字重新排列，均不影响其是不是3的倍数。他想研究对于二进制，是否也有类似的性质。于是他生成了一个长为n的二进制串，希望你对于这个二进制串的一个子区间，能求出其有多少位置不同的连续子串，满足在重新排列后（可包含前导0）是一个3的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。由于他想尝试尽量多的情况，他有时会修改串中的一个位置，并且会进行多次询问。

输入

输入第一行包含一个正整数n，表示二进制数的长度。
之后一行n个空格隔开的整数，保证均是0或1，表示该二进制串。
之后一行一个整数m，表示询问和修改的总次数。
之后m行每行为1 i，表示pupil修改了串的第i个位置（0变成1或1变成0），或2 l r，表示pupil询问的子区间是[l,r]。
串的下标从1开始。

输出

对于每次询问，输出一行一个整数表示对应该询问的结果。

样例输入

样例输出

2
3

提示

对于第一个询问，区间[2,2]只有数字0，是3的倍数，区间[1,3]可以重排成011₍₂₎=3₍₁₀₎，是3的倍数，其他区间均不能重排成3的倍数。
对于第二个询问，全部三个区间均能重排成3的倍数（注意00也是合法的）。

对于20%的数据，1≤n,m≤100；
对于50%的数据，1≤n,m≤5000；
对于100%的数据，1≤n,m≤100000，l≤r。

Solution：

设cnt0，cnt1分别为[l,r]区间内的1和0的个数，易得：

　　1. if cnt1==1 => 不可整除3

　　2. if cnt1&1 and cnt0<2 => 不可整除3

　　简单证明上述结论：

　　　　显然结论1是成立的（1<<n不可能整除3），当cnt1为偶数时，显然也一定可以整除3，而当cnt1&1时：

　　　　先考虑这种情况，将一个二进制数将其两位两位拆分并求和得到sum，显然如果 sum%3==0 ，则该二进制数的十进制一定可以整除3。

　　　　如：111010001=>(01,11,01,00,01)，sum=1+3+1+0+1=6。

　　　　那么，对于奇数个1，从中挑出cnt1-3个“1”两两组合，确保对sum%3的结果无贡献后，再看剩下的3个“1”的情况：

　　　　　　①、sum(111)=4 无法整除。【区间内无0】

　　　　　　②、sum(1101)=4,sum(1011)=5 无法整除。【区间内只含有一个0】

　　　　　　③、sum(10101)=3 可整除。【区间内至少含有两个0】

　　综上：

　　　　我们用线段树去维护上述两种不合法情况，再用【总数-不合法数=合法数】来得到答案。

　　　　其中，dl/dr[2][2] 代表经过左右节点后：cnt0=0/1，cnt1&1?1:0。

　　　　fl/fr[3] 代表经过左右节点后：满足（cnt1==1 and cnt0==0/1）的方案数。

　　　　L/R表示经过左右节点后，连续0的长度。

代码：

  1 #include <iostream>
  2 #include <string>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <deque>
 10 #include <map>
 11 #include <set>
 12 #define range(i,a,b) for(auto i=a;i<=b;++i)
 13 #define LL long long
 14 #define ULL unsigned long long
 15 #define elif else if
 16 #define itrange(i,a,b) for(auto i=a;i!=b;++i)
 17 #define rerange(i,a,b) for(auto i=a;i>=b;--i)
 18 #define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
 19 #define IOS ios::sync_with_stdio(false);cin.tie(0)
 20 using namespace std;
 21 int n,m,op,l,r,A[int(1e5+5)];
 22 class SegTree{
 23 private:
 24     struct node{
 25         LL s,dl[2][2],dr[2][2],fl[3],fr[3],L,R;
 26         int cnt0,cnt1;
 27         void reset(){
 28             range(i,0,1)range(j,0,1)dl[i][j]=dr[i][j]=0;
 29             fl[0]=fl[1]=fr[0]=fr[1]=fl[2]=fr[2]=L=R=s=cnt0=cnt1=0;
 30         }
 31         node(){reset();}
 32     }tree[int(1e5+5)<<2];
 33     node comb(node A,node B){
 34         node tmp;
 35         range(i,0,1)range(j,0,1){
 36             tmp.dl[i][j]+=A.dl[i][j];
 37             tmp.dr[i][j]+=B.dr[i][j];
 38             if(i>=A.cnt0)tmp.dl[i][j]+=B.dl[i-A.cnt0][j^(A.cnt1&1)];
 39             if(i>=B.cnt0)tmp.dr[i][j]+=A.dr[i-B.cnt0][j^(B.cnt1&1)];
 40         }
 41         range(i,0,2){
 42             tmp.fl[i]+=A.fl[i];
 43             tmp.fr[i]+=B.fr[i];
 44             if(!A.cnt1)tmp.fl[min(2,i+A.cnt0)]+=B.fl[i];
 45             if(!B.cnt1)tmp.fr[min(2,i+B.cnt0)]+=A.fr[i];
 46         }
 47         if(A.cnt1==1 and B.L){
 48             ++tmp.fl[min(2LL,A.cnt0+B.L)];
 49             tmp.fl[2]+=B.L-1;
 50         }
 51         if(B.cnt1==1 and A.R){
 52             ++tmp.fr[min(2LL,B.cnt0+A.R)];
 53             tmp.fr[2]+=A.R-1;
 54         }
 55         tmp.L=(!A.cnt1?A.cnt0+B.L:A.L);tmp.R=(!B.cnt1?B.cnt0+A.R:B.R);
 56         tmp.cnt0=A.cnt0+B.cnt0;tmp.cnt1=A.cnt1+B.cnt1;tmp.s+=A.s+B.s;
 57         tmp.s+=A.dr[0][1]*(B.dl[1][0]+B.dl[0][0])+A.dr[1][0]*B.dl[0][1];
 58         tmp.s+=A.dr[0][0]*(B.dl[1][1]+B.dl[0][1])+A.dr[1][1]*B.dl[0][0];
 59         if(B.L)tmp.s+=(A.fr[1]+A.fr[2])*B.L+A.fr[0]*(B.L-1);
 60         if(A.R)tmp.s+=(B.fl[1]+B.fl[2])*A.R+B.fl[0]*(A.R-1);
 61         return tmp;
 62     }
 63     void pushup(node &tmp,int x){
 64         tmp.reset();
 65         if(x)tmp.s=tmp.fl[0]=tmp.fr[0]=tmp.dl[0][1]=tmp.dr[0][1]=tmp.cnt1=1;
 66         else tmp.dl[1][0]=tmp.dr[1][0]=tmp.L=tmp.R=tmp.cnt0=1;
 67     };
 68 public:
 69     void build(int l,int r,int rt=1){
 70         if(l==r){
 71             pushup(tree[rt],A[l]);
 72             return;
 73         }
 74         int m=(l+r)>>1;
 75         build(l,m,rt<<1);
 76         build(m+1,r,rt<<1|1);
 77         tree[rt]=comb(tree[rt<<1],tree[rt<<1|1]);
 78     }
 79     void update(int l,int r,int rt,int L){
 80         if(l==r){
 81             pushup(tree[rt],A[l]);
 82             return;
 83         }
 84         int m=(l+r)>>1;
 85         if(L<=m)update(l,m,rt<<1,L);
 86         else update(m+1,r,rt<<1|1,L);
 87         tree[rt]=comb(tree[rt<<1],tree[rt<<1|1]);
 88     }
 89     node query(int l,int r,int rt,int L,int R){
 90         if(L<=l and r<=R)return tree[rt];
 91         int m=(l+r)>>1;
 92         if(R<=m)return query(l,m,rt<<1,L,R);
 93         if(L>m)return query(m+1,r,rt<<1|1,L,R);
 94         return comb(query(l,m,rt<<1,L,m),query(m+1,r,rt<<1|1,m+1,R));
 95     }
 96 }segTree;
 97 void init(){
 98     scanf("%d",&n);
 99     range(i,1,n)scanf("%d",A+i);
100     segTree.build(1,n);
101     scanf("%d",&m);
102 }
103 void solve(){
104     while(m--){
105         scanf("%d%d",&op,&l);
106         if(op&1)A[l]^=1,segTree.update(1,n,1,l);
107         else{
108             scanf("%d",&r);
109             printf("%lld
",1LL*(r-l+1)*(r-l+2)/2-segTree.query(1,n,1,l,r).s);
110         }
111     }
112 }
113 int main() {
114     init();
115     solve();
116     return 0;
117 }

View Code