社区讨论
求助
P10120『STA - R4』冰红茶参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m1vlnrmu
- 此快照首次捕获于
- 2024/10/05 11:33 去年
- 此快照最后确认于
- 2025/11/04 18:01 4 个月前
除了 #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 条回复,欢迎继续交流。
正在加载回复...