LibreOJ2302 - 「NOI2017」整数

Description

有一个整数\(x=0\)，对其进行\(n(n\leq10^6)\)次操作：

给出\(a(|a|\leq10^9),b(b\leq30n)\)，将\(x\)加上\(a\cdot 2^b\)。
询问\(x\)在二进制下位权为\(2^k(k\leq30n)\)的位的值。

保证任意时刻\(x\geq0\)。

Solution

用线段树来模拟二进制下的加减运算。

线段树上的每个位置维护\(30\)位二进制数，即第一位维护\(2^0...2^{29}\)，第二位维护\(2^{30}...2^{59}\)，以此类推。考虑当我们将某位置上的值修改为\(a\)后应当怎么做：

若\(a\in[0,2^{30})\)，则什么也不做。
若\(a\geq2^{30}\)，则需要进位：将前面一段连续的\(2^{30}-1\)修改为\(0\)，然后将这段\(2^{30}-1\)前面的一个数\(+1\)。
若\(a<0\)，则需要退位：将前面一段连续的\(0\)修改为\(2^{30}-1\)，然后将这段\(0\)前面的一个数\(-1\)。

那么我们需要区间修改，单点查询，并维护每个区间从低位到高位连续的\(0/2^{30}-1\)的长度。具体细节可以看代码。

时间复杂度\(O(nlogn)\)。

Code

//「NOI2017」整数

#include <cstdio>

#include <cstring>

inline char gc()

{

    static char now[1<<16],*s,*t;

    if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}

    return *s++;

}

inline int read()

{

    int x=0,f=1; char ch=gc();

    while(ch<'0'||'9'<ch) f=(ch^'-')?f:-1,ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x*f;

}

int const N=4e6+10;

int const N0=30;

int n=1e6+100;

int Q,t1,t2,t3;

#define Ls (p<<1)

#define Rs ((p<<1)|1)

int rt,len[2][N],val[N],tag[N];

void update(int p,int L0,int R0)

{

    int mid=L0+R0>>1;

    len[0][p]=len[0][Ls]+(len[0][Ls]==mid-L0+1)*len[0][Rs];

    len[1][p]=len[1][Ls]+(len[1][Ls]==mid-L0+1)*len[1][Rs];

}

void change(int p,int L0,int R0,int x)

{

    if(x) val[p]=(1<<N0)-1; else val[p]=0;

    tag[p]=x,len[x][p]=R0-L0+1,len[x^1][p]=0;

}

void pushdw(int p,int L0,int R0)

{

    if(tag[p]<0) return;

    int mid=L0+R0>>1;

    change(Ls,L0,mid,tag[p]),change(Rs,mid+1,R0,tag[p]);

    tag[p]=-1;

}

int L,R,cyV;

void ins1(int p,int L0,int R0,int v)

{

    if(L<=L0&&R0<=R)

    {

        val[p]+=v;

        if(val[p]>=(1<<N0)) cyV=1,val[p]&=(1<<N0)-1;

        if(val[p]<0) cyV=0,val[p]+=1<<N0;

        len[0][p]=len[1][p]=0;

        if(val[p]==0) len[0][p]=1;

        if(val[p]==(1<<N0)-1) len[1][p]=1;

        return;

    }

    pushdw(p,L0,R0);

    int mid=L0+R0>>1;

    if(L<=mid) ins1(Ls,L0,mid,v);

    if(mid<R) ins1(Rs,mid+1,R0,v);

    update(p,L0,R0);

}

void ins2(int p,int L0,int R0,int v)

{

    if(L<=L0&&R0<=R) {change(p,L0,R0,v); return;}

    pushdw(p,L0,R0);

    int mid=L0+R0>>1;

    if(L<=mid) ins2(Ls,L0,mid,v);

    if(mid<R) ins2(Rs,mid+1,R0,v);

    update(p,L0,R0);

}

int query1(int p,int L0,int R0)

{

    if(L<=L0&&R0<=R) return val[p];

    pushdw(p,L0,R0);

    int mid=L0+R0>>1;

    if(L<=mid) return query1(Ls,L0,mid);

    if(mid<R) return query1(Rs,mid+1,R0);

}

//query2返回在[L0,R0]∩[L,R]中L向后有多少个连续的v

int query2(int p,int L0,int R0,int v)

{

    if(L<=L0&&R0<=R) return len[v][p];

    pushdw(p,L0,R0);

    int mid=L0+R0>>1,r1=0,r2=0;

    if(L<=mid) r1=query2(Ls,L0,mid,v);

    if(mid<R) r2=query2(Rs,mid+1,R0,v);

    if(L<=mid) return r1+(r1==mid-L+1)*r2;

    else return r2;

}

void add(int x,int v)

{

    L=R=x,cyV=-1; ins1(rt,1,n,v);

    if(cyV>=0)

    {

        L=x+1,R=n; int len=query2(rt,1,n,cyV);

        L=x+1,R=x+len; if(L<=R) ins2(rt,1,n,cyV^1);

        L=R=x+len+1; ins1(rt,1,n,cyV?1:-1);

    }

}

int main()

{

    Q=read(); t1=read(),t2=read(),t3=read();

    memset(tag,-1,sizeof tag);

    rt=1;

    change(rt,1,n,0);

    for(int i=1;i<=Q;i++)

    {

        int opt=read();

        if(opt==1)

        {

            int a=read(),b=read();

            int b1=b/N0+1,b2=b%N0,t=1<<(N0-b2);

            int a1=a/t,a2=a%t*(1<<b2);

            add(b1,a2); add(b1+1,a1);

        }

        else

        {

            int k=read();

            int k1=k/N0+1,k2=k%N0;

            L=R=k1; printf("%d\n",(query1(rt,1,n)>>k2)&1);

        }

    }

    return 0;

}

P.S.

多谢Pickupwin大佬指点

巴特西

LibreOJ2302 - 「NOI2017」整数

Description

Solution

Code

P.S.

最新文章

热门文章