社区讨论

求助

P10120『STA - R4』冰红茶参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m1vok9se
此快照首次捕获于
2024/10/05 12:55
去年
此快照最后确认于
2025/11/04 18:01
4 个月前
查看原帖
除了SubtaskSubtask #1AC,其他点均TLE
CPP
#include <bits/stdc++.h>
#define int long long
#define lson id<<1,l,mid
#define rson id<<1|1,mid+1,r
#define ls id<<1
#define rs id<<1|1
using namespace std;

const int MAXN=3e5;
const int MAXM=3e6;
int n,m;
struct st{
	int l,r;
	int mx;
	int cover,add;
}tree[MAXN<<2][3];
//  0 -> 热带风味冰红茶
//  1 -> 原味冰红茶
//  2 -> 存活人数 

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline void up(int id,int x){
	tree[id][x].mx=max(tree[ls][x].mx,tree[rs][x].mx);
}

inline void up_people(int id){
	tree[id][2].mx=tree[ls][2].mx+tree[rs][2].mx;
}

inline void down_cover(int id,int x){
//	cout<<"\n down_cover:"<<id<<endl;
	tree[ls][x].mx=tree[ls][x].add=0;
	tree[rs][x].mx=tree[rs][x].add=0;
	tree[ls][x].cover=tree[rs][x].cover=1;
	tree[id][x].cover=0;
}

inline void down_add(int id,int x){
	if(tree[id][x].cover){
//		cout<<"\n down_add:"<<id<<' '<<x<<' '<<tree[id][x].cover<<endl;
		down_cover(id,x); 
	}
	tree[ls][x].mx+=tree[id][x].add;
	tree[rs][x].mx+=tree[id][x].add;
	tree[ls][x].add+=tree[id][x].add;
	tree[rs][x].add+=tree[id][x].add;
	tree[id][x].add=0;
}

inline void build(int id,int l,int r){
	tree[id][0].l=tree[id][1].l=tree[id][2].l=l;
	tree[id][0].r=tree[id][1].r=tree[id][2].l=r;
	tree[id][0].cover=tree[id][1].cover=tree[id][2].cover=0;
	if(l==r){
		tree[id][2].mx=1;
		return;
	}
	int mid=l+r>>1;
	build(lson);build(rson);
	up(id,1);up(id,0);up_people(id);
}

inline void update_add(int id,int l,int r,int L,int R,int w,int x){
	if(l>R||L>r||tree[id][2].mx==0) return;
	if(L<=l&&r<=R){
		tree[id][x].add+=w;
		tree[id][x].mx+=w;
		return; 
	}
	down_add(id,x);
	int mid=l+r>>1;
	if(L<=mid) update_add(lson,L,R,w,x);
	if(R>mid) update_add(rson,L,R,w,x);
	up(id,x);
}

inline void update_cover(int id,int l,int r,int L,int R,int x){
	if(l>R||L>r||tree[id][2].mx==0) return;
	if(L<=l&&r<=R){
//		cout<<"\n update_cover:"<<id<<' '<<l<<' '<<r<<endl;
		tree[id][x].cover=1;
		tree[id][x].mx=tree[id][x].add=0;
		return; 
	}
	down_add(id,x);
	int mid=l+r>>1;
	if(L<=mid) update_cover(lson,L,R,x);
	if(R>mid) update_cover(rson,L,R,x);
	up(id,x);
}

inline void kill(int id,int l,int r,int L,int R,int k){
	if(L>r||tree[id][2].mx==0) return;
	if(tree[id][1].mx<k&&tree[id][0].mx<k) return;
	if(L<=l&&r<=R&&l==r){
		tree[id][2].mx=tree[id][1].mx=tree[id][0].mx=0;
		return; 
	}
	down_add(id,1);down_add(id,2);
	int mid=l+r>>1;
	if(L<=mid) kill(lson,L,R,k);
	if(R>mid) kill(rson,L,R,k);
	up_people(id);
	up(id,1);up(id,0);
}

inline void cs(int id,int l,int r,int x){
	if(l==r){
		return ;
	}
	down_add(id,x);
	int mid=l+r>>1;
	cs(lson,x);cs(rson,x);
	up(id,x);
}

signed main(){
	n=read();m=read();
	build(1,1,n);
	while(m--){
		int opx,l,r,w;
		opx=read();
		if(opx==1){
			l=read();r=read();w=read();
			//原味冰红茶 
//			cout<<1<<' '<<l-1<<"         "<<l<<' '<<r<<"          "<<r+1<<' '<<n<<endl;
			if(1<=l-1) update_cover(1,1,n,1,l-1,1);
			update_add(1,1,n,l,r,w,1);
			if(r+1<=n) update_cover(1,1,n,r+1,n,1);
			
			//热带风味冰红茶
			if(1<=l-1) update_add(1,1,n,1,l-1,w,0);
			update_cover(1,1,n,l,r,0);
			if(r+1<=n) update_add(1,1,n,r+1,n,w,0);
		}
		if(opx==2){
			l=read();r=read();w=read();
			kill(1,1,n,l,r,w);
		}
		if(opx==3){
			printf("%d\n",tree[1][2].mx); 
		}
//		cout<<"\n热带风味冰红茶:\n";
		cs(1,1,n,0);
//		cout<<endl;
//		cout<<"\n原味冰红茶:\n";
		cs(1,1,n,1);
//		cout<<endl;
//		cout<<"\n存活人数:\n";cs(1,1,n,2);
	}
}

回复

0 条回复,欢迎继续交流。

正在加载回复...