LuoguP4137题解

发表于 更新于

莫队的简单应用

Description

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

Samples

Input #1

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

Output #1

1
2
3
4
5
1
2
3
0
3

Hint

对于30%的数据：1<=n,m<=1000

对于100%的数据：1<=n,m<=200000，0<=ai<=10^9，1<=l<=r<=n

Solution

看到没有强制在线, 第一眼就是莫队/cy

接下来就是考虑怎么写ADD和DEL了, 首先按照惯例记一个当前答案now和每个数的出现次数.

在ADD的时候, 如果这个数之前没有出现过, 那么应该和当前答案now比较一下:

  • 如果此数比now要大, 那么now依然是最优答案, 不必更新
  • 如果此数等于now(显然, 比now小的数是不存在的), 那么应该向上找出一个满足条件的次小值然后更新答案.

DEL就比较简单, 如果被DEL掉的数出现次数变为0, 那么应该和now比较一下, 如果比now小就需要更新了.

Code

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
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 2e5 + 10;
int n, m, cnt[MAXN], a[MAXN], ans[MAXN], Belong, now, ql = 1, qr;
struct NODE{int l, r, ser;}q[MAXN];
/* functions */
inline bool cmp(NODE a, NODE b) {
	if(a.l / Belong == b.l / Belong) return a.r < b.r;
	return a.l < b.l;
}
inline void DEL(int place) {
	if(((--cnt[a[place]]) == 0) && a[place] < now) now = a[place];
}
inline void ADD(int place) {
	if((++cnt[a[place]]) == 1) {
		int tmp = a[place];
		if(now == tmp) {
			while(++tmp) {if(cnt[tmp] == 0) {now = tmp; return ;}}
		}
	}
}
int main(int argc,char *argv[]){
	scanf("%d %d", &n, &m); Belong = std::sqrt(n);
	FOR(i, 1, n, 1) scanf("%d", &a[i]);
	FOR(i, 1, m, 1) {
		scanf("%d %d", &q[i].l, &q[i].r);
		q[i].ser = i;	
	}
	std::sort(q + 1, q + m + 1, cmp);
	FOR(i, 1, m, 1) {
		int L = q[i].l, R = q[i].r;
		while(ql < L) DEL(ql++);
		while(ql > L) ADD(--ql);
		while(qr < R) ADD(++qr);
		while(qr > R) DEL(qr--);
		ans[q[i].ser] = now;
	}
	FOR(i, 1, m, 1) printf("%d\n", ans[i]);
	return 0;
}

THE END