BZOJ-4942: [Noi2017]整数

[文章目录]

Description

P 博士将他的计算任务抽象为对一个整数的操作。具体来说,有一个整数 x ,一开始为 0。接下来有 n 个操作,每个操作都是以下两种类型中的一种:
• 1 a b :将 x 加上整数 a · 2b,其中 a 为一个整数,b 为一个非负整数
• 2 k :询问 x 在用二进制表示时,位权为 2k 的位的值(即这一位上的 1 代表 2k )
保证在任何时候,x ≥ 0。n<=1000000

线段树维护1和0的连续状况,优化进位复杂度,再对与叶子压位一下就行了。
话说我blog实力拖更啊

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int ui;
#define N 1001000 
#define ls (p<<1)
#define rs (p<<1|1)
const unsigned int inf=0x3fffffff;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char fl=0,ch=nc();
    while(!isdigit(ch)) fl|=(ch=='-'),ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return fl ? -re : re;
}
int n,R,flg;
ui w[N],fro[40],aft[40];
struct seg
{
    bool lz[2],is[2];
}t[N<<2];
void pushup(int p)
{
    t[p].is[0]=(t[ls].is[0]&t[rs].is[0]);
    t[p].is[1]=(t[ls].is[1]&t[rs].is[1]);
}
void pushdown(int p)
{
    if(t[p].lz[0])
    {
        t[ls].lz[0]=t[ls].is[0]=t[rs].lz[0]=t[rs].is[0]=1;
        t[ls].lz[1]=t[ls].is[1]=t[rs].lz[1]=t[rs].is[1]=0;
        t[p].lz[0]=0;
    }
    if(t[p].lz[1])
    {
        t[ls].lz[1]=t[ls].is[1]=t[rs].lz[1]=t[rs].is[1]=1;
        t[ls].lz[0]=t[ls].is[0]=t[rs].lz[0]=t[rs].is[0]=0;
        t[p].lz[1]=0;
    }
}
void make(int p,int l,int r,int x,int y)
{
    if(x<=l)
    {
        if(t[p].is[y^1])
        {
            t[p].is[y]=t[p].lz[y]=1;
            t[p].is[y^1]=t[p].lz[y^1]=0;
            return ;
        }
        if(l==r)
        {
            if(t[p].lz[0]) w[l]=0,t[p].lz[0]=0;
            if(t[p].lz[1]) w[l]=inf,t[p].lz[1]=0;
            if(y==1) w[l]--;
            else w[l]++;
            t[p].is[0]=(w[l]==0);
            t[p].is[1]=(w[l]==inf);
            flg=0;
            return ;
        }
        int mid=(l+r)>>1; pushdown(p);
        make(ls,l,mid,x,y);
        if(flg) make(rs,mid+1,r,x,y);
        pushup(p);
        return ;
    }
    int mid=(l+r)>>1; pushdown(p);
    if(x<=mid) make(ls,l,mid,x,y);
    if(flg) make(rs,mid+1,r,x,y);
    pushup(p);
}
void fix(int p,int l,int r,int x,int y)
{
    if(l==r)
    {
        if(t[p].lz[0]) w[l]=0,t[p].lz[0]=0;
        if(t[p].lz[1]) w[l]=inf,t[p].lz[1]=0;
        if(y>=0) w[l]+y<=inf ? w[l]+=y : (flg=1,make(1,1,R,l+1,0),w[l]=w[l]+y-(1<<30));
        else w[l]>=(ui)-y ? w[l]+=y : (flg=1,make(1,1,R,l+1,1),w[l]=w[l]+(1<<30)+y);
        t[p].is[0]=(w[l]==0);
        t[p].is[1]=(w[l]==inf);
        return ;
    }
    int mid=(l+r)>>1; pushdown(p);
    if(x<=mid) fix(ls,l,mid,x,y);
    else fix(rs,mid+1,r,x,y);
    pushup(p);
}
bool query(int p,int l,int r,int x)
{
    if(l==r)
    {
        if(t[p].lz[0]) w[l]=0,t[p].lz[0]=0;
        if(t[p].lz[1]) w[l]=inf,t[p].lz[1]=0;
        return (w[l]>>(x-(l-1)*30-1))&1;
    }
    int mid=(l+r)>>1; pushdown(p);
    if(x<=mid*30) return query(ls,l,mid,x);
    return query(rs,mid+1,r,x);
}
int main()
{
    n=read(); read(); read(); read();
    for(int i=1;i<=30;++i) fro[i]=fro[i-1]|(1<<(30-i));
    for(int i=1;i<=30;++i) aft[i]=aft[i-1]|(1<<(i-1));
    R=n+100; int a,b,c,x,y,z; t[1].lz[0]=1; t[1].is[0]=1;
    while(n--)
    {
        if(read()==1)
        {
            a=read(); b=read(); c= (a>0) ? 1 : -1; a= (a>0) ? a :-a;
            x=b/30; y=b-30*x;
            if(z=(a&aft[30-y])) fix(1,1,R,x+1,c*(z<<y));
            if(a-z) fix(1,1,R,x+2,c*(a>>(30-y)));
        }
        else putchar('0'+query(1,1,R,read()+1)),putchar('\n');
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注