[文章目录]
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;
}