P2042 [NOI2005]维护数列

P2042 [NOI2005]维护数列

思路

超级恶心的pushdown
昏天黑地的调
让我想起了我那前几个月的线段树2

错误

这恶心的一道题终于过了
太多错误，简直说不过来
pushup
pushdown
主要就是这俩不太清晰，乱pushdown
其他的写的还没啥毛病(能看出来)

代码

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=5e5+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
int read() {int x=0,f=1;char s=getchar();for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';return x*f;
}
int n,m,rt,cnt;
int init[maxn];
stack<int> q;//回收废弃数组
struct node 
{int ch[2],val,pri,size;int sum,ma,lma,rma;int lazy_fanzhuan,lazy_chenzhen;void clear() {ch[1]=ch[2]=val=pri=size=sum=lazy_fanzhuan=lma=rma=0;ma=-inf;lazy_chenzhen=inf;}void iit(int x) {ma=sum=val=init[x];lma=rma=max(init[x],0);size=1;pri=x;}
}e[maxn];
void pushup(int a) 
{int ls=e[a].ch[0],rs=e[a].ch[1];//sume[a].sum=e[ls].sum+e[rs].sum+e[a].val;//sizee[a].size=e[ls].size+e[rs].size+1;//mae[a].ma=max(max(e[ls].ma,e[rs].ma),e[ls].rma+e[a].val+e[rs].lma);//lmae[a].lma=max(e[ls].lma,e[ls].sum+e[a].val+e[rs].lma);//rmae[a].rma=max(e[rs].rma,e[rs].sum+e[a].val+e[ls].rma);}
void down_1(int a,int ad) 
{//@修改自身e[a].lazy_chenzhen=ad;e[a].val=e[a].lazy_chenzhen;e[a].sum=e[a].size*e[a].val;e[a].ma=max(e[a].sum , e[a].val);e[a].lma=e[a].rma=max(e[a].sum , 0);    
}
void down_2(int a) 
{//sum和ma是不变的 swap(e[a].lma,e[a].rma);swap(e[a].ch[0],e[a].ch[1]);e[a].lazy_fanzhuan^=1;
}
void pushdown(int a) 
{if(!a) return;int ls=e[a].ch[0],rs=e[a].ch[1];if(e[a].lazy_fanzhuan) {//sum和ma是不变的 if(ls) down_2(ls);if(rs) down_2(rs);}if(e[a].lazy_chenzhen!=inf) {if(ls) down_1(ls,e[a].lazy_chenzhen);if(rs) down_1(rs,e[a].lazy_chenzhen);}e[a].lazy_chenzhen=inf;e[a].lazy_fanzhuan=0;
}
int merge(int x,int y) 
{pushdown(x),pushdown(y);if(!x || !y) return x+y;if(e[x].pri<e[y].pri) {e[x].ch[1]=merge(e[x].ch[1],y);pushup(x);return x;} else {e[y].ch[0]=merge(x,e[y].ch[0]);pushup(y);return y;}
}
void split(int now,int k,int &x,int &y) 
{if(!now) x=y=0,e[now].clear();else {pushdown(now);if(e[e[now].ch[0]].size+1<=k) x=now,split(e[now].ch[1],k-e[e[now].ch[0]].size-1,e[x].ch[1],y);elsey=now,split(e[now].ch[0],k,x,e[y].ch[0]);pushup(now);}
}
int GET() 
{if(!q.empty()) {int tmp&#p();q.pop();return tmp;} else return ++cnt;
}
int build(int l,int r) 
{if(l>r) return 0;int mid=(l+r)>>1,p=GET();e[p].clear(); e[p].iit(mid);e[p].ch[0]=build(l,mid-1);e[p].ch[1]=build(mid+1,r);pushup(p);return p;
}
void dfs(int now) 
{if(!now) return;dfs(e[now].ch[0]);q.push(now);dfs(e[now].ch[1]);
}
int main() 
{
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);n=read(),m=read();FOR(i,1,n) init[i]=read();rt=build(1,n);FOR(i,1,m) {string s;cin>>s;if(s=="INSERT") { // 插入 int id=read(),gs=read(),x,y,z;FOR(j,1,gs) init[j]=read();y=build(1,gs);split(rt,id,x,z);rt=merge(merge(x,y),z);} else if(s=="DELETE") {int id=read()-1,gs=read(),x,y,z;split(rt,id,x,z);split(z,gs,y,z);dfs(y);rt=merge(x,z);} else if(s=="MAKE-SAME") {int id=read()-1,gs=read(),ad=read(),x,y,z;split(rt,id,x,z);split(z,gs,y,z);down_1(y,ad);rt=merge(merge(x,y),z);} else if(s=="REVERSE") {int id=read()-1,gs=read(),x,y,z;split(rt,id,x,z);split(z,gs,y,z);down_2(y);rt=merge(merge(x,y),z);} elseif(s=="GET-SUM") {int id=read()-1,gs=read(),x,y,z;split(rt,id,x,z);split(z,gs,y,z);cout<<e[y].sum<<"n";rt=merge(merge(x,y),z);} elseif(s=="MAX-SUM") { //询问 cout<<e[rt].ma<<"n";}}return 0;
} 

转载于:.html