fhq 80pts 求助
- 板块P2042 [NOI2005] 维护数列
- 楼主Z_AuTwT
- 当前回复1
- 已保存回复1
- 发布时间2025/1/16 12:35
- 上次更新2025/1/16 15:57:22
查看原帖
被骇客银狼阻止的越权访问保存失败
fhq 80pts 求助
#include<bits/stdc++.h>
#define LL true
#define FST true
#define DEBUG false
#define FIO false
#define STD true
#define IOS true
#define unGet false
#define I128 false
#if STD
using namespace std;
#endif
#if LL
#define int long long
#endif
#if I128
#define int __int128
#endif
#if FST
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() {
register int x=0,f=1;
register char ch=getchar();
while(!(ch>='0'&&ch<='9'))
ch=getchar();
while(ch>='0'&&ch<='9')
x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline void write(register int x){
if(x>9)
write(x/10);
putchar((x%10)^48);
}
struct Flush{
~Flush(){flush();}
}_;
#if unGet
#undef getchar
#endif
#else
inline int read(){
int x;
cin>>x;
return x;
}
inline void write(register long long x){
cout<<x;
}
#endif
#if FIO
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#endif
bool st;
const int N=6000100;
int stk[N],tot,Arr[N];
struct Tree{
int X,Y,Z,cnt,ROOT,Val[N],Key[N],L[N],R[N],Size[N],Sum[N],tp_val[N],Max[N],lMax[N],rMax[N];
bool re[N],tp[N];
void update(int x){
Size[x]=Size[L[x]]+Size[R[x]]+1;
Sum[x]=Sum[L[x]]+Sum[R[x]]+Val[x];
Max[x]=max({Val[x],(L[x]?Max[L[x]]:-1000000000000000000LL),(R[x]?Max[R[x]]:-10000000000000000LL),rMax[L[x]]+lMax[R[x]]+Val[x]});
lMax[x]=max({lMax[L[x]],0LL,Sum[L[x]]+Val[x]+lMax[R[x]]});
rMax[x]=max({rMax[R[x]],0LL,Sum[R[x]]+Val[x]+rMax[L[x]]});
}
void push_down(int x){
if(re[x]){
swap(L[x],R[x]);
swap(lMax[x],rMax[x]);
re[L[x]]=(re[L[x]]==1?0:1);
re[R[x]]=(re[R[x]]==1?0:1);
re[x]=false;
}
if(re[L[x]]&&L[x]){
swap(L[L[x]],R[L[x]]);
swap(lMax[L[x]],rMax[L[x]]);
re[L[L[x]]]=(re[L[L[x]]]==1?0:1);
re[R[L[x]]]=(re[R[L[x]]]==1?0:1);
re[L[x]]=false;
}
if(re[R[x]]&&R[x]){
swap(L[R[x]],R[R[x]]);
swap(lMax[R[x]],rMax[R[x]]);
re[L[R[x]]]=(re[L[R[x]]]==1?0:1);
re[R[R[x]]]=(re[R[R[x]]]==1?0:1);
re[R[x]]=false;
}
if(tp[x]){
Val[x]=tp_val[x],Sum[x]=tp_val[x]*Size[x],Max[x]=max(tp_val[x],tp_val[x]*Size[x]),lMax[x]=rMax[x]=max(0LL,tp_val[x]*Size[x]);
tp_val[L[x]]=tp_val[R[x]]=tp_val[x];
tp[L[x]]=tp[R[x]]=true;
tp[x]=false;
tp_val[x]=0;
}
if(tp[L[x]]&&L[x]){
Val[L[x]]=tp_val[L[x]],Sum[L[x]]=tp_val[L[x]]*Size[L[x]],Max[L[x]]=max(tp_val[L[x]],tp_val[L[x]]*Size[L[x]]),lMax[L[x]]=rMax[L[x]]=max(0LL,tp_val[L[x]]*Size[L[x]]);
tp_val[L[L[x]]]=tp_val[R[L[x]]]=tp_val[L[x]];
tp[L[L[x]]]=tp[R[L[x]]]=true;
tp[L[x]]=false;
tp_val[L[x]]=0;
}
if(tp[R[x]]&&R[x]){
Val[R[x]]=tp_val[R[x]],Sum[R[x]]=tp_val[R[x]]*Size[R[x]],Max[R[x]]=max(tp_val[R[x]],tp_val[R[x]]*Size[R[x]]),lMax[R[x]]=rMax[R[x]]=max(0LL,tp_val[R[x]]*Size[R[x]]);
tp_val[L[R[x]]]=tp_val[R[R[x]]]=tp_val[R[x]];
tp[L[R[x]]]=tp[R[R[x]]]=true;
tp[R[x]]=false;
tp_val[R[x]]=0;
}
}
void split(int Root,int value,int &x,int &y){
if(!Root){
x=y=0;
return;
}
push_down(Root);
if(Size[L[Root]]+1<=value){
value-=Size[L[Root]]+1;
x=Root;
split(R[x],value,R[x],y);
}else{
y=Root;
split(L[y],value,x,L[y]);
}
update(Root);
}
int Merge(int x,int y){
if(!x||!y) return x+y;
if(Key[x]>Key[y]){
push_down(x);
R[x]=Merge(R[x],y);
update(x);
return x;
}else{;
push_down(y);
L[y]=Merge(x,L[y]);
update(y);
return y;
}
}
int New(int value){
if(tot==0){
++cnt;
Max[cnt]=Sum[cnt]=Val[cnt]=value;
L[cnt]=R[cnt]=0;
Key[cnt]=rand();
Size[cnt]=1;
lMax[cnt]=rMax[cnt]=max(0LL,value);
tp_val[cnt]=tp[cnt]=re[cnt]=0;
return cnt;
}else{
int Cnt=stk[tot--];
Max[Cnt]=Sum[Cnt]=Val[Cnt]=value;
L[Cnt]=R[Cnt]=0;
Key[Cnt]=rand();
Size[Cnt]=1;
lMax[Cnt]=rMax[Cnt]=max(0LL,value);
tp_val[Cnt]=tp[Cnt]=re[Cnt]=0;
return Cnt;
}
}
int build(int l,int r){
if(l!=r){
int mid=l+r>>1;
return Merge(build(l,mid),build(mid+1,r));
}else
return New(Arr[l]);
}
void insert(int k,int Cnt){
int Root=build(1,Cnt);
split(ROOT,k,X,Y);
ROOT=Merge(Merge(X,Root),Y);
}
void D(int x){
if(!x)return;
stk[++tot]=x;
// Val[x]=0,Key[x]=0,L[x]=0,R[x]=0,Size[x]=0,Sum[x]=0,tp_val[x]=0,Max[x]=0,lMax[x]=0,rMax[x]=0,re[x]=0,tp[x]=0;
D(L[x]),D(R[x]);
}
void Del(int l,int r){
split(ROOT,r,X,Z);
split(X,l-1,X,Y);
ROOT=Merge(X,Z);
D(Y);
}
void Re(int l,int r){
split(ROOT,r,X,Z);
split(X,l-1,X,Y);
push_down(Y);
if(re[Y]==1) re[Y]=0;
else re[Y]=1;
ROOT=Merge(Merge(X,Y),Z);
}
void Tp(int l,int r,int c){
split(ROOT,r,X,Z);
split(X,l-1,X,Y);
push_down(Y);
tp[Y]=true;
tp_val[Y]=c;
ROOT=Merge(Merge(X,Y),Z);
}
int Get_Max(){
// update(ROOT);
return Max[ROOT];
}
int Get_Sum(int l,int r){
split(ROOT,r,X,Z);
split(X,l-1,X,Y);
push_down(Y);
update(Y);
int res=Sum[Y];
ROOT=Merge(Merge(X,Y),Z);
return res;
}
void OUT(int x){
if(!x)return;
// stk[++tot]=x;
cout<<x<<"\n";
OUT(L[x]),OUT(R[x]);
}
}tr;
bool ed;
signed main(){
#if IOS
std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#endif
#if FIO
File("que");
#endif
srand(time(NULL));
int n,m;
cin>>n>>m;
memset(tr.Max,-0x7f,sizeof tr.Max);
for(int i=1;i<=n;i++) cin>>Arr[i];
for(int i=1;i<=n;i++){
int dt=tr.New(Arr[i]);
tr.split(tr.ROOT,i-1,tr.X,tr.Z);
tr.ROOT=tr.Merge(tr.Merge(tr.X,dt),tr.Z);
}
// tr.insert(0,n);
// tr.OUT(tr.ROOT);
// cout<<tr.Size[tr.ROOT]<<"\n";
while(m--){
string s;
cin>>s;
if(s[0]=='I'){
int k,tot;
cin>>k>>tot;
if(tot==0) continue;
for(int i=1;i<=tot;i++) cin>>Arr[i];
// for(int i=1;i<=tot;i++){
// int dt=tr.New(Arr[i]);
// tr.split(tr.ROOT,k+i-1,tr.X,tr.Z);
// tr.ROOT=tr.Merge(tr.Merge(tr.X,dt),tr.Z);
// }
tr.insert(k,tot);
}else if(s[0]=='D'){
int k,tot;
cin>>k>>tot;
if(tot==0) continue;
tr.Del(k,k+tot-1);
}else if(s[0]=='M'&&s[2]=='K'){
int k,tot,c;
cin>>k>>tot>>c;
if(tot==0) continue;
tr.Tp(k,k+tot-1,c);
}else if(s[0]=='R'){
int k,tot;
cin>>k>>tot;
if(tot==0) continue;
tr.Re(k,k+tot-1);
}else if(s[0]=='G'){
int k,tot;
cin>>k>>tot;
if(tot==0) cout<<0<<"\n";
cout<<tr.Get_Sum(k,k+tot-1)<<"\n";
}else{
int dt=tr.Get_Max();
// if(dt<0) cout<<0<<"\n";
/*else */cout<<dt<<"\n";
}
}
#if DEBUG
cerr<<1.00*clock()/CLOCKS_PER_SEC<<" s\n";
cerr<<abs(&st-&ed)/1024.00/1024.00<<" MB";
#endif
return 0;
}
加载中...