社区讨论

90pts求调

rroumeideclown
P2042[NOI2005] 维护数列参与者 3已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mhjoipch
此快照首次捕获于
2025/11/04 05:55
4 个月前
此快照最后确认于
2025/11/04 05:55
4 个月前
查看原帖
WA on #3 玄关
CPP
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
namespace exstd{
    template<typename T>inline const T min(const T&x){return x;}
    template<typename T>inline const T max(const T&x){return x;}
    template<typename T>inline const T min(const T&x,const T&y){return x<y?x:y;}
    template<typename T>inline const T max(const T&x,const T&y){return x<y?y:x;}
    template<typename T,typename ...R>inline const T min(const T&first,R...rest){return min<T>(first,min(rest...));}
    template<typename T,typename ...R>inline const T max(const T&first,R...rest){return max<T>(first,max(rest...));}
};
#define fi first
#define se second
constexpr int INF=0x3f3f3f3f;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N=5e5+5;
struct node {
	int ls,rs,pri,val,siz,sum,lsum,rsum,msum,chg;
	bool rev;
} tr[N];
int root,tot,arr[N];
stack<int> rec;
int NewNode(int val) {
	int u;
	if(!rec.empty()) {
		u=rec.top();
		rec.pop();
	}
	else u=++tot;
	tr[u].ls=tr[u].rs=0;
	tr[u].pri=rnd();
	tr[u].val=tr[u].sum=val;
	tr[u].lsum=tr[u].rsum=tr[u].msum=max(0,val);
	tr[u].siz=1;
	tr[u].chg=INF;
	tr[u].rev=0;
	return u;
}
void Recycle(int u) {
	if(!u) return;
	Recycle(tr[u].ls);
	Recycle(tr[u].rs);
	rec.push(u);
}
void Pushup(int u) {
	tr[u].siz=tr[tr[u].ls].siz+tr[tr[u].rs].siz+1;
	tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum+tr[u].val;
	// tr[u].msum=max({tr[u].val,(tr[u].ls?tr[tr[u].ls].msum:-INF),(tr[u].rs?tr[tr[u].rs].msum:-INF),(tr[u].ls?tr[tr[u].ls].rsum+tr[u].val:-INF),(tr[u].rs?tr[u].val+tr[tr[u].rs].lsum:-INF),(tr[u].ls&&tr[u].rs?tr[tr[u].ls].rsum+tr[u].val+tr[tr[u].rs].lsum:-INF)});
	// tr[u].lsum=max({tr[u].ls?tr[tr[u].ls].lsum:-INF,tr[u].ls?tr[tr[u].ls].sum+tr[u].val:-INF,tr[u].ls&&tr[u].rs?tr[tr[u].ls].sum+tr[u].val+tr[tr[u].rs].lsum:-INF});
	// tr[u].rsum=max({tr[u].rs?tr[tr[u].rs].rsum:-INF,tr[u].rs?tr[tr[u].rs].sum+tr[u].val:-INF,tr[u].ls&&tr[u].rs?tr[tr[u].rs].sum+tr[u].val+tr[tr[u].ls].rsum:-INF});
	if(tr[u].ls){
		if(tr[u].rs){
			tr[u].msum=exstd::max(tr[tr[u].ls].msum,tr[tr[u].rs].msum,tr[tr[u].ls].rsum+tr[u].val,tr[tr[u].rs].lsum+tr[u].val,tr[tr[u].ls].rsum+tr[tr[u].rs].lsum+tr[u].val,tr[u].val);
			tr[u].lsum=exstd::max(tr[tr[u].ls].lsum,tr[tr[u].ls].sum+tr[u].val,tr[tr[u].ls].sum+tr[u].val+tr[tr[u].rs].lsum);
			tr[u].rsum=exstd::max(tr[tr[u].ls].rsum+tr[u].val+tr[tr[u].rs].sum,tr[u].val+tr[tr[u].rs].sum,tr[tr[u].rs].rsum);
		}
		else{
			tr[u].msum=exstd::max(tr[tr[u].ls].msum,tr[tr[u].ls].rsum+tr[u].val,tr[u].val);
			tr[u].lsum=exstd::max(tr[tr[u].ls].lsum,tr[tr[u].ls].sum+tr[u].val);
			tr[u].rsum=exstd::max(tr[tr[u].ls].rsum+tr[u].val,tr[u].val);
		}
	}
	else if(tr[u].rs){
		tr[u].msum=exstd::max(tr[tr[u].rs].msum,tr[tr[u].rs].lsum+tr[u].val,tr[u].val);
		tr[u].rsum=exstd::max(tr[tr[u].rs].rsum,tr[tr[u].rs].sum+tr[u].val);
		tr[u].lsum=exstd::max(tr[tr[u].rs].lsum+tr[u].val,tr[u].val);
	}
	else tr[u].msum=tr[u].lsum=tr[u].rsum=tr[u].val;
}
void Pushdown(int u) {
	if(tr[u].chg!=INF) {
		if(tr[u].ls) {
			tr[tr[u].ls].val=tr[tr[u].ls].chg=tr[u].chg;
			tr[tr[u].ls].sum=tr[u].chg*tr[tr[u].ls].siz;
			tr[tr[u].ls].lsum=tr[tr[u].ls].rsum=tr[tr[u].ls].msum=max(tr[u].chg,tr[u].chg*tr[tr[u].ls].siz);
		}
		if(tr[u].rs) {
			tr[tr[u].rs].val=tr[tr[u].rs].chg=tr[u].chg;
			tr[tr[u].rs].sum=tr[u].chg*tr[tr[u].rs].siz;
			tr[tr[u].rs].lsum=tr[tr[u].rs].rsum=tr[tr[u].rs].msum=max(tr[u].chg,tr[u].chg*tr[tr[u].rs].siz);
		}
		tr[u].rev=0,tr[u].chg=INF;
	}
	else if(tr[u].rev) {
		swap(tr[u].ls,tr[u].rs);
		tr[tr[u].ls].rev^=1,tr[tr[u].rs].rev^=1;
		swap(tr[tr[u].ls].lsum,tr[tr[u].ls].rsum);
		swap(tr[tr[u].rs].lsum,tr[tr[u].rs].rsum);
		tr[u].rev=0;
	}
}
void Split(int u,int rk,int &l,int &r) {
	if(!u) {
		l=r=0;
		return;
	}
	Pushdown(u);
	if(rk<=tr[tr[u].ls].siz) {
		r=u;
		Split(tr[u].ls,rk,l,tr[u].ls);
		Pushup(r);
	}
	else {
		l=u;
		Split(tr[u].rs,rk-tr[tr[u].ls].siz-1,tr[u].rs,r);
		Pushup(l);
	}
}
int Merge(int u,int v) {
	if(!u||!v) return u+v;
	if(tr[u].pri<tr[v].pri) {
		Pushdown(u);
		tr[u].rs=Merge(tr[u].rs,v);
		Pushup(u);
		return u;
	}
	else {
		Pushdown(v);
		tr[v].ls=Merge(u,tr[v].ls);
		Pushup(v);
		return v;
	}
}
int Build(int *add,int len) {
	if(len==1) return NewNode(add[0]);
	return Merge(Build(add,len/2),Build(add+len/2,len-len/2));
}
void Insert(int pos,int *add,int len) {
	int l,r;
	Split(root,pos,l,r);
	root=Merge(Merge(l,Build(add,len)),r);
}
void Delete(int pl,int pr) {
	int l,mid,r;
	Split(root,pr,l,r);
	Split(l,pl-1,l,mid);
	Recycle(mid);
	root=Merge(l,r);
}
void Modify(int pl,int pr,int val) {
	int l,mid,r;
	Split(root,pr,l,r);
	Split(l,pl-1,l,mid);
	tr[mid].val=tr[mid].chg=val;
	tr[mid].sum=tr[mid].siz*val;
	tr[mid].lsum=tr[mid].rsum=tr[mid].msum=max(val,tr[mid].siz*val);
	tr[mid].rev=0;
	root=Merge(Merge(l,mid),r);
}
void Reverse(int pl,int pr) {
	int l,mid,r;
	Split(root,pr,l,r);
	Split(l,pl-1,l,mid);
	tr[mid].rev^=1;
	swap(tr[mid].lsum,tr[mid].rsum);
	root=Merge(Merge(l,mid),r);
}
int QuerySum(int pl,int pr) {
	int l,mid,r;
	Split(root,pr,l,r);
	Split(l,pl-1,l,mid);
	int res=tr[mid].sum;
	root=Merge(Merge(l,mid),r);
	return res;
}
int QueryMaxSubSum() {
	return tr[root].msum;
}
void MidPrint(int u) { // for debug
	if(!u) return;
	Pushdown(u);
	MidPrint(tr[u].ls);
	cout<<tr[u].val<<" ";
	MidPrint(tr[u].rs);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=0;i<n;i++) cin>>arr[i];
	Insert(root,arr,n);
	// cout<<"DEBUG: ";MidPrint(root);cout<<"\n";
	while(m--) {
		string op;cin>>op;
		if(op=="INSERT") {
			int pos,tot;cin>>pos>>tot;
			for(int i=0;i<tot;i++) cin>>arr[i];
			Insert(pos,arr,tot);
		}
		else if(op=="DELETE") {
			int pos,tot;cin>>pos>>tot;
			Delete(pos,pos+tot-1);
		}
		else if(op=="MAKE-SAME") {
			int pos,tot,c;cin>>pos>>tot>>c;
			Modify(pos,pos+tot-1,c);
		}
		else if(op=="REVERSE") {
			int pos,tot;cin>>pos>>tot;
			Reverse(pos,pos+tot-1);
		}
		else if(op=="GET-SUM") {
			int pos,tot;cin>>pos>>tot;
			cout<<QuerySum(pos,pos+tot-1)<<"\n";
		}
		else cout<<QueryMaxSubSum()<<"\n";
		// cout<<"DEBUG: ";MidPrint(root);cout<<"\n";
	}
	return 0;
}
/*
9 8 
2 -6 3 5 1 -5 -3 6 3 
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
*/

回复

共 3 条回复，欢迎继续交流。

正在加载回复...