首页 > 其他 > 详细

BZOJ3339&&3585 Rmq Problem&&mex

时间:2018-02-25 20:29:29      阅读:268      评论:0      收藏:0      [点我收藏+]

BZOJ3339&&3585:Rmq Problem&&mex

Description

  有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。

Input

  第一行n,m。
  第二行为n个数。
  从第三行开始,每行一个询问l,r。

Output

  一行一个数,表示每个询问的答案。

Sample Input

5 5

2 1 0 2 1

3 3

2 3

2 4

1 2

3 5

Sample Output

1

2

3

0

3

HINT

数据规模和约定

  对于\(100%\)的数据:

  \(1\leq n,m\leq200000\)

  \(0\leq a_i\leq10^9\)

  \(1\leq l,r\leq n\)

  对于\(30%\)的数据:

  \(1\leq n,m \leq1000\)

题解

先离散化,注意补充上每个数\(+1\)\(0\)
离线所有询问,按左端点\(l\)排序。
不难得到\([1,i]\)的答案
考虑已知区间\([l,r]\)的答案,如何得到区间\([l+1,r]\)的答案
这样其实是删除了\(a[l]\)\(nxt[l]\)表示下一个\(a[l]\)出现的位置,所以删除\(a[l]\)影响了\([l+1,l+1]\)\([l+1,nxt[l]-1]\)这些区间。这些区间的\(mex\)都要对\(a[l]\)\(min\)
区间取\(min\),典型线段树操作。叶子节点的\(ma\)是值,其余节点\(ma\)存区间取\(min\)标记。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <string>
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void read(T &x)
{
    x = 0;char ch = getchar(), c = ch;
    while(ch < '0' || ch > '9') c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
    if(c == '-') x = -x;
}
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
const int INF = 0x3f3f3f3f;
const int MAXN = 400000 + 10;
int n,q,num[MAXN],tong[MAXN],nxt[MAXN];
struct Q
{
    int l,r,rank;
}a[MAXN];
bool cmp(Q a, Q b)
{
    return a.l < b.l;
}
struct Node
{
    int ma, lazy, l, r;
    Node(){ma = INF;lazy = -1;}
}node[MAXN << 3];
void pushdown(int o)
{
    node[o << 1].ma = min(node[o << 1].ma, node[o].ma);
    node[o << 1 | 1].ma = min(node[o << 1 | 1].ma, node[o].ma); 

} 
void modify(int ll, int rr, int k, int o = 1, int l = 1, int r = n)
{
    pushdown(o);node[o].l = l, node[o].r = r;
    if(ll <= l && rr >= r)
    {
        node[o].ma = min(node[o].ma, k);
        node[o].lazy = k;
        return;
    } 
    int mid = (l + r) >> 1;
    if(mid >= ll) modify(ll, rr, k, o << 1, l, mid);
    if(mid < rr) modify(ll, rr, k, o << 1 | 1, mid + 1, r);
    return;
}
int ask(int p, int o = 1, int l = 1, int r = n)
{
    pushdown(o);
    if(l == r && p == l) return node[o].ma;
    int mid = (l + r) >> 1;
    if(p <= mid) return ask(p, o << 1, l, mid);
    else return ask(p, o << 1 | 1, mid + 1, r);
}
int ans[MAXN];

//lisanhua
int tmp[MAXN], cnt[MAXN], val[MAXN], tot;
bool cmpp(int a, int b)
{
    return tmp[a] < tmp[b];
}

int main()
{
    read(n), read(q);
    for(int i = 1;i <= n;++ i)
        read(num[i]), tmp[i] = num[i], cnt[i] = i;
    std::sort(cnt + 1, cnt + 1 + n, cmpp);num[0] = -1;
    for(int i = 1;i <= n;++ i)
    {
        if(tmp[cnt[i - 1]] != tmp[cnt[i]]) 
        {
            ++ tot;
            if(tmp[cnt[i]] - tmp[cnt[i - 1]] > 1) val[tot] = num[cnt[i - 1]] + 1, ++ tot;
            num[cnt[i]] = tot;
            val[tot] = tmp[cnt[i]];
        }
        else num[cnt[i]] = tot;
    }
    val[++ tot] = tmp[cnt[n]] + 1;
    for(int i = 1;i <= q;++ i)
        read(a[i].l), read(a[i].r), a[i].rank = i;
    std::sort(a + 1, a + 1 + q, cmp);
    int p = 0;
    for(int i = 1;i <= n;++ i)
        if(num[i] == p)
        {
            tong[p] = 1;
            while(tong[p]) ++ p;
            modify(i, i, p);
        }
        else tong[num[i]] = 1, modify(i, i, p);
    memset(tong, 0, sizeof(tong));
    for(int i = n;i >= 1;-- i) 
        if(!tong[num[i]]) nxt[i] = n + 1, tong[num[i]] = i;
        else nxt[i] = tong[num[i]], tong[num[i]] = i;
    int now = 1;
    for(int i = 1;i <= q;++ i)
    {
        while(now < a[i].l)
        {
            modify(now, nxt[now] - 1, num[now]);
            ++ now;
        }
        ans[a[i].rank] = ask(a[i].r);
    }
    for(int i = 1;i <= q;++ i) printf("%d\n", val[ans[i]]);
    return 0;
}

BZOJ3339&&3585 Rmq Problem&&mex

原文:https://www.cnblogs.com/huibixiaoxing/p/8470095.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!