翻车笔记_ 关于next数组的几道题[离线, 线段树, 树状数组, 清奇脑回路]

有些东西需要静下心来仔细琢磨一下…

果然早上交题容易上榜…祝我生日快乐qwq…

qwq

懵逼的 题目

有的时候我们会碰到一些题目, 要求颜色种类怎样怎样, 没出现过的怎样怎样

之前我一直想用线段树做…但是发现不会…就觉得线段树应该做不了来着…然后学了莫队, 哦这个应该用莫队做…直到现在, 才发现线段树/树状数组真的可以做…

先说一下nex[]数组的定义: nex[i]表示在i之后, 最左边的, 与a[i]相等的数的位置(如果没有就是n + 1)

然后这类题比较通用的一个做法就是: 把所有的询问离线, 按照左端点排序, 再用一个指针1 ~ n来扫描一遍, 对于指针扫到的位置, 计算他的贡献, 然后如果当前指针是某一个询问的左端点, 直接查询当前询问的右端点…
这样的好处就是当前指针之前, 也就是当前询问的左端点之前的影响, 都不用再考虑了

沙茶的 代码

H(工口)H(工口)的项链

(逃

这个题…树状数组做法还是挺有意思的…

搞一个空的树状数组

先对于每一个节点第一次出现的位置都修改为1

对于当前指针i扫到的位置, 查询所有询问左端点为i的询问的右端点, 在当前指针移动之前, 把nex[i]修改为1

用大佬的话说, 也就是 “保证每一种颜色第一次出现的位置被计入答案” (仔细琢磨一下…一旦当前指针扫过了当前的位置, 就意味着当前节点上的颜色不会对答案再产生影响了)

下面这个代码要是想去luogu交的话要开大数据范围…

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
/**************************************************************
Problem: 1878
User: Cansult
Language: C++
Result: Accepted
Time:1576 ms
Memory:8440 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXQ (200000 + 5)
#define MAXZ (1000000 + 5)
#define rint register int
#define cint const int
using namespace std;
struct question
{
int le, ri, bh;
}que[MAXQ];
int n, a[MAXN], b[MAXN], q, nex[MAXN], ans[MAXQ], last[MAXZ], maxz;
inline int lowbit(cint x)
{ return (x & (-x)); }
inline int max(cint x, cint y)
{
if (x > y)
return x;
else
return y;
}
inline void xg(cint x)
{
for (rint i = x; i <= n; i += lowbit(i))
++b[i];
}
inline int cx(cint x)
{
rint re = 0;
for (rint i = x; i; i -= lowbit(i))
re += b[i];
return re;
}
void init()
{
for (rint i = n; i >= 1; i--)
nex[i] = ((last[a[i]] == 0) ? (n + 1) : last[a[i]]), last[a[i]] = i;
for (rint i = 1; i <= maxz; i++)
if (last[i])
xg(last[i]);
}
bool cmp(const question x, const question y)
{ return x.le < y.le; }
int main()
{
scanf("%d", &n);
for (rint i = 1; i <= n; i++)
scanf("%d", &a[i]), maxz = max(maxz, a[i]);
init();
scanf("%d", &q);
for (rint i = 1; i <= q; i++)
scanf("%d%d", &que[i].le, &que[i].ri), que[i].bh = i;
sort(que + 1, que + q + 1, cmp);
for (rint i = 1, j = 1; i <= q; i++)
{
while (j < que[i].le)
xg(nex[j++]);
ans[que[i].bh] = cx(que[i].ri) - cx(que[i].le - 1);
}
for (rint i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}

HEOI2012 采(上)(厕所)

这个题和上面那个挺像的…都是把符合条件的第一个值计入答案

但是:

  • 不能把每一个首次出现某一颜色的位置置为1, 而是把首次出现某一颜色的位置的nex置为1(因为必须要有两个)…
  • 当前指针扫过一个位置的时候, 要把当前位置的nex置回0(因为那个位置已经不会被计入答案了)
  • 当前指针扫过一个位置的时候, 要把nexnex置为1

注意在树状数组修改的时候判断是否传入的位置是0

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
/**************************************************************
Problem: 2743
User: Cansult
Language: C++
Result: Accepted
Time:7520 ms
Memory:33448 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define lowbit(i) ((i) & (-(i)))
using namespace std;
struct question
{
int le, ri, bh;
}que[MAXN];
int n, c, q, a[MAXN], b[MAXN], nex[MAXN], ans[MAXN];
int cx(int le, int ri)
{
int re = 0;
for (int i = ri; i; i -= lowbit(i))
re += b[i];
for (int i = le - 1; i; i -= lowbit(i))
re -= b[i];
return re;
}
void xg(int wz, int zh)
{
for (int i = wz; i <= n; i += lowbit(i))
b[i] += zh;
}
void init()
{
int qwq[MAXN];
for (int i = 1; i < MAXN; i++)
qwq[i] = n + 1;
for (int i = n; i >= 1; i--)
nex[i] = qwq[a[i]], qwq[a[i]] = i;
bool vis[MAXN];
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++)
if (!vis[a[i]])
xg(nex[i], 1), vis[a[i]] = true;

}
bool cmp(question x, question y)
{ return x.le < y.le; }
int main(int argc, char const *argv[])
{
scanf("%d%d%d", &n, &c, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= q; i++)
scanf("%d%d", &que[i].le, &que[i].ri), que[i].bh = i;
init();
sort(que + 1, que + q + 1, cmp);
for (int i = 1, wz = 1; i <= n; i++)
{
while (wz <= q && que[wz].le < i)
++wz;
while (wz <= q && que[wz].le == i)
ans[que[wz].bh] = cx(que[wz].le, que[wz].ri), ++wz;
xg(nex[i], -1);
if (nex[nex[i]])
xg(nex[nex[i]], 1);
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}

RMQ Problem

这道题非常有意思…真的很有意思

还是按照上面的思路考虑…

  1. 我们先求出所有以1为左端点的询问的$mex$值(扫描一遍就可以了), 做一个线段树, 底层节点i存储的是以当前指针为左端点, 以i为右端点的$mex$
  2. 对于所有左端点和当前指针i相等的询问, 答案就是直接查询他右端点
  3. 移动当前指针, 考虑移动当前指针对答案造成的影响:
    • 首先去掉了一个数, 所有询问的$mex$肯定都不会变大, 只可能有一些区间的$mex$变小, 那么哪些询问的$mex$变大了呢? $[i, nex[i] - 1]$
    • 这样修改的时候我们就可以区间取一个$\min$, 我写了一个标记永久化线段树, 看上去比较优雅 Aufun: 这™写的什么玩意
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
/**************************************************************
Problem: 3339
User: Cansult
Language: C++
Result: Accepted
Time:2020 ms
Memory:17040 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define INF (0x7ffffff)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct question
{
int le, ri, bh;
}que[MAXN];
struct node
{
int le, ri, zh;
}b[MAXN << 2];
int n, a[MAXN], q, ans[MAXN], nex[MAXN], mex[MAXN];
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].zh = INF;
if (le == ri)
{
b[dq].zh = mex[le];
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].zh = min(b[dq].zh, zh);
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg(RS(dq), le, ri, zh);
else if (ri <= mi)
xg(LS(dq), le, ri, zh);
else
xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
}
int cx(int dq, int wz)
{
if (b[dq].le == b[dq].ri)
return b[dq].zh;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz > mi)
return min(b[dq].zh, cx(RS(dq), wz));
else
return min(b[dq].zh, cx(LS(dq), wz));
}
bool cmp(question x, question y)
{ return x.le < y.le; }
void init()
{
bool vis[MAXN];
memset(vis, false, sizeof(vis));
int dqmex = 0;
for (int i = 1; i <= n; i++)
{
vis[a[i]] = true;
while (vis[dqmex])
++dqmex;
mex[i] = dqmex;
}
}
void solve()
{
int qwq[MAXN];
for (int i = 0; i < MAXN; i++)
qwq[i] = n + 1;
for (int i = n; i >= 1; i--)
nex[i] = qwq[a[i]], qwq[a[i]] = i;
init();
js(1, 1, n);
sort(que + 1, que + q + 1, cmp);
for (int i = 1, le = 1; i <= q; i++)
{
while (le < que[i].le)
xg(1, le, nex[le] - 1, a[le]), ++le;
ans[que[i].bh] = cx(1, que[i].ri);
}
}
int main(int argc, char const *argv[])
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= q; i++)
scanf("%d%d", &que[i].le, &que[i].ri), que[i].bh = i;
solve();
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}

By 大沙茶 Cansult