1. 题目

传送门=￣ω￣=

2. 题解

考试考了这题，幸好对拍了。

挺好的模板。

代码：

#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
#define REG register
#pragma GCC optimize(2)
#define NS (200005)
using namespace std;
template<typename _Tp>inline void IN(REG _Tp&dig)
{
    REG char c;REG bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,mx,tag,rev,sz;}e[NS];
int n,m,data[NS],root,cnt;
char opt[10];
bool pos(REG int a){return e[e[a].f].s[1]==a;}
void pup(REG int a)
{
    e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;
    e[a].mx=min(e[e[a].s[0]].mx,e[e[a].s[1]].mx);
    e[a].mx=min(e[a].mx,e[a].d);
}
void pdown(REG int a)
{
    REG int l=e[a].s[0],r=e[a].s[1],t=e[a].tag;
    if(t)
    {
        if(l)e[l].tag+=t,e[l].d+=t,e[l].mx+=t;
        if(r)e[r].tag+=t,e[r].d+=t,e[r].mx+=t;
        e[a].tag=0;
    }
    if(e[a].rev)
    {
        if(l)e[l].rev^=1,swap(e[l].s[0],e[l].s[1]);
        if(r)e[r].rev^=1,swap(e[r].s[0],e[r].s[1]);
        e[a].rev=0;
    }
}
int build(REG int l,REG int r,REG int fa)
{
    if(l>r)return 0;
    REG int a=++cnt,mid=(l+r)>>1;
    e[a].d=data[mid],e[a].f=fa;
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    pup(a);
    return a;
}
void rot(REG int a)
{
    REG int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(REG int a,REG int t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
int find_by_order(REG int k)
{
    int a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
inline void get_seg(int&l,int&r)
{
    l=find_by_order(l),r=find_by_order(r+2);
    splay(l,0),splay(r,l);
}
void work_add()
{
    REG int l,r,d,p;
    IN(l),IN(r),IN(d),get_seg(l,r),p=e[r].s[0];
    e[p].tag+=d,e[p].d+=d,e[p].mx+=d,pup(r),pup(root);
}
void work_rev()
{
    REG int l,r,p;
    IN(l),IN(r),get_seg(l,r),p=e[r].s[0];
    e[p].rev^=1,swap(e[p].s[0],e[p].s[1]);
}
void work_rot()
{
    REG int l,r,t,tmp,p;
    IN(l),IN(r),IN(t);
    if(t%=(r-l+1),!t)return;
    tmp=r-t+1,get_seg(tmp,r),p=e[r].s[0];
    e[r].s[0]=0,pup(r),pup(root);
    r=l-1,get_seg(l,r),e[r].s[0]=p,e[p].f=r,pup(r),pup(root);
}
void work_insert()
{
    REG int x,y;
    IN(x),IN(data[1]),x++,y=x-1,get_seg(x,y);
    e[y].s[0]=build(1,1,y),pup(y),pup(root);
}
void work_del()
{
    REG int x,y;
    IN(x),y=x,get_seg(x,y);
    e[e[y].s[0]].f=0,e[y].s[0]=0,pup(y),pup(root);
}
void work_mx()
{
    REG int l,r;
    IN(l),IN(r),get_seg(l,r),printf("%d\n",e[e[r].s[0]].mx);
}
int main()
{
    IN(n),e[0].d=e[0].mx=data[1]=data[n+2]=INT_MAX;
    for(REG int i=1;i<=n;i++)IN(data[i+1]);
    root=build(1,n+2,0);
    IN(m);
    while(m--)
    {
        scanf("%s",opt);
        if(opt[0]=='A')work_add();
        else if(opt[0]=='R')
        {
            if(opt[3]=='E')work_rev();
            else work_rot();
        }
        else if(opt[0]=='I')work_insert();
        else if(opt[0]=='D')work_del();
        else work_mx();
    }
    return 0;
}