[NOI2017]整数

题目大意：

\(n(n\le10^6)\)次操作维护一个长度为\(30n\)的二进制整数\(x\)，支持以下两种操作：

1. 将这个整数加上\(a\cdot2^b(|a|\le10^9,b\le30)\)。
2. 询问这个整数第\(k\)位的值。

题目保证任何时刻\(x\ge0\)。

思路：

维护每一位的值，并在线段树上记录每个区间是否含有\(0\)或\(1\)，以便发生进退位时快速查找到进退位结束的位置。区间修改，单点查询。时间复杂度\(\mathcal O(n\log(30n))\)。显然会TLE。

考虑使用压位线段树，每\(30\)位压在一个叶子结点，修改操作可以枚举\(a\)的每一个二进制位\(1\)并进行相应的操作。由于\(a\)最多有\(\log a\)个二进制位，因此时间复杂度\(\mathcal O(n\log n\log a)\)。实测\(76\)分。

事实上，由于\(a\)在线段树中最多对应\(2\)个叶子结点，而叶子结点内部的进位就是整数加减法，不需要专门在线段树上查找。我们可以直接将\(a\)拆分成两次修改，时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
    register char ch;
    register bool neg=false;
    while(!isdigit(ch=getchar())) neg|=ch=='-';
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return neg?-x:x;
}
const int N=1e6,base=30,lim=(1<<base)-1;
typedef long long int64;
int n;
inline int bel(const int &x) {
    return x/base+1;
}
class SegmentTree {
    #define _left <<1
    #define _right <<1|1
    #define mid ((b+e)>>1)
    private:
        bool have[2][N<<2];
        int val[N],tag[N<<2];
        void push_up(const int &p) {
            have[0][p]=have[0][p _left]||have[0][p _right];
            have[1][p]=have[1][p _left]||have[1][p _right];
        }
        void push_down(const int &p,const int &b,const int &e) {
            if(tag[p]==-1) return;
            b==mid?val[b]=lim*tag[p]:tag[p _left]=tag[p];
            mid+1==e?val[e]=lim*tag[p]:tag[p _right]=tag[p];
            have[tag[p]][p _left]=have[tag[p]][p _right]=true;
            have[!tag[p]][p _left]=have[!tag[p]][p _right]=false;
            tag[p]=-1;
        }
    public:
        void build(const int &p,const int &b,const int &e) {
            tag[p]=-1;
            have[0][p]=true;
            if(b==e) return;
            build(p _left,b,mid);
            build(p _right,mid+1,e);
        }
        int find(const int &p,const int &b,const int &e,const int &x,const bool &t) {
            if(!have[t][p]) return 0;
            if(b==e) {
                const int tmp=(t?val[b]:~val[b])>>(bel(x)!=b?0:x%base);
                if(tmp==0) return 0;
                const int pos=__builtin_ffs(tmp)-1+(bel(x)!=b?0:x%base);
                return pos<base?pos+(b-1)*base+1:0;
            }
            push_down(p,b,e);
            if(bel(x)<=mid) {
                return find(p _left,b,mid,x,t)?:find(p _right,mid+1,e,x,t);
            } else {
                return find(p _right,mid+1,e,x,t);
            }
        }
        void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const bool &t) {
            if(tag[p]==t) return;
            if(b==e) {
                if(!t) val[b]=~val[b];
                val[b]|=(1<<(r%base+1))-(1<<(l%base));
                if(!t) val[b]=~val[b];
                have[0][p]=lim-val[b];
                have[1][p]=val[b];
                return;
            }
            if(l==(b-1)*base&&r==e*base-1) {
                tag[p]=t;
                have[!t][p]=false;
                have[t][p]=true;
                return;
            }
            push_down(p,b,e);
            if(bel(l)<=mid) modify(p _left,b,mid,l,std::min(mid*base-1,r),t);
            if(bel(r)>mid) modify(p _right,mid+1,e,std::max(mid*base,l),r,t);
            push_up(p);
        }
        void change(const int &p,const int &b,const int &e,const int &x,const bool &t) {
            if(tag[p]==t) return;
            if(b==e) {
                val[b]^=1<<(x%base);
                have[0][p]=lim-val[b];
                have[1][p]=val[b];
                return;
            }
            push_down(p,b,e);
            if(bel(x)<=mid) change(p _left,b,mid,x,t);
            if(bel(x)>mid) change(p _right,mid+1,e,x,t);
            push_up(p);
        }
        bool query(const int &p,const int &b,const int &e,const int &x) {
            if(!have[0][p]) return 1;
            if(!have[1][p]) return 0;
            if(b==e) return val[b]>>(x%base)&1;
            return bel(x)<=mid?query(p _left,b,mid,x):query(p _right,mid+1,e,x);
        }
        bool modify2(const int &p,const int &b,const int &e,const int &x,const int &y,const bool &t) {
            if(b==e) {
                t?val[b]-=y:val[b]+=y;
                const bool ret=val[b]<0||val[b]>lim;
                if(val[b]>lim) val[b]-=lim+1;
                if(val[b]<0) val[b]+=lim+1;
                have[0][p]=lim-val[b];
                have[1][p]=val[b];
                return ret;
            }
            push_down(p,b,e);
            bool ret;
            if(x<=mid) ret=modify2(p _left,b,mid,x,y,t);
            if(x>mid) ret=modify2(p _right,mid+1,e,x,y,t);
            push_up(p);
            return ret;
        }
    #undef _left
    #undef _right
    #undef mid
};
SegmentTree t;
int main() {
    n=getint();
    getint(),getint(),getint();
    t.build(1,1,n);
    for(register int i=0;i<n;i++) {
        const int opt=getint();
        if(opt==1) {
            int a=getint();
            const int b=getint();
            const bool v=a<0;
            if(v) a=-a;
            const int t1=(int64)a<<(b%30)&lim;
            const int t2=(((int64)a<<(b%30))-((int64)a<<(b%30)&lim))>>base;
            if(t.modify2(1,1,n,bel(b),t1,v)) {
                const int pos=t.find(1,1,n,bel(b)*30,v)-1;
                t.change(1,1,n,pos,v);
                if(pos>bel(b)*30) t.modify(1,1,n,bel(b)*30,pos-1,v);
            }
            if(t.modify2(1,1,n,bel(b)+1,t2,v)) {
                const int pos=t.find(1,1,n,(bel(b)+1)*30,v)-1;
                t.change(1,1,n,pos,v);
                if(pos>(bel(b)+1)*30) t.modify(1,1,n,(bel(b)+1)*30,pos-1,v);
            }
        }
        if(opt==2) {
            printf("%d\n",t.query(1,1,n,getint()));
        }
    }
    return 0;
}

[NOI2017]整数

原文：https://www.cnblogs.com/skylee03/p/9289748.html