Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP5064 [Ynoi2014] 等这场战争结束之后

Posted on In
Symbols count in article: 4k Reading time ≈ 4 mins.

做了那么久的水题，来道有难度的

问题

等这场战争结束之后

题意和永无乡类似，多了一个回退操作，支持回到第 $x$ 次操作后的状态， $n, m \le 10^5$ ，时间 $500ms$ ，空间 $20MB$

先不管时空，看操作

回退

先看比永无乡多的这个操作，说是回退，但其实又和一般回退不同，因为它是“回到第 $x$ 次操作后的状态”，不只是这期间的加边要撤销，这期间的“回到……”也要撤销掉

那咋办呢？考虑建树，具体地，建出 $0$ 号点为根，对于第 $i$ 次操作（它的编号为 $i$ ），如果它是加边，就让它的父亲为 $i - 1$ ；如果是回到 $x$ ，就让它的父亲为 $x$ ；如果是询问，其实可以打标记的，但是最坏情况下对时空都没有优化，所以还是直接让它的父亲为 $i - 1$ 即可

这样只要dfs遍历一遍操作树，根据节点信息操作，就可以得到答案，时空消耗均为 $O(n)$ ，可以接受

操作

现在来看如何根据节点信息操作，首先这是dfs，所以我们的操作必须支持撤销，且能够在线维护加边（联通）和查询第 $k$ 小

可撤销的查询第 $k$ 小可以考虑可持久化平衡树，但sm的空间（ $20MB$ ）不允许，考虑分块，对值域进行分块，记得离散化，单次 $O(\sqrt{n})$

加边很明显用并查集，不打路径压缩，按秩合并单次询问可以做到 $O(\log n)$

时空

现在来看时空限制，明显时空都是 $O(n\sqrt{n})$ ，一般的题也就过去了，但这个出题人不一般

时间 $500ms$ 没问题，但 $20MB$ 的空间只允许 $n \log n$ ，shit

尝试卡块数，设为 $B$ ，发现：

  • $B \le 25$ 时， $96pts$ TLE
  • $25 < B \le 27$ ， $92pts$ TLE + WA（不知道为啥WA）
  • $B > 27$ ， $88pts$ MLE

这就是由乃oi吗，i了i了

但是，我们发现 short 可以存 $2^{15} - 1$ ，大概 $3 \times 10^4$ ，而 $n / B$ 在 $B > 10$ 的情况下不大于 short 所以可以开成 short ，空间变为 $O(\frac{n B}{2})$ ，计算出 $20MB = 20 * 1024 * 1024B$ ， $n \le 10^5$ ，不难发现 $20 * 1024 * 1024 / 2 / n$ ， $B$ 大概可以开 $100$ ，但别的数组也要空间呀，所以 $B$ 开个 $50$ 差不多

调试

调试时遇到一些问题，莫名其妙输出 $0$ ，样例太水了，手打了 $makedate$ 和脚本对拍：

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
//make_date.cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
	srand(time(0));
	int n = rand() % 100000, m = rand() % 100000;
	cout << n << " " << m << endl;
	for (int i = 1; i <= n; ++i)
	{
		int a = rand() % 10000;
		cout << a << " ";
	}
	cout << endl;
	for (int i = 1; i <= m; ++i)
	{
		int op = rand() % 3 + 1;
		cout << op << " ";
		if (op == 2)
		{
			int x = rand() % i;
			cout << x << endl;
		}
		else
		{
			int x = rand() % n + 1;
			int y = rand() % (i / 2 + 1) + 1;
			cout << x << " " << y << endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
#check.bat
g++ -o std std.cpp
g++ -o t t.cpp
g++ -o make_d make_d.cpp
:label
.\make_d > t.in
.\t < t.in > t.out
.\std < t.in > t.ans
fc /w /a t.out t.ans
if "%errorlevel%" == "0" goto label

调出来发现是 ask 函数里面 for (int i = (y - 1) * blk + 1, t = y * blk; i <= t && k; ++i) 写成了 for (int i = (y - 1) * blk + 1, t = y * num; i <= t && k; ++i) 导致询问大小只有 $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
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
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1e5 + 5, B = 50;
int si[N], fa[N];
int blk, num;
short cnt[N][B + 5]; //short立大功
struct Question
{
    int typ, x, y, ans;
} que[N];
struct Node
{
    int val, id;
    bool operator < (const Node &t) const
    {
        return val < t.val;
    }
} p[N];
struct Edge
{
    int ne, ver;
} e[N];
int h[N], idx = 0;
void add(int x, int y)
{
    e[idx] = {h[x], y}, h[x] = idx++;
}
int find(int x)
{
    return x == fa[x] ? x : find(fa[x]);
}
void merge(int x, int y, int typ)
{
    if (si[x] > si[y])
        swap(x, y);
    fa[x] = (typ == 1 ? y : x), si[y] += si[x] * typ;
    for (int i = 1; i <= num; ++i)
        cnt[y][i] += cnt[x][i] * typ;
}
int ask(int x, int k)
{
    if (k > si[x = find(x)])
        return -1;
    int y = 0, res = 0;
    for (int i = 1; i <= num && !y; ++i)
        if (k > cnt[x][i])
            k -= cnt[x][i];
        else
            y = i;
    for (int i = (y - 1) * blk + 1, t = y * blk; i <= t && k; ++i)
        if (find(p[i].id) == x)
            --k, res = p[i].val;
    return res;
}
void dfs(int x)
{
    bool typ1 = false;
    if (que[x].typ == 1)
    {
        que[x].x = find(que[x].x), que[x].y = find(que[x].y);
        if (que[x].x ^ que[x].y) //就是que[x].x != que[x].y
            typ1 = true, merge(que[x].x, que[x].y, 1);
    }
    else if (que[x].typ == 3)
        que[x].ans = ask(que[x].x, que[x].y);
    for (int i = h[x]; i != -1; i = e[i].ne)
        dfs(e[i].ver);
    if (typ1)
        merge(que[x].x, que[x].y, -1);
}
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    blk = n / B; //这里B是块数,blk是块长
    if (!blk)
        blk = 1;
    num = (n - 1) / blk + 1;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &p[i].val);
        p[i].id = i;
        si[fa[i] = i] = 1;
    }
    //离散化
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; ++i)
        ++cnt[p[i].id][(i - 1) / blk + 1];
    //操作树
    for (int i = 0; i <= m; ++i)
        h[i] = -1;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &que[i].typ);
        if (que[i].typ == 2)
        {   
            scanf("%d", &que[i].x);
            add(que[i].x, i);
        }
        else
        {
            add(i - 1, i);
            scanf("%d %d", &que[i].x, &que[i].y);
        }
    }
    dfs(0);
    for (int i = 1; i <= m; ++i)
        if (que[i].typ == 3)
            printf("%d\n", que[i].ans);
    return 0;
}