[Noi2017]整数 BZOJ4942

时间:2022-06-12 22:47:58

分析:

30+暴力应该还是蛮水的,可以随便写写...

60+的就没那么容易了,但是应该挺裸的,往上架一颗线段树,查询连续1或0的长度,或者找到前缀中,第一个1或0,之后区间覆盖,单点查询,开bool,完全可做,手动模拟二进制加减法就可以了,O(nlog^2)

96的是被卡常了...仔细思考一下,如果开long long的话,时间复杂度是2*log(n/2)=2*(logn-log2),自己给自己找麻烦,多出来了二倍常数...(本来想优化,结果是劣化)

100的算法其实和60+的一样,只是需要压位,毕竟用线段树存0101太浪费了,同样,只是查询变成查前缀中第一个inf和0,或者连续的inf或0的长度,区间覆盖,单点查询,(第一次写这种的查询,调了一上午,其实应该重构一下的,手动划掉...),其实是懒得写区间合并了,唯一值得思考的就是判断加在哪里,这个很显然,因为是a*2^b,所以,把b/30得到p,一个加在p,加上x<<(b-p*30)另一个加在p+1,x>>(30-b+p*30),减法同上。

各种奇技淫巧,这样的情况下,就变成了O(nlog),完全OK,没问题,记得不要用long long去劣化...外加上,我没写读入输出优化都A了,证明这个题的常数没有想象的那么大,可能只是写的比较丑...

这可能是我要凉...4h做一道T1,剩下一个小时还不凉成schnappi?这种东西,考试的时候绝对不会去写正解的...O(nloglog)什么的完全OK,有时间剩余再考虑一下,否则,还是算了吧...据说T2就是暴力大测验,表示本人没看出来...目测如果不是被及时制止了,将会写一个Splay...

先不说别的了,附上代码吧...

常数没有想象的那么大,bzoj上50s,大概跑了24s左右,亲测OK,大样例什么的,还是很靠谱的,过了就AC了。(uoj上有大样例)

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 1000005
#define maxn 1000001
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int S=((1<<30)-1);
int cov[N<<2],va[N<<2],vb[N<<2],Q;
void PushUp(int rt){va[rt]=(va[rt<<1]&va[rt<<1|1]);vb[rt]=(vb[rt<<1]|vb[rt<<1|1]);}
void PushDown(int rt)
{
if(cov[rt]!=-1)
{
va[rt<<1]=va[rt<<1|1]=vb[rt<<1]=vb[rt<<1|1]=cov[rt<<1]=cov[rt<<1|1]=cov[rt];
cov[rt]=-1;
}
}
void Update_add(int x,int c,int l,int r,int rt)
{
if(l==r){va[rt]+=c;vb[rt]+=c;return ;}PushDown(rt);int m=(l+r)>>1;
if(m>=x)Update_add(x,c,lson);else Update_add(x,c,rson);PushUp(rt);
}
void Update_cov(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R){va[rt]=vb[rt]=cov[rt]=c;return ;}PushDown(rt);int m=(l+r)>>1;
if(L<=m)Update_cov(L,R,c,lson);if(m<R)Update_cov(L,R,c,rson);PushUp(rt);
}
int findzero(int x,int l,int r,int rt)
{
if(!vb[rt])return -1;if(l==r)return l;PushDown(rt);int m=(l+r)>>1;
if(x<=m){int t=findzero(x,lson);return ~t?t:findzero(x,rson);}
return findzero(x,rson);
}
int findone(int x,int l,int r,int rt)
{
if(va[rt]==S)return -1;if(l==r)return l;PushDown(rt);int m=(l+r)>>1;
if(x<=m){int t=findone(x,lson);return ~t?t:findone(x,rson);}
return findone(x,rson);
}
int query(int x,int l,int r,int rt)
{
if(l==r)return va[rt];PushDown(rt);int m=(l+r)>>1;
if(m>=x)return query(x,lson);return query(x,rson);
}
void add(int x,int c)
{
int t=query(x,0,maxn,1);
if(t+c<(1<<30))Update_add(x,c,0,maxn,1);
else
{
Update_add(x,c-(1<<30),0,maxn,1);
t=findone(x+1,0,maxn,1);
if(t!=x+1)Update_cov(x+1,t-1,0,0,maxn,1);
Update_add(t,1,0,maxn,1);
}
}
void del(int x,int c)
{
int t=query(x,0,maxn,1);
if(t-c>=0)Update_add(x,-c,0,maxn,1);
else
{
Update_add(x,(1<<30)-c,0,maxn,1);
t=findzero(x+1,0,maxn,1);
//printf("%d\n",t);
if(t!=x+1)Update_cov(x+1,t-1,S,0,maxn,1);
Update_add(t,-1,0,maxn,1);
}
}
int main()
{
scanf("%d%*d%*d%*d",&Q);
while(Q--)
{
int op,x,y,p;
scanf("%d%d",&op,&x);
if(op==1)
{
scanf("%d",&y);p=y/30;
if(x>0)
{
add(p,(x<<(y-p*30))&S);
add(p+1,(x>>(30-(y-p*30))));
}else
{
x=-x;
del(p,(x<<(y-p*30))&S);
del(p+1,(x>>(30-(y-p*30))));
}
}else
{
p=x/30;
int t=query(p,0,maxn,1);
//printf("%d\n",t);
printf("%d\n",(t>>(x-p*30))&1);
}
}
return 0;
}