Machine Learning 离散化 + 带修改莫队

发表于 | 分类于 | 阅读次数：

题目链接

题意

给你一个序列，每次询问一个区间，问你区间内的Mex值。

什么是Mex值呢？比如说某个数字出现1次，某个数字出现3次，那么Mex就是：2.

这个类似于SG函数，就是未出现过的最小的那个数字。

另外输入中还会有另一种操作： 单点修改

思路

我们肯定需要首先求出区间内每个数字出现的次数，然后再把这个次数存到一个数组中。求次数，不用说，莫队。但是单点修改需要用带修改莫队。需要注意的是，扩展区间的时候，要先扩展，再收缩，否则会出现下标为负数的情况。另外modify函数中，最后是交换两个数字，因为可能以后还得把他们换回来，所以不是赋值。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;
const int maxn = 400005;
struct node{
   int l, r, id, pre;
  }q[maxn];

struct node1{
    int pos, val;
}C[maxn];

int num[maxn], ans[maxn], a[maxn], b[maxn << 2], col[maxn], sum[maxn];

bool cmp(node a , node b)
{
    if(col[a.l] != col[b.l])  return a.l < b.l;
    else if(col[a.r] != col[b.r]) return a.r < b.r;
    else  return a.pre < b.pre;
}

void update(int x, int add)
{
    ans[sum[x]]--;
    sum[x] += add;
    ans[sum[x]]++;
}

void modify(int time , int i)
{
    if(C[time].pos >= q[i].l && C[time].pos <= q[i].r)
    {
        update(a[C[time].pos], -1);
        update(C[time].val, 1);
    }
    swap(a[C[time].pos] ,C[time].val);
}

int main()
{
    int n, Q, op, ll, rr;
    scanf("%d %d",&n,&Q);
    int sz = pow(n, 0.67);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        b[i] = a[i];
        col[i] = (i - 1)/ sz + 1;
    }
    int tot = 0, cnt = 0;
    for(int i = 1; i <= Q; ++i)
    {
        scanf("%d %d %d",&op, &ll, &rr);
        if(op == 1)
        {
            q[++tot].l = ll;
            q[tot].r = rr;
            q[tot].id = tot;
            q[tot].pre = cnt;
        }
        else{
            C[++cnt].pos = ll;
            C[cnt].val = rr;
            b[n + cnt] = rr;
        }
    }
    sort(q + 1, q + tot + 1, cmp);
    sort(b + 1, b + n + cnt + 1);
    int N = unique(b + 1, b + cnt + n + 1) - (b + 1);
    for(int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(b + 1, b + N + 1,a[i]) - b;
    }
    for(int i = 1; i <= cnt; ++i)
    {
        C[i].val = lower_bound(b + 1, b + N + 1, C[i].val) - b;
    }
    int l = 1, r = 0, time = 0;
    for(int i = 1; i <= tot; ++i)
    {
        while(l > q[i].l){l--; update(a[l], 1);}
        while(r < q[i].r){r++; update(a[r], 1);}
        while(r > q[i].r){update(a[r], -1); r--;}
        while(l < q[i].l){update(a[l], -1); l++;}
        while(time < q[i].pre){time++; modify(time, i);}
        while(time > q[i].pre){modify(time, i); time--;}
        int k = 1;
        while(ans[k]) k++;
        num[q[i].id] = k;
    }
    for(int i = 1; i <= tot; ++i)
    {
        cout << num[i] << '\n';
    }
}