社区讨论
How G?
学术版参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mkiddrdh
- 此快照首次捕获于
- 2026/01/17 21:55 上个月
- 此快照最后确认于
- 2026/01/20 23:55 4 周前
rt,我的思路:维护区间状态(0:全反,1:全正,2:部分)+区间max
关键代码:
CPPvoid pushdown(int i){
if(tr[i].lazy1){
if(tr[2*i].fm!=0){
tr[2*i].lazy1+=tr[i].lazy1;
tr[2*i].maxx+=tr[i].lazy1;
}
if(tr[2*i+1].fm!=0){
tr[2*i+1].lazy1+=tr[i].lazy1;
tr[2*i+1].maxx+=tr[i].lazy1;
}
tr[i].lazy1=0;
}
if(tr[i].lazy2){
tr[2*i].maxx=0;
tr[2*i+1].maxx=0;
tr[2*i].lazy2=tr[i].lazy2;
tr[2*i+1].lazy2=tr[i].lazy2;
if(tr[2*i].fm!=2){
tr[2*i].fm^=1;
}
if(tr[2*i+1].fm!=2){
tr[2*i+1].fm^=1;
}
tr[i].lazy2=0;
}
}
void pushup(int i){
tr[i].maxx=max(tr[2*i].maxx,tr[2*i+1].maxx);
if(tr[2*i].fm==0 && tr[2*i+1].fm==0) tr[i].fm=0;
else if(tr[2*i].fm==1 && tr[2*i+1].fm==1) tr[i].fm=1;
else tr[i].fm=2;
}
代码:
CPP#include<iostream>
#define int long long
using namespace std;
int n,q;
int t,l,r,x;
const int N=2e5+5;
struct Node{
int l,r;
int maxx;
int fm;
int lazy1,lazy2;
}tr[4*N];
void pushdown(int i){
if(tr[i].lazy1){
if(tr[2*i].fm!=0){
tr[2*i].lazy1+=tr[i].lazy1;
tr[2*i].maxx+=tr[i].lazy1;
}
if(tr[2*i+1].fm!=0){
tr[2*i+1].lazy1+=tr[i].lazy1;
tr[2*i+1].maxx+=tr[i].lazy1;
}
tr[i].lazy1=0;
}
if(tr[i].lazy2){
tr[2*i].maxx=0;
tr[2*i+1].maxx=0;
tr[2*i].lazy2=tr[i].lazy2;
tr[2*i+1].lazy2=tr[i].lazy2;
if(tr[2*i].fm!=2){
tr[2*i].fm^=1;
}
if(tr[2*i+1].fm!=2){
tr[2*i+1].fm^=1;
}
tr[i].lazy2=0;
}
}
void pushup(int i){
tr[i].maxx=max(tr[2*i].maxx,tr[2*i+1].maxx);
if(tr[2*i].fm==0 && tr[2*i+1].fm==0) tr[i].fm=0;
else if(tr[2*i].fm==1 && tr[2*i+1].fm==1) tr[i].fm=1;
else tr[i].fm=2;
}
void build(int i,int l,int r){
// cout<<1<<endl;
tr[i]={l,r};
if(l==r){
tr[i].maxx=0;
tr[i].fm=1;
return;
}
int mid=(l+r)>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
pushup(i);
}
void modify1(int i,int l,int r,int k){
if(l<=tr[i].l && tr[i].r<=r){
tr[i].maxx+=k;
tr[i].lazy1+=k;
return;
}
if(l>tr[i].r or r<tr[i].l){
return;
}
pushdown(i);
modify1(2*i,l,r,k);
modify1(2*i+1,l,r,k);
pushup(i);
}
void modify2(int i,int l,int r){
if(l<=tr[i].l && tr[i].r<=r){
tr[i].maxx=0;
if(tr[i].fm!=2){
tr[i].fm^=1;
}
tr[i].lazy2=1;
return;
}
if(l>tr[i].r or r<tr[i].l){
return;
}
pushdown(i);
modify2(2*i,l,r);
modify2(2*i+1,l,r);
pushup(i);
}
int query(int i,int l,int r){
if(l<=tr[i].l && tr[i].r<=r){
return tr[i].maxx;
}
if(l>tr[i].r or r<tr[i].l){
return 0;
}
pushdown(i);
int res=0;
res=max(res,query(2*i,l,r));
res=max(res,query(2*i+1,l,r));
return res;
}
signed main(){
cin>>n>>q;
build(1,1,n);
for(int i=1;i<=q;i++){
cin>>t;
if(t==1){
cin>>l>>r>>x;
modify1(1,l,r,x);
}
else if(t==2){
cin>>l>>r;
modify2(1,l,r);
}
else{
cin>>l>>r;
cout<<query(1,l,r)<<endl;
}
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...