bzoj - 3339 and bzoj - 3585

Posted by WildCow on May 30, 2018

Rmq Problem

Time Limit: 20 Sec
Memory Limit: 128 MB

Description

avater

Input

avater

Output

avater

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

mex

Time Limit: 20 Sec
Memory Limit: 128 MB

Description

有一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$。$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


感觉是我认为的经典数据结构题的模型
通过降维 or 转换
变成常见的模型
第二题的数据是一个假范围
对于大于 n 的数字对结果肯定没用贡献
直接丢掉就好了

莫队

不带修改的区间查询
很容易想到莫队
开一个 bool 型的数组标记当前区间每个数字出现的次数
然后答案就是找这个数组第一个 0 在哪个位置上
问题就转化成对于一个 0 1 序列
查询查询第一个 0 的位置
两种方法
树状数组维护一下区间和
每次二分终点即可
当然也可以分块
维护每个块内是否被完全覆盖
但是为什么我被造数据叉掉的暴力更新跑得快如闪电啊!


#include <bits/stdc++.h>
using namespace std;

const int N = 200020;

struct Quary
{
    int l;
    int r;
    int num;
};

Quary quary[N];
int cnt[N];
int ma[N];
int ans[N];
int bits[N];
int pos[N];
int n, m;
int block;

bool cmp(Quary a, Quary b)
{
    if(pos[a.l] == pos[b.l]){
        return a.r < b.r;
    }
    else{
        return pos[a.l] < pos[b.l];
    }
}

int lowbit(int x)
{
    return x & (- x);
}

int TreeQuary(int x)
{
    int ans;

    ans = 0;
    while(x > 0){
        // printf("x = %d  ans = %d\n", x, ans + bits[x]);
        ans += bits[x];
        x -= lowbit(x);
    }

    return ans;
}

int Update(int x, int v)
{
    while(x <= N){
        bits[x] += v;
        x += lowbit(x);
    }
}

void Add(int x)
{
    cnt[ma[x]] ++;
    if(ma[x]){
        if(cnt[ma[x]] == 1){
            /// printf("66666 = %d\n", ma[x]);
            Update(ma[x], 1);
        }
    }
}

void Del(int x)
{
    cnt[ma[x]] --;
    if(ma[x]){
        if(!cnt[ma[x]]){
            Update(ma[x], -1);
        }
    }
}

int Quary()
{
    int l, r;
    int ans;

    if(!cnt[0]){
        return 0;
    }
    l = 0;
    ans = l;
    r = n;
    while(l <= r){
        int mid;

        mid = l + ((r - l) >> 1);
        /// printf("mid = %d  sum = %d\n", mid, TreeQuary(mid));
        if(TreeQuary(mid) < mid){
            r = mid - 1;
            ans = mid;
        }
        else{
            l = mid + 1;
        }
    }
    // printf("ans = %d   sum = %d\n", ans, TreeQuary(ans) + 1);

    return ans;
}

int main(int argc, char const *argv[])
{
    int l, r;

    while(scanf("%d%d", &n, &m) == 2){
        memset(bits, 0, sizeof(bits));
        memset(cnt, 0, sizeof(cnt));
        block = sqrt(n);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
            pos[i] = i / block;
        }
        for(int i = 1; i <= m; i ++){
            scanf("%d%d", &quary[i].l, &quary[i].r);
            quary[i].num = i;
        }
        sort(quary + 1, quary + m + 1, cmp);
        l = 1;
        r = 0;
        for(int i = 1; i <= m; i ++){
            // printf("ql = %d  qr = %d\n", quary[i].l, quary[i].r);
            while(l < quary[i].l){
                Del(l);
                l ++;
            }
            while(l > quary[i].l){
                l --;
                Add(l);
            }
            while(r < quary[i].r){
                r ++;
                Add(r);
            }
            while(r > quary[i].r){
                Del(r);
                r --;
            }
            // printf("l = %d  r = %d\n", l, r);
            ans[quary[i].num] = Quary();
        }
        for(int i = 1; i <= m; i ++){
            printf("%d\n", ans[i]);
        }
    }

    return 0;
}




主席树

以后有时间补