BZOJ4942 & UOJ314：[NOI2017]整数—

BZOJ4942 & UOJ314：[NOI2017]整数——题解

阅读量：6261 次

发布时间：2019-06-22

本文共 2060 字，大约阅读时间需要 6 分钟。

题面是markdown形式的所以我传不上……

UPD：18.5.11改成对参考代码的理解失误。

参考：仔细思考之后发现lazy标记可以不下传，因为区间修改都是改0/INF，单点修改就直接改就行了……

（晚上睡前突然发现这个sb问题然后太晚了只好现在改。）

暴力修改显然是不行的。

考虑让你改的是a*2^b，已经明示了想让你直接修改二进制位，于是把a用O(log)时间拆成二进制然后log次加减，期间的进位退位问题用参考博客的方法可以O(log)实现。

但问题是位数一共有3e7……显然会T的。

于是压60位，这样时间复杂度就有保证了。

（我记得以前有人批评松松松就是因为他WC出神题然后NOI出签到题……woc我怕不是送分题都做不出来我退役吧。）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=5e5+5;const int B=60;const ll INF=(1LL<
            
             >1; build(a<<1,l,mid);build(a<<1|1,mid+1,r);}void modify(int a,int l,int r,int l1,int r1,ll x){ if(r
             
              
               r1)return; if(l1<=l&&r<=r1){ mdy(a,x); return; } push(a); int mid=(l+r)>>1; modify(a<<1,l,mid,l1,r1,x); modify(a<<1|1,mid+1,r,l1,r1,x); upt(a);}ll query(int a,int l,int r,int p){ if(l==r)return val[l]; push(a); int mid=(l+r)>>1; if(p<=mid)return query(a<<1,l,mid,p); else return query(a<<1|1,mid+1,r,p);}int find(int a,int l,int r,int p,int o){ if(tag[a][!o])return -1; if(l==r)return l; push(a); int mid=(l+r)>>1,tmp; if(p<=mid&&(tmp=find(a<<1,l,mid,p,o))!=-1)return tmp; return find(a<<1|1,mid+1,r,p,o);}void add(int p,ll x){ ll tmp=query(1,0,N,p); modify(1,0,N,p,p,(tmp+x)&INF); if(tmp+x>INF){ int r=find(1,0,N,p+1,0); modify(1,0,N,r,r,val[r]+1); modify(1,0,N,p+1,r-1,0); }}void del(int p,ll x){ ll tmp=query(1,0,N,p); modify(1,0,N,p,p,(tmp-x)&INF); if(tmp-x<0){ int r=find(1,0,N,p+1,1); modify(1,0,N,r,r,val[r]-1); modify(1,0,N,p+1,r-1,INF); }}int main(){ int n=read();read(),read(),read(); build(1,0,N); for(int i=1;i<=n;i++){ int op=read(); if(op==1){ ll a=read(),b=read(); ll p=b/B,m=b%B; if(a>0){ ll x=(ll)a<
               
                >=(B-m); if(a)add(p,a); }else{ a=-a; ll x=(ll)a<
                
                 >=(B-m); if(a)del(p,a); } }else{ ll k=read(); printf("%lld\n",query(1,0,N,k/B)>>(k%B)&1); } } return 0;}