简要题意

你需要维护一个长为 \(n\) 的序列 \(a\)，支持以下操作：

• shift(i1,i2,...,ik) 对于 \(1 \leq p \leq k\)，将 \(a_{i_p}\) 赋值为 \(a_{i_{(p \bmod k) + 1}}\)。
• query(l,r) 查询区间 \([l,r]\) 的最小值。

\(1 \leq n \leq 10^5,1 \leq q \leq 2.5\times 10^5\)，输入的操作长度不超过 \(30\)。

思路

输入操作长度不超过 \(30\) 这个条件很关键。它告诉我们，最多有 \(30\) 个元素会被修改，而 \(30\) 很小，完全可以逐个单点修改来实现。具体做法是，储存一下 \(v=a_{i_1}\)，然后逐个按题面修改，最后将 \(a_{i_k}\) 修改为 \(v\) 即可。

于是这道题可以用一个支持单点修改，区间最小值的数据结构解决，恰好，线段树就可以胜任这两个操作。

时间复杂度 \(O(n+q\log n)\)，完全可以通过本题。

最后讲一讲输入，貌似题解里没有我这么输入的。

我的输入方法是：每个操作用 std::cin 读入一个字符串，然后从第 \(6\) 个字符（下标从 \(0\) 开始，这样子会跳过前面的引导字符串和一个左括号）。然后每遇到一个字符，进行分类讨论：

• 如果是右括号，直接忽略。
• 如果是逗号，则将计数器加 \(1\)，下一次存储时会存储到右边的位置中。
• 如果是数字，将计数器所对应的数据乘上 \(10\) 加上这个字符表示的数字。

然后查询操作就是前两个数据，修改操作就是读进来的全部数据。

这个写法个人觉得比其他写法更简便、好懂，也不易写错。

代码

#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int n,q;
const int N = 100005;
int mint[N<<2];

void pushup(int i){
    mint[i]=min(mint[ls],mint[rs]);
}

void build(int i,int l,int r){
    if(l==r){
        cin>>mint[i];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}

void update(int p,int v,int i,int l,int r){
    if(l==r){
        mint[i]=v;return;
    }
    if(p<=mid) update(p,v,ls,l,mid);
    else update(p,v,rs,mid+1,r);
    pushup(i);
}

int query(int ql,int qr,int i,int l,int r){
    if(ql<=l&&r<=qr) return mint[i];
    int ans=INT_MAX;
    if(ql<=mid) ans=min(ans, query(ql,qr,ls,l,mid));
    if(qr>mid) ans=min(ans, query(ql,qr,rs,mid+1,r));
    return ans;
}

void shift(int *ids,int size){
    int first = query(ids[0], ids[0], 1, 1, n);
    for(int i=0;i<size-1;i++){
        update(ids[i], query(ids[i+1], ids[i+1], 1, 1, n), 1, 1, n);
    }
    update(ids[size-1], first, 1, 1, n);
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        string str;
        cin>>str;
        int arr[30],tot=0;
        memset(arr,0,sizeof(arr));
        for(int i=6;i<str.size();i++){
            if(str[i] == ')') continue;
            if(str[i] == ',') tot++;
            else arr[tot]=arr[tot]*10+(str[i]-'0');
        }
        if(str[0] == 'q') cout<<query(arr[0], arr[1], 1,1, n)<<'\n';
        else {
            shift(arr, tot+1);
        }
    }
    return 0;
}