RMQ with Shifts - UVA 12299

题目描述

在传统的RMQ问题中有一个不变的数组A,然后需要堆每个询问(L，R)输出A[L],A[L + 1],...,A[R]中的最小值

在本题中A时可变的，我们还需要支持一种询问移动操作，即shift(i1,i2,...,ik)表示把元素A[i1],A[i2],...,A[ik]

循环向左移动一次。

对于每个query操作，输出范围最小值

所有操作以字符串的格式给出，长度不会超过30

样例

1
3
5 11 3
1 10 1
3 13 2
0
14

算法1

(线段树单点修改 + 区间最值)
  • 动态区间问题我们考虑用线段树
  • 我们发现操作的元素个数很少
  • 所以可以用单点修改处理shift操作（单次最多不会超过15次）
  • 询问就是常见的区间最值

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
const int INF = 0x3f3f3f3f;
struct Node
{
    int l,r;
    int minv,maxv;
    int setv;
}tr[N * 4];
char str[50];
int a[N];
int qu[N],cnt;
int flag[N * 4];
int ks;
int n,q;

void init(int u)
{
    if(flag[u] == ks) return;
    flag[u] = ks;
    tr[u].minv = tr[u].maxv = 0;
    tr[u].setv = -1;
}

void pushup(int u)
{
    init(lc);
    init(rc);
    tr[u].minv = min(tr[lc].minv,tr[rc].minv);
    tr[u].maxv = max(tr[lc].maxv,tr[rc].maxv);
}

void pushdown(int u)
{
    if(tr[u].setv != -1)
    {
        init(lc);
        init(rc);
        tr[lc].minv = max(tr[lc].minv,tr[u].setv);
        tr[lc].maxv = max(tr[lc].maxv,tr[u].setv);
        tr[rc].minv = max(tr[rc].minv,tr[u].setv);
        tr[rc].maxv = max(tr[rc].maxv,tr[u].setv);
        tr[lc].setv = max(tr[lc].setv,tr[u].setv);
        tr[rc].setv = max(tr[rc].setv,tr[u].setv);
        tr[u].setv = -1;
    }
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = Node({l,r,0,0,-1});
        return;
    }
    int mid = (l + r) >> 1;
    tr[u] = Node({l,r});
    build(lc,l,mid);
    build(rc,mid + 1,r);
    pushup(u);
}

void modify(int u,int l,int r,int k)
{
    init(u);
    if(tr[u].minv > k) return;
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].minv = tr[u].setv = k;
        if(tr[u].maxv <= k)
        {
            tr[u].maxv = k;
            return;
        }
    }
    if(tr[u].l == tr[u].r) return;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(lc,l,r,k);
    if(r > mid) modify(rc,l,r,k);
    pushup(u);
}

int query(int u,int l,int r,int k)
{
    init(u);
    if(tr[u].minv > k) return 0;
    if(tr[u].l >= l && tr[u].r <= r && tr[u].maxv <= k) 
        return (tr[u].r - tr[u].l + 1);
    if(tr[u].l == tr[u].r) return 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0;
    if(l <= mid) res += query(lc,l,r,k);
    if(r > mid)  res += query(rc,l,r,k);
    pushup(u);
    return res;
}

void dfs(int u,int l,int r,int k)
{
    // printf("%d %d %d\n",tr[u].l,tr[u].r,tr[u].maxv);
    if(tr[u].l >= l && tr[u].r <= r && tr[u].maxv <= k) 
    {
        printf("%d %d %d\n",tr[u].l,tr[u].r,(tr[u].r - tr[u].l + 1));
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid && tr[lc].minv <= k) dfs(lc,l,r,k);
    if(r > mid && tr[rc].minv <= k) dfs(rc,l,r,k);
}

void solve()
{
    build(1,1,N - 1);
    while(scanf("%d",&n) == 1,n)
    {
        while(n -- )
        {
            scanf("%d",&q);
            ks ++;
            LL res = 0;
            for(int i = 0;i < q;i ++)
            {
                int l,r,h;
                scanf("%d%d%d",&l,&r,&h);
                // printf("%d\n",query(1,l,r - 1,h));
                // dfs(1,l,r - 1,h);
                res += query(1,l,r - 1,h);
                modify(1,l,r - 1,h);
            }
            printf("%lld\n",res);
        }
    }
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}