bzoj3339 Rmq Problem

3339: Rmq Problem

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1316  Solved: 696
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

Source

By Xhr

分析：这道题因为只涉及到区间查询，可以考虑一些这类优秀算法，解决这道题可以用莫队算法.

      对于每次增加操作，如果新增加的这个数正好是当前的ans,那么我们就不断把ans++,直到没有出现和ans相等的数，对于删除操作，看删除的这个数是否比ans小，是的话直接更新就好了.不过似乎每次转移不是O(1)的，还好数据没有特别卡莫队，不然就gg了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 2000010;

int n, q,a[maxn],ans[maxn],anss,L = 1,R = 0,sizee = 0,c[maxn];
struct node
{
    int l, r, id;
}e[maxn];

bool cmp(node a, node b)
{
    if (a.l / sizee == b.l / sizee)
        return a.r < b.r;
    else
        return a.l / sizee < b.l / sizee;
}

void add(int x)
{
    c[a[x]]++;
    if (anss == a[x])
    while (c[anss])
        anss++;
}

void del(int x)
{
    c[a[x]]--;
    if (c[a[x]] == 0 && a[x] < anss)
        anss = a[x];
}

int main()
{
    scanf("%d%d", &n, &q);
    sizee = sqrt(n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &e[i].l, &e[i].r);
        e[i].id = i;
    }
    sort(e + 1, e + 1 + q,cmp);
    for (int i = 1; i <= q; i++)
    {
        while (R < e[i].r)
            add(++R);
        while (L > e[i].l)
            add(--L);
        while (R > e[i].r)
            del(R--);
        while (L < e[i].l)
            del(L++);
        ans[e[i].id] = anss;
    }
    for (int i = 1; i <= q; i++)
        printf("%d
", ans[i]);

    return 0;
}