BJOI2018 二进制

题目:

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

思路:

   因为 ,所以如果区间中有偶数个 ,那么只要全部排在一起就行了。考虑奇数个 ,比如 时,可以排成 。所以不合法的情况只有两种:
   1.只有
   2. 的个数小于 的个数为奇数。
   可以直接用线段树维护这个两种区间的个数,但是细节巨多,极不推荐
   如果把第2种情况再拆成 两种情况, 的个数为 的情况可以直接用线段树维护连续 的长度。设 表示长度为 区间能被划分成几个不同的奇数长度区间。那么
   而剩下两种,可以用 set 维护前驱后继就能算出这两个情况的方案数了(类似 )。对于每一个点,记录它的方案数,用树状数组区间查询即可,但是最左、右的 会受到影响,所以要重新计算这 个点的贡献。

代码:

#include <bits/stdc++.h>
#define clr(a) memset(a,0,sizeof a)
#define _(...) (void)(__VA_ARGS__)
#define pw(x) ((ll)(x)*(x))
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
using std::max;using std::min;
typedef long long ll;
const int N=1e5+5;

int n;

ll num[N];
void init_num(){
    rep(i,3,n)
        num[i]=num[i-1]+(i-1)/2;
}
struct Segment{
    struct Node{
        int lc,rc,L,R;
        ll sum;
        void set(int a,int x){
            lc=rc=x;L=R=a;sum=0;
        }
        Node operator + (const Node _) const {
            return (Node){
                lc==R-L+1?lc+_.lc:lc,
                _.rc==_.R-_.L+1?_.rc+rc:_.rc,
                L,_.R,
                sum+_.sum-num[rc]-num[_.lc]+num[rc+_.lc]
            };
        }
    }node[N<<2];
    #define ls (o<<1)
    #define rs (o<<1|1)
    #define mid (L+R>>1)
    #define lson ls,L,mid
    #define rson rs,mid+1,R
    void build(bool a[],int o=1,int L=1,int R=n){
        if(L==R)return node[o].set(L,a[L]);
        build(a,lson);build(a,rson);
        node[o]=node[ls]+node[rs];
    }
    void upd(int a,int x,int o=1,int L=1,int R=n){
        if(L==R)return node[o].set(a,x);
        if(a<=mid)upd(a,x,lson);
        else upd(a,x,rson);
        node[o]=node[ls]+node[rs];
    }
    Node qry(int l,int r,int o=1,int L=1,int R=n){
        if(l==L&&r==R)return node[o];
        if(r<=mid)return qry(l,r,lson);
        else if(l>mid)return qry(l,r,rson);
        else return qry(l,mid,lson)+qry(mid+1,r,rson);
    }
}T;

struct BIT{
    ll c[N],a;
    #define low(x) (-(x)&(x))
    void upd(int x,ll k){
        for(;x<N;x+=low(x))c[x]+=k;
    }
    ll qry(int x){
        for(a=0;x;x-=low(x))a+=c[x];
        return a;
    }
    ll qry(int l,int r){return qry(r)-qry(l-1);}
}C,cnt[2];

std::set<int> s[2];
typedef std::set<int>::iterator sit;
ll calc(int d1,int d2,int x){
    if(x==0)//11110111 d1=5,d2=4
        return (ll)(d1/2)*((d2-1)/2+1)+(ll)((d1-1)/2+1)*(d2/2);
    else    //00010000 d1=4,d2=5
        return (ll)d1*d2-(d1>1)-(d2>1);
}
ll val[N];
ll qry(int l,int r){
    ll ans=(ll)(r-l+1)*(r-l+2)/2;
    ans-=T.qry(l,r).sum+C.qry(l,r);
    rep(d,0,1){
        int k=cnt[d].qry(l,r);
        if(k==1){
            int id=*s[d].lower_bound(l);
            ans+=val[id];
            ans-=calc(id-(l-1),(r+1)-id,d);
        }
        else if(k>1){
            sit p=s[d].lower_bound(l),nxt=p;nxt++;
            ans+=val[*p];
            ans-=calc(*p-(l-1),*nxt-*p,d);
            p=--s[d].upper_bound(r);nxt=p;nxt--;
            ans+=val[*p];
            ans-=calc(*p-*nxt,(r+1)-*p,d);
        }
    }
    return ans;
}
bool now[N];
void maintain(int x){
    sit l=s[now[x]].find(x),r=l;
    l--;r++;
    val[x]=calc(x-*l,*r-x,now[x]);
}
void upd(int x){
    sit l=s[now[x]].find(x),r=l;
    l--;r++;
    int vec[5]={*l,*r,x};
    s[now[x]].erase(x);
    cnt[now[x]].upd(x,-1);
    now[x]^=1;
    cnt[now[x]].upd(x,1);
    s[now[x]].insert(x);
    T.upd(x,now[x]);
    l=s[now[x]].find(x),r=l;
    l--;r++;
    vec[3]=*l;vec[4]=*r;
    rep(i,0,4){
        int x=vec[i];
        if(x<1||x>n)continue;
        C.upd(x,-val[x]);
        maintain(x);
        C.upd(x,val[x]);
    }
}

void debug(){}

int main(){
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    scanf("%d",&n);
    init_num();
    s[0].insert(0);s[0].insert(n+1);
    s[1].insert(0);s[1].insert(n+1);
    rep(i,1,n){
        int d;
        scanf("%d",&d);
        now[i]=d;
        s[now[i]].insert(i);
        cnt[now[i]].upd(i,1);
    }
    T.build(now);
    rep(i,1,n){
        maintain(i);
        C.upd(i,val[i]);
    }
    int m;
    scanf("%d",&m);
    rep(i,1,m){
        int f,a,l,r;
        scanf("%d",&f);
        if(f==1){
            scanf("%d",&a);
            upd(a);
        }
        else {
            scanf("%d%d",&l,&r);
            printf("%lld\n",qry(l,r));
        }
    }
    return 0;
}