UVA12299 RMQ with Shifts
xiezheyuan
·
·
题解
也许有更好的阅读体验
简要题意
你需要维护一个长为 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] 的最小值。
## 思路
输入操作长度不超过 $30$ 这个条件很关键。它告诉我们,最多有 $30$ 个元素会被修改,而 $30$ 很小,完全可以逐个单点修改来实现。具体做法是,储存一下 $v=a_{i_1}$,然后逐个按题面修改,最后将 $a_{i_k}$ 修改为 $v$ 即可。
于是这道题可以用一个支持单点修改,区间最小值的数据结构解决,恰好,线段树就可以胜任这两个操作。
时间复杂度 $O(n+q\log n)$,完全可以通过本题。
最后讲一讲输入,貌似题解里没有我这么输入的。
我的输入方法是:每个操作用 `std::cin` 读入一个字符串,然后从第 $6$ 个字符(下标从 $0$ 开始,这样子会跳过前面的引导字符串和一个左括号)。然后每遇到一个字符,进行分类讨论:
- 如果是右括号,直接忽略。
- 如果是逗号,则将计数器加 $1$,下一次存储时会存储到右边的位置中。
- 如果是数字,将计数器所对应的数据乘上 $10$ 加上这个字符表示的数字。
然后查询操作就是前两个数据,修改操作就是读进来的全部数据。
这个写法个人觉得比其他写法更简便、好懂,也不易写错。
## 代码
```cpp
#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;
}
```