UVA12299 RMQ with Shifts 题解

题目链接：UVA12299 RMQ with Shifts

题意：

萌妹纸 cxy 想要维护一个数据结构，支持以下操作（询问由字符串给出）：

1. shift(a,b,c...) 该字符串表示把位于 \(\langle a,b,c\cdots\rangle\) 的数移动为 \(\langle b,c\cdots,a \rangle\)
2. query(l,r) 该字符串表示查询 \([l,r]\) 的最小值。

因为 cxy 忙着和妹纸玩，所以这个任务就交给你啦！

数据范围：

\(1\le n,q\le 10^5\) ，询问字符串的长度不超过 \(30\) 。

注意到询问的字符串长度不超过 \(30\) ，因此需要移动的位置在 \(10\) 个左右，记为 \(\varepsilon\)

我们直接维护一个单点修改的线段树，然后把每个要移动的位置改一下值就好了

时间复杂度 \(\mathcal{O}(\varepsilon n \log n)\)

代码：（摘自参考文献[1]）

#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;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/xiezheyuan/solution-uva12299