简要题意
你需要维护一个长为 \(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;
}