[NOI2017]整数

古城微笑少年丶 2021-11-13 15:36 219阅读 0赞

[\[NOI2017\]整数][NOI2017]

压位+线段树

unsigned long long压64位

加法为例。

a拆成两半加入。处理进位

往后进位？

二分到第一个0位置，变成1，途中的都变成0

线段树二分+区间赋值。

维护区间有没有0

减法同理。

注意：

1.只要区间里面有更新，就要pushup！

2.叶子节点加减也要处理has\[0\],has\[1\]

3.a的位数，用log2(a)查，不是\_\_builtin\_popcount(a)。。。那个是1的个数

4.然后，st=b，nd=b+log(2)，nd不用-1，，，，

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    #define ull unsigned long long 
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=998244353;
    il int ad(int x,int y){
        return x+y>=mod?x+y-mod:x+y;}
    il int sub(int x,int y){
        return ad(x,mod-y);}
    il int mul(int x,int y){
        return (ll)x*y%mod;}
    il void inc(int &x,int y){x=ad(x,y);}
    il void inc2(int &x,int y){x=mul(x,y);}
    il int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    template<class ...Args>il int ad(const int a,const int b,const Args &...args) {
        return ad(ad(a,b),args...);}
    template<class ...Args>il int mul(const int a,const int b,const Args &...args) {
        return mul(mul(a,b),args...);}
    }
    // using namespace Modulo;
    namespace Miracle{
    const int N=500000+5;
    struct node{
        int has[2];
        int tag;
        ull val;
    }t[4*N];
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid ((l+r)>>1)
    ull lim[2];
    void pushup(int x){
        t[x].has[0]=t[ls].has[0]|t[rs].has[0];
        t[x].has[1]=t[ls].has[1]|t[rs].has[1];
    }
    void fu(int x,int c){
        t[x].tag=c;
        t[x].has[c]=1;
        t[x].val=lim[c];
        t[x].has[c^1]=0;
    }
    void pushdown(int x){
        if(t[x].tag!=-1){
            fu(ls,t[x].tag);
            fu(rs,t[x].tag);
            t[x].tag=-1;
        }
    }
    void build(int x,int l,int r){
        if(l==r){
            t[x].tag=-1;t[x].val=0;
            t[x].has[0]=1;
            return ;
        }
        t[x].tag=-1;t[x].has[0]=1;
        build(ls,l,mid);build(rs,mid+1,r);
    }
    int jin;
    void che(int x){
        if(t[x].val==lim[0]){
            t[x].has[0]=1;t[x].has[1]=0;
        }else if(t[x].val==lim[1]){
            t[x].has[0]=0;t[x].has[1]=1;
        }else{
            t[x].has[0]=t[x].has[1]=1;
        }
    }
    void add(int x,int l,int r,int p,ull c,int typ){
        //jin==0 || 1
        if(l==r){
            if(typ==1){
                ull nc=t[x].val+c;
                if(nc<t[x].val) jin=1;
                else jin=0;
    
                t[x].val=nc;
            }else{
                ull nc=t[x].val-c;
                if(nc>t[x].val) jin=1;
                else jin=0;
    
                t[x].val=nc;
            }
            che(x);
            return;
        }
        pushdown(x);
        if(p<=mid) add(ls,l,mid,p,c,typ);
        else add(rs,mid+1,r,p,c,typ);
        pushup(x);
    }
    
    int fin(int x,int l,int r,int p,int c){
        //first >=p and has[c]==1
        if(!t[x].has[c]) return -1;
        if(l==r){
            if(c==0) t[x].val++;
            else t[x].val--;
            che(x);
            return l;
        }
        pushdown(x);
        int ret=-1;
        if(p<=mid){
            ret=fin(ls,l,mid,p,c);
            if(ret==-1){
                ret=fin(rs,mid+1,r,p,c);
            }
        }else{
            ret=fin(rs,mid+1,r,p,c);
        }
        pushup(x);
        return ret;
    }
    void upda(int x,int l,int r,int L,int R,int c){
        if(L<=l&&r<=R){
            fu(x,c);
            return;
        }
        pushdown(x);
        if(L<=mid) upda(ls,l,mid,L,R,c);
        if(mid<R) upda(rs,mid+1,r,L,R,c);
        pushup(x);
    }
    int query(int x,int l,int r,int p,int c){
        if(l==r){
            return (t[x].val>>c)&1;
        }
        pushdown(x);
        if(p<=mid) return query(ls,l,mid,p,c);
        else return query(rs,mid+1,r,p,c);
    }int n,m;
    int main(){
        rd(m);int t;rd(t);rd(t);rd(t);
        int n=((30*m+60)/64)+10;
        build(1,0,n);
        // cout<<" after build "<<endl;
        lim[1]=(ull)-1;
        lim[0]=0;
        int op,a,b,k;
        while(m--){
            rd(op);
            if(op==1){
                rd(a);rd(b);
                if(a==0) continue;
                if(a>0){
                    int len=log2(a);
                    int st=b,nd=b+len;
                    int bst=st/64,bnd=nd/64;
                    // cout<<" st "<<st<<" nd "<<nd<<" bst "<<bst<<"  bnd "<<bnd<<endl;
                    jin=0;
                    if(bst==bnd){
                        add(1,0,n,bnd,(ull)a<<(st%64),1);
                    }else{
                        add(1,0,n,bst,(ull)a<<(st%64),1);
                        add(1,0,n,bnd,((ull)a>>(64-st%64))+jin,1);
                    }   
                    if(jin){
                        int pos=fin(1,0,n,bnd+1,0);
                        if(bnd+1<=pos-1){
                            upda(1,0,n,bnd+1,pos-1,0);
                        }
                    }
                }else {
                    a=-a;
                    int len=log2(a);
                    int st=b,nd=b+len;
                    int bst=st/64,bnd=nd/64;
                    jin=0;
                    if(bst==bnd){
                        add(1,0,n,bnd,(ull)a<<(st%64),-1);
                    }else{
                        add(1,0,n,bst,(ull)a<<(st%64),-1);
                        add(1,0,n,bnd,((ull)a>>(64-st%64))+jin,-1);
                    }   
                    if(jin){
                        int pos=fin(1,0,n,bnd+1,1);
                        if(bnd+1<=pos-1){
                            upda(1,0,n,bnd+1,pos-1,1);
                        }
                    }
                }
            }else{
                rd(k);
                printf("%d\n",query(1,0,n,k/64,k%64));
            }
        }
        // dfs(1,0,n);
        return 0;
    }
    
    }
    signed main(){
        // freopen("data.in","r",stdin);
        // freopen("my.out","w",stdout);
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

压位常用套路

注意细节。

转载于:https://www.cnblogs.com/Miracevin/p/11038278.html

[NOI2017]: https://www.luogu.org/problemnew/show/P3822