[BZOJ4942][Noi2017]整数 线段树+压位

用线段树来模拟加减法过程,维护连续一段中是否全为0/1。

因为数字很大,我们60位压一位来处理。

 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define maxn 505050
#define base 60
#define ll long long
using namespace std;
inline ll read() {
ll x=,f=;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
ll n,m,S=(1ll<<)-;
struct Seg {
int al[];
ll tag,val;
}t[maxn*];
void put(int o,ll tmp) {
if(tmp!=-) t[o].val=tmp;
if(tmp==) {t[o].al[]=;t[o].al[]=;t[o].tag=tmp;}
else if(tmp==S) {t[o].al[]=;t[o].al[]=;t[o].tag=tmp;}
else {t[o].al[]=t[o].al[]=;t[o].tag=tmp;}
}
void pushdown(int o) {
int ls=o<<,rs=ls+;
if(t[o].tag!=-) {put(ls,t[o].tag);put(rs,t[o].tag);t[o].tag=-;}
}
void pushup(int o) {
int ls=o<<,rs=ls+;
t[o].al[]=t[ls].al[]&t[rs].al[];
t[o].al[]=t[ls].al[]&t[rs].al[];
}
void build(int l,int r,int o) {
t[o].tag=-,t[o].al[]=;t[o].al[]=;t[o].val=;
if(l==r) return;
int mid=l+r>>,ls=o<<,rs=ls+;
build(l,mid,ls);build(mid+,r,rs);
}
ll query(int l,int r,int o,int x) {
if(l==r) return t[o].val;
pushdown(o);
int mid=l+r>>,ls=o<<,rs=ls+;
if(x<=mid) return query(l,mid,ls,x);
else return query(mid+,r,rs,x);
pushup(o);
}
void change(int l,int r,int o,int L,int R,ll tmp) {
if(L<=l&&R>=r) {put(o,tmp);return;}
pushdown(o);
int mid=l+r>>,ls=o<<,rs=ls+;
if(L<=mid) change(l,mid,ls,L,R,tmp);
if(R>mid) change(mid+,r,rs,L,R,tmp);
pushup(o);
}
int find(int l,int r,int o,int pos,int k) {
if(t[o].al[!k]) return -;
if(l==r) return l;
int mid=l+r>>,ls=o<<,rs=ls+;
pushdown(o);
if(pos<=mid) {
ll tmp=find(l,mid,ls,pos,k);
if(tmp!=-) return tmp;
}
return find(mid+,r,rs,pos,k);
pushup(o);
}
void add(int pos,ll ad) {
ll tmp=query(,n,,pos);change(,n,,pos,pos,(tmp+ad)&S);
if(tmp+ad>S) {
int l=find(,n,,pos+,);
tmp=query(,n,,l);
change(,n,,l,l,tmp+);
if(pos+<=l-) change(,n,,pos+,l-,);
}
}
void del(int pos,ll ad) {
ll tmp=query(,n,,pos);
if(tmp-ad<) change(,n,,pos,pos,(S+tmp-ad+)&S);
else change(,n,,pos,pos,(tmp-ad)&S);
if(tmp-ad<) {
int l=find(,n,,pos+,);
tmp=query(,n,,l);
change(,n,,l,l,tmp-);
if(pos+<=l-) change(,n,,pos+,l-,S);
}
}
int main() {
m=read();read();read();read();n=;build(,n,);
for(int i=;i<=m;i++) {
int tp=read();
if(tp==) {
ll a=read(),b=read();
if(a>) {
ll p=b/base,q=b%base;
ll x=(a<<q)&S;add(p,x);
a>>=base-q;add(p+,a);
}
else {
a=-a;ll p=b/base,q=b%base;
ll x=(a<<q)&S;del(p,x);
a>>=base-q;del(p+,a);
}
}
else {
ll a=read();
printf("%lld\n",(query(,n,,a/base)>>(a%base))&);
}
}
}
/*
10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15
*/
上一篇:【BZOJ4942】[Noi2017]整数 线段树+DFS(卡过)


下一篇:哥的第一个Jquery程序