C++(g++ 7.5.0) 解法, 执行用时: 262ms, 内存消耗: 4000K, 提交时间: 2022-08-09 15:13:18
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define keytree (ch[ch[root][1]][0])
#define maxn 200010
int pre[maxn],ch[maxn][2],siz[maxn],key[maxn];
int add[maxn];
int root,tot1;
int rev[maxn],mx[maxn];
int s[maxn],tot2;
int a[maxn];
int n,q;
inline void newnode(int &r,int f,int k)
{
if(tot2) r=s[tot2--];
else r=++tot1;
pre[r]=f;
ch[r][0]=ch[r][1]=0;
key[r]=k;
mx[r]=k;
add[r]=0;
rev[r]=0;
siz[r]=1;
}
inline void update_rev(int r)
{
if(!r) return ;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
}
inline void update_add(int r,int val)
{
if(!r) return ;
add[r]+=val;
key[r]+=val;
mx[r]+=val;
}
inline void pushdown(int r)
{
if(rev[r])
{
update_rev(ch[r][0]);
update_rev(ch[r][1]);
rev[r]=0;
}
if(add[r])
{
update_add(ch[r][0],add[r]);
update_add(ch[r][1],add[r]);
add[r]=0;
}
}
inline void pushup(int r)
{
int lson=ch[r][0],rson=ch[r][1];
siz[r]=siz[lson]+siz[rson]+1;
mx[r]=key[r];
mx[r]=min(mx[lson],mx[r]);
mx[r]=min(mx[rson],mx[r]);
}
inline void build(int &x,int l,int r,int f)
{
if(l>r) return ;
int mid=(l+r)>>1;
newnode(x,f,a[mid]);
build(ch[x][0],l,mid-1,x);
build(ch[x][1],mid+1,r,x);
pushup(x);
}
void init()
{
root=tot1=tot2=0;
ch[root][0]=ch[root][1]=siz[root]=pre[root]=0;
rev[root]=0;
key[root]=INF;
mx[root]=INF;
add[root]=0;
newnode(root,0,INF);
newnode(ch[root][1],root,INF);
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
build(keytree,0,n-1,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
inline void Rotate(int x,int kind)
{
int y=pre[x];
pushdown(y);
pushdown(x);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
pushup(y);
}
void splay(int r,int goal)
{
pushdown(r);
while(pre[r]!=goal)
{
if(pre[pre[r]]==goal)
{
pushdown(pre[r]);
pushdown(r);
Rotate(r,ch[pre[r]][0]==r);
}
else
{
pushdown(pre[pre[r]]);
pushdown(pre[r]);
pushdown(r);
int y=pre[r];
int kind=ch[pre[y]][0]==y;
if(ch[y][kind]==r)
{
Rotate(r,!kind);
Rotate(r,kind);
}
else
{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
pushup(r);
if(goal==0) root=r;
}
inline int get_kth(int r,int k)
{
pushdown(r);
int t=siz[ch[r][0]]+1;
if(t==k) return r;
if(t>k) return get_kth(ch[r][0],k);
else return get_kth(ch[r][1],k-t);
}
inline void Insert(int pos,int tot)
{
for(int i=0; i<tot; i++) scanf("%d",&a[i]);
splay(get_kth(root,pos+1),0);
splay(get_kth(root,pos+2),root);
build(keytree,0,tot-1,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
inline void Erase(int r)
{
if(!r) return ;
s[++tot2]=r;
Erase(ch[r][0]);
Erase(ch[r][1]);
}
inline void Delete(int pos,int tot)
{
splay(get_kth(root,pos),0);
splay(get_kth(root,pos+tot+1),root);
Erase(keytree);
pre[keytree]=0;
keytree=0;
pushup(ch[root][1]);
pushup(root);
}
inline void Reverse(int pos,int tot)
{
splay(get_kth(root,pos),0);
splay(get_kth(root,pos+tot+1),root);
update_rev(keytree);
pushup(ch[root][1]);
pushup(root);
}
inline void Add(int l,int r,int num)
{
splay(get_kth(root,l),0);
splay(get_kth(root,r+2),root);
key[keytree]+=num;
add[keytree]+=num;
mx[keytree]+=num;
}
void Revolve(int l,int r,int c)
{
int mod=r-l+1;
if(c<0)
{
c=-c;
c%=mod;
if(!c) return ;
c=mod-c;
}
else c=c%mod;
if(!c) return ;
int mid=r-c+1;
splay(get_kth(root,mid),0);
splay(get_kth(root,r+2),root);
int temp=keytree;
keytree=0;
pushup(ch[root][1]);
pushup(root);
splay(get_kth(root,l),0);
splay(get_kth(root,l+1),root);
keytree=temp;
pre[temp]=ch[root][1];
pushup(ch[root][1]);
pushup(root);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
scanf("%d",&q);
while(q--)
{
char op[20];
scanf("%s",op);
if(!strcmp(op,"ADD"))
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a>b) swap(a,b);
Add(a,b,c);
}
else if(!strcmp(op,"REVERSE"))
{
int a,b;
scanf("%d%d",&a,&b);
if(a>b) swap(a,b);
Reverse(a,b-a+1);
}
else if(!strcmp(op,"REVOLVE"))
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Revolve(a,b,c);
}
else if(!strcmp(op,"INSERT"))
{
int a;
scanf("%d",&a);
Insert(a,1);
}
else if(!strcmp(op,"DELETE"))
{
int a;
scanf("%d",&a);
Delete(a,1);
}
else if(!strcmp(op,"MIN"))
{
int a,b;
scanf("%d%d",&a,&b);
splay(get_kth(root,a),0);
splay(get_kth(root,b+2),root);
printf("%d\n",mx[keytree]);
}
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 282ms, 内存消耗: 6220K, 提交时间: 2020-05-04 22:01:42
#include<iostream>
#include<cstdio>
using namespace std;
struct{int l,r,size,dat,bit,add,rev;}a[200010];
int L[200010],R[200010],n,m,tot,root,i,x,y,z;
char str[10];
void spreadadd(int x,int y)
{
if(!x||!y) return;
a[x].add+=y; a[x].dat+=y; a[x].bit+=y;
}
void spreadrev(int x)
{
if(!a[x].rev) return;
swap(a[x].l,a[x].r);
if(a[x].l) a[a[x].l].rev^=1;
if(a[x].r) a[a[x].r].rev^=1;
}
void spread(int x)
{
spreadadd(a[x].l,a[x].add);
spreadadd(a[x].r,a[x].add);
spreadrev(x);
a[x].add=a[x].rev=0;
}
inline void update(int x)
{
a[x].size=a[a[x].l].size+a[a[x].r].size+1;
a[x].bit=min(a[x].dat,min(a[a[x].l].bit,a[a[x].r].bit));
}
void turnleft(int &x)
{
int y=a[x].r; a[x].r=a[y].l; a[y].l=x;
update(x); update(y); x=y;
}
void turnright(int &x)
{
int y=a[x].l; a[x].l=a[y].r; a[y].r=x;
update(x); update(y); x=y;
}
void splay(int &x,int y)
{
if(!x) return;
L[0]=R[0]=0;
while(1)
{
spread(x),spread(a[x].l),spread(a[x].r);
int temp=a[a[x].l].size+1;
if(y==temp||(y<temp&&!a[x].l)||(y>temp&&!a[x].r)) break;
if(y<temp)
{
if(a[a[x].l].l&&y<=a[a[a[x].l].l].size) {turnright(x); if(!a[x].l) break;}
R[++R[0]]=x; x=a[x].l;
}
else
{
y-=temp;
int temp=a[a[a[x].r].l].size+1;
if(a[a[x].r].r&&y>temp) {y-=temp; turnleft(x); if(!a[x].r) break;}
L[++L[0]]=x; x=a[x].r;
}
}
L[++L[0]]=a[x].l; R[++R[0]]=a[x].r;
for(int i=L[0]-1;i>0;i--) {a[L[i]].r=L[i+1]; update(L[i]);}
for(int i=R[0]-1;i>0;i--) {a[R[i]].l=R[i+1]; update(R[i]);}
a[x].l=L[1]; a[x].r=R[1]; update(x);
}
void ADD(int x,int y,int z)
{
splay(root,y+1);
splay(a[root].l,x-1);
spreadadd(a[a[root].l].r,z);
}
void INSERT(int x,int y)
{
splay(root,x);
a[++tot].dat=y; a[tot].r=a[root].r; a[root].r=tot;
update(tot); update(root);
}
void DELETE(int x)
{
splay(root,x);
splay(a[root].r,1);
a[a[root].r].l=a[root].l; root=a[root].r;
update(root);
}
void REVERSE(int x,int y)
{
splay(root,y+1);
splay(a[root].l,x-1);
a[a[a[root].l].r].rev^=1;
}
void REVOLVE(int x,int y,int z)
{
z%=y-x+1;
if(!z)return;
int mid=y-z;
splay(root,mid);
splay(a[root].l,x-1);
splay(a[root].r,y-a[a[root].l].size);
z=a[root].l;
a[root].l=a[z].r;
a[z].r=a[a[root].r].l;
a[a[root].r].l=0;
update(z); update(a[root].r); update(root);
splay(root,1);
a[root].l=z;
update(root);
}
void MIN(int x,int y)
{
splay(root,y+1);
splay(a[root].l,x-1);
printf("%d\n",a[a[a[root].l].r].bit);
}
int main()
{
cin>>n;
a[1].size=1; a[n+2].l=n+1; a[n+2].size=n+2;
a[1].dat=a[n+2].dat=a[1].bit=a[0].bit=0x3fffffff;
for(i=2;i<=n+1;i++)
{
scanf("%d",&a[i].dat);
a[i].l=i-1; a[i].size=i;
a[i].bit=min(a[i-1].bit,a[i].dat);
}
a[n+2].bit=a[n+1].bit;
root=tot=n+2;
cin>>m;
for(i=0;i<m;i++)
{
scanf("%s",&str);
if(str[0]=='A') {scanf("%d%d%d",&x,&y,&z); ADD(++x,++y,z);}
if(str[0]=='I') {scanf("%d%d",&x,&y); INSERT(++x,y);}
if(str[0]=='D') {scanf("%d",&x); DELETE(++x);}
if(str[0]=='M') {scanf("%d%d",&x,&y); MIN(++x,++y);}
if(str[0]=='R'&&str[3]=='E') {scanf("%d%d",&x,&y); REVERSE(++x,++y);}
if(str[0]=='R'&&str[3]=='O') {scanf("%d%d%d",&x,&y,&z); REVOLVE(++x,++y,z);}
}
return 0;
}
. Then the host performs a series of operations and queries on the sequence which consists:. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
.
, the numbers of operations and queries.