线段树求调
查看原帖
线段树求调
752094
MornHus楼主2023/2/27 13:04
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;
	int f=-1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x;
}
int ans;
int n,m,opt;
struct XDS{
	int len,maxl,maxr,maxv;
}t[500005<<2];
int lazy[500005<<2];
void pushup(int x){
	if(t[x<<1].len==t[x<<1].maxv){
		t[x].maxl=t[x<<1].len+t[x<<1|1].maxl;
	}else{
		t[x].maxl=t[x<<1].maxl;
	}
	if(t[x<<1|1].len==t[x<<1|1].maxv){
		t[x].maxr=t[x<<1|1].len+t[x<<1].maxr;
	}else{
		t[x].maxr=t[x<<1|1].maxr;
	}
	t[x].maxv=max(max(t[x<<1].maxv,t[x<<1|1].maxv),t[x<<1].maxr+t[x<<1|1].maxl);
}
void build(int x,int l,int r){
	lazy[x]=0;
	t[x].maxl=t[x].maxr=t[x].maxv=t[x].len=(r-l+1);
	if(l==r)return;
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void pushdown(int x,int l,int r){
	if(lazy[x]==1){
		lazy[x<<1]=lazy[x<<1|1]=1;
		t[x<<1].maxl=t[x<<1].maxr=t[x<<1].maxv=0;
		t[x<<1|1].maxl=t[x<<1|1].maxr=t[x<<1|1].maxv=0;
	}
	if(lazy[x]==2){
		lazy[x<<1]=lazy[x<<1|1]=2;
		t[x<<1].maxl=t[x<<1].maxr=t[x<<1].maxv=t[x<<1].len;
		t[x<<1|1].maxl=t[x<<1|1].maxr=t[x<<1|1].maxv=t[x<<1|1].len;
	} 
	lazy[x]=0;
}
void update(int x,int l,int r,int L,int R,int tag){
	pushdown(x,l,r);
	if(L<=l&&r<=R){
		if(tag==1){
			t[x].maxl=t[x].maxr=t[x].maxv=0;
		}else{
			t[x].maxl=t[x].maxr=t[x].maxv=t[x].len;
		}
		lazy[x]=tag;
	}else{
		int mid=(l+r)>>1;
		if(L<=mid)update(x<<1,l,mid,L,R,tag);
		if(R>mid)update(x<<1|1,mid+1,r,L,R,tag);
		pushup(x);
	}
}
int query(int x,int l,int r,int L){
	pushdown(x,l,r);
	if(l==r){
		return l;
	}else{
		int mid=(l+r)>>1;
		if(t[x<<1].maxv>=L)return query(x<<1,l,mid,L);
		else if(t[x<<1].maxr+t[x<<1|1].maxl>=L)return mid-t[x<<1].maxr+1;
		else return query(x<<1|1,mid+1,r,L);
	}
}
int main(){
	n=read();
	m=read();
	build(1,1,n);
	char c; 
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>c;
		if(c=='A'){
			x=read();
			if(t[1].maxv<x){
				ans++;
			}else{
				int left=query(1,1,n,x);
				update(1,1,n,left,left+x-1,1);
			}
		}else{
			x=read();
			y=read();
			update(1,1,n,x,x+y-1,2);
		}
	}
	cout<<ans;
	return 0;
}
2023/2/27 13:04
加载中...