学步园

题意：有一数组A是可变的，支持shift(i1,i2,...,ik),表示把元素A[i1],A[i2],....,A[ik],循环左移一位。query(L,R);是询问区间[L,R]的最小值。

思路：这是道比较简单的线段树问题，把循环的更改的值依次单点更新即可。

//0 KB    258 ms
#include
#include
#define L(u) (u<<1)
#define R(u) (u<<1|1)
const int M = 100005;

struct Node
{
    int l,r,minx;
} node[M<<2];
int val[M],tmp[50],n,m,Num;

int min(int a,int b)
{
    return a > b ? b : a;
}
void Pushup(int u)
{
    node[u].minx = min(node[L(u)].minx,node[R(u)].minx);
}
void Build (int u,int left,int right)
{
    node[u].l = left,node[u].r = right;
    if (node[u].l == node[u].r)
    {
        node[u].minx = val[left];
        return ;
    }
    int mid = (node[u].l + node[u].r)>>1;
    Build (L(u),left,mid);
    Build (R(u),mid+1,right);
    Pushup(u);
}
void Update(int u,int pos,int va)
{
    if (node[u].l == node[u].r)
    {
        node[u].minx = va;
        return ;
    }
    int mid = (node[u].l+node[u].r)>>1;
    if (pos <= mid) Update(L(u),pos,va);
    else Update(R(u),pos,va);
    Pushup(u);
}
int Query (int u,int left,int right)
{
    if (left<=node[u].l&&node[u].r<=right)
        return node[u].minx;
    int mid = (node[u].l + node[u].r )>>1;
    if (right<= mid) return Query(L(u),left,right);
    else if (left > mid) return Query(R(u),left,right);
    else return min(Query(L(u),left,mid),Query(R(u),mid+1,right));
}
void solve()
{
    char str[50];
    int i,j,t;
    memset(str,'\0',sizeof(str));
    scanf ("%s",str);
    if (str[0] == 's')
    {
        for (j = 0,i = 0; i < strlen(str); i ++)
        {
            if (str[i]<'0'||str[i] >'9') continue;
            t = 0;
            while (str[i]>='0'&&str[i]<='9')
            {
                t *= 10;
                t += str[i] - '0';
                i ++;
            }
            tmp[j++] = t;
        }
        Num = j;
        t = val[tmp[0]];
        for (i = 0; i < Num-1; i ++)
        {
            val[tmp[i]] = val[tmp[i+1]];
            Update(1,tmp[i],val[tmp[i]]);
        }
        val[tmp[i]] = t;
        Update(1,tmp[i],val[tmp[i]]);
    }
    else
    {
        for (j = 0,i = 0;i
        {
            if (str[i]<'0'||str[i] >'9') continue;
            t = 0;
            while (str[i]>='0'&&str[i]<='9')
            {
                t *= 10;
                t += str[i] - '0';
                i ++;
            }
            tmp[j++] = t;
        }
        printf ("%d\n",Query(1,tmp[0],tmp[1]));
    }
}
int main ()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    while (~scanf ("%d %d",&n,&m))
    {
        for (int i = 1; i <= n; i++)
            scanf("%d",&val[i]);
        Build (1,1,n);
        while (m --)
            solve();
    }
    return 0;
}