UVA12299 RMQ with Shifts

· · 题解

也许有更好的阅读体验

简要题意

你需要维护一个长为 n 的序列 a,支持以下操作:

## 思路 输入操作长度不超过 $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; } ```