牛客练习赛34 F little w and Discretization (线段树 + 树状数组 + 离线)

发表于 | 分类于 | Views

题目链接

题意：
给你 $n$ 个数，$m$ 个操作，每个操作是对区间 $[L_i,R_i]$ 进行离散化，求这个区间离散化前和离散化后相同位置元素的值不一样的个数，每一个操作都是独立的。

解题思路：

这里是按照题解的写法，每一个离散化的操作可以看成是一个区间求 $mex$ 的操作，得到区间的 $mex$ 之后，在询问这个区间比 $mex$ 大的数有多少个就是每一个询问的答案了。

整个过程 离线 来搞。

那么，每一部分要怎么写呢，首先求区间 $mex$ ，这个可以用线段树来做，线段树维护区间编号出现的最左的位置，子节点维护子节点编号最后出现的位置。具体什么意思下面来讲。

对线段树每个结点初始化为 $-1$。 先对每个询问的 $R$ 排序，然后从左到右扫过去，每扫一个数就更新线段树上对应元素出现的最右位置，当扫到的点是询问的点的时候，就对 $L$ $query$ 一下。这里什么意思呢，就是我们知道这个区间最左端是 $L$，那么，在 $L$ 左边出现的较小的数我们是可以选的，比如 $1$ 最后出现的位置是 $L - 1$，那么我们这个 $mex$ 当然就可以选 $1$ 了，如果最后出现的位置大于 $L$ 就显然不能选 $1$。这样子线段树子节点为什么维护子节点编号最后出现的位置我们就知道了(这里的编号不是 $rt$，而是 $L$)，区间维护编号出现的最左位置，倘若区间最左的位置都比 $L$ 大了，那么这个区间所有的编号显然不能作为 \(mex\)，所以要往右区间找，直到 \(L == R\) 就是我们要的 \(mex\) 了。

这里推一道类似的求区间 $mex$ 的题

好了，求完 \(mex\)，剩下的就简单了，询问这个区间比 \(mex\) 大的数有多少个，经典题了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#include <ext/rope>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 3e5 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

int n;
int v[N];
int bit[N];
int tree[N << 2];

struct Query {
    int L;
    int R;
    int mex;
    int ansL;
    int ansR;
    int id;

    bool operator < (const Query& t) const {
        return R < t.R;
    }
}Q[N];

void update (int L, int R, int rt, int pos, int val) {
    if (L == R)
        tree[rt] = val;
    else {
        int mid = (L + R) >> 1;

        if (pos <= mid)
            update(L, mid, rt << 1, pos, val);
        else
            update(mid + 1, R, rt << 1 | 1, pos, val);

        tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
    }
}
int query (int L, int R, int rt, int pos) {
    if (L == R)
        return L;

    int mid = (L + R) >> 1;

    if (tree[rt << 1] < pos)
        return query(L, mid, rt << 1, pos);
    else
        return query(mid + 1, R, rt << 1 | 1, pos);
}
inline void add (int pos, int val) {
    for (; pos <= n; pos += lowbit(pos)) {
        bit[pos] += val;
    }
}
inline int getAns (int pos) {
    int res = 0;

    for (; pos > 0; pos -= lowbit(pos)) {
        res += bit[pos];
    }

    return res;
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    mst(tree, -1);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);

    int m;

    scanf("%d", &m);

    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &Q[i].L, &Q[i].R);
        Q[i].id = i;
    }

    sort(Q + 1, Q + 1 + m);

    for (int i = 1, pos = 1; i <= n; i++) {
        if (v[i] <= n) {
            update(1, n + 1, 1, v[i], i);
            add(v[i], 1);
        }

        for (; Q[pos].R == i && pos <= m; pos++) {
            Q[pos].mex = query(1, n + 1, 1, Q[pos].L);
            Q[pos].ansR = getAns(Q[pos].mex);
        }
    }

    mst(bit, 0);

    sort(Q + 1, Q + 1 + m, [](Query a, Query b) { return a.L < b.L; });

    for (int i = 0, pos = 1; i <= n; i++) {
        if (i && v[i] <= n)
            add(v[i], 1);

        for (; Q[pos].L - 1 == i && pos <= m; pos++) {
            Q[pos].ansL = getAns(Q[pos].mex);
        }
    }

    sort(Q + 1, Q + 1 + m, [](Query a, Query b) { return a.id < b.id; });

    for (int i = 1; i <= m; i++) {
        printf("%d\n", Q[i].R - Q[i].L + 1 - (Q[i].ansR - Q[i].ansL));
    }

    return 0;
}