题目链接
https://www.luogu.org/problemnew/show/P3822
想法
这个啊，就是线段树哇
最初的想法是每位一个节点，然后进位、退位找这一位前面第一个0或第一个1，然后把中间一段修改了即可 但是每位一个节点太浪费了，会超时，故可以压位，30位一个节点 要找每个点前面第一个0或1的话，可以记录一下每个区间里是否全0或全1，不停地维护
反正基本思路就是这样，但是代码真心挺恶心的，调了一天呢！NOI题真是毒瘤！ （初三一模前两天调这个代码，酸爽啊……qwq）
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int read(){
char ch=getchar();
int ret=0,f=1;
while(!isdigit(ch) && ch!='-') ch=getchar();
if(ch=='-') f=-1,ch=getchar();
while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
return f*ret;
}
typedef long long ll;
const int N = 1000005;
const int MAX = 1000000;
const int FULL = (1<<30)-1;
struct node{
int v,flag,lazy,id;
node *ch[2],*pa;
}pool[N*4],*root;
int cnt;
void build(node *p,int l,int r){
p->v=p->flag=0; p->lazy=-1;
if(l==r) { p->id=l; return; }
int mid=(l+r)>>1;
build(p->ch[0]=&pool[++cnt],l,mid);
build(p->ch[1]=&pool[++cnt],mid+1,r);
p->ch[0]->pa=p; p->ch[1]->pa=p;
}
void update(node *p){
if(!p->ch[0]){ //single
if(p->v==FULL) p->flag=1;
else if(p->v==0) p->flag=0;
else p->flag=-1;
}
else if(p->ch[0]->flag==p->ch[1]->flag) p->flag=p->ch[0]->flag;
else p->flag=-1;
}
void up(node *p){
if(!p) return;
update(p); up(p->pa);
}
void pushdown(node *p){
if(p->lazy==-1) return;
if(!p->ch[0]) return;
p->ch[0]->lazy=p->lazy; p->ch[0]->flag=p->lazy;
if(!p->ch[0]->ch[0]) p->ch[0]->v=p->lazy ? FULL : 0;
p->ch[1]->lazy=p->lazy; p->ch[1]->flag=p->lazy;
if(!p->ch[1]->ch[0]) p->ch[1]->v=p->lazy ? FULL : 0;
p->lazy=-1;
}
node *get_node(node *p,int l,int r,int c){
if(l==r) return p;
pushdown(p);
int mid=(l+r)>>1;
if(c<=mid) return get_node(p->ch[0],l,mid,c);
return get_node(p->ch[1],mid+1,r,c);
}
void fix(node *p,int l,int r,int c,int f){
if(l==r){
if(f==0) p->v++;
else p->v--;
update(p);
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(c<=mid) fix(p->ch[0],l,mid,c,f);
else fix(p->ch[1],mid+1,r,c,f);
update(p);
}
void change(node *p,int l,int r,int L,int R,int f){
if(l==L && r==R){
p->lazy=p->flag=f;
if(l==r) p->v= f ? FULL : 0;
return;
}
pushdown(p);
int mid=(l+r)>>1;
if(R<=mid) change(p->ch[0],l,mid,L,R,f);
else if(L>mid) change(p->ch[1],mid+1,r,L,R,f);
else{
change(p->ch[0],l,mid,L,mid,f);
change(p->ch[1],mid+1,r,mid+1,R,f);
}
update(p);
}
int find(node *p,int c,int f){ //f=1: 011111 f=0:100000
if(p->flag!=f){
if(!p->ch[0]) return p->id;
if(c==-1){
pushdown(p);
if(p->ch[0]->flag!=f) return find(p->ch[0],-1,f);
else return find(p->ch[1],-1,f);
}
if(c==0 && p->ch[1] && p->ch[1]->flag!=f) return find(p->ch[1],-1,f);
return find(p->pa,p==p->pa->ch[1],f);
}
return find(p->pa,p==p->pa->ch[1],f);
}
void add(int a,int x){
int ty=a/30+1,y=x*(1<<(a-(ty-1)*30));
node *p=get_node(root,1,MAX,ty);
if(p->v+y<=FULL) { p->v+=y; up(p); return; }
p->v=p->v+y-FULL-1; up(p);
node *q=get_node(root,1,MAX,ty+1);
int v=find(q,0,1);
if(v==ty+1) fix(root,1,MAX,ty+1,0);
else change(root,1,MAX,ty+1,v-1,0),fix(root,1,MAX,v,0);
}
void del(int a,int x){
int ty=a/30+1,y=x*(1<<(a-(ty-1)*30));
node *p=get_node(root,1,MAX,ty);
if(p->v-y>=0) { p->v-=y; up(p); return; }
p->v=p->v-y+FULL+1; up(p);
node *q=get_node(root,1,MAX,ty+1);
int v=find(q,0,0);
if(v==ty+1) fix(root,1,MAX,ty+1,1);
else change(root,1,MAX,ty+1,v-1,1),fix(root,1,MAX,v,1);
}
void Add(int a,int x){
int ty=a/30+1;
ll y=x*(1ll<<(a-(ty-1)*30));
if(y<=1ll*FULL) add(a,x);
else add((ty-1)*30,(int)(y%(FULL+1))),add(ty*30,(int)(y/(FULL+1)));
}
void Del(int a,int x){
int ty=a/30+1;
ll y=x*(1ll<<(a-(ty-1)*30));
if(y<=1ll*FULL) del(a,x);
else del((ty-1)*30,(int)(y%(FULL+1))),del(ty*30,(int)(y/(FULL+1)));
}
int main()
{
int n,opt,a,b;
n=read();read();read();read();
root=&pool[++cnt];
build(root,1,MAX);
for(int i=0;i<n;i++){
opt=read();
if(opt==1){
a=read(); b=read();
if(a>0) Add(b,a);
else if(a<0) Del(b,-a);
}
else{
a=read();
node *p=get_node(root,1,MAX,a/30+1);
printf("%d\n",(p->v&(1<<(a-(a/30)*30)))!=0 ? 1 : 0);
}
}
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/9031793.html
相关资源：数据结构—成绩单生成器
