TIOJ-2185

發表於 更新於 Disqus：

$p_0,p_1,\cdots,p_{M-1}$是$M$個$1 \sim N$的排列，且對於 $i = 1, 2, 3, \cdots, M-1$，$p_i$是$p_{i-1}$交換第$x_i$和第$y_i$個數字得到的排列。假設依照字典序排序這$M$個排列後我們有$p_{a_1} \le p_{a_2} \le \cdots \le p_{a_M}$（若有一樣的排列，則讓下標較小的排列出現在前面），請輸出$a_1, a_2,\cdots,a_M$。

$N, M\le 10^5$

如果我們對每個排列Hash，我們就能在$\mathcal{O}(logn)$的時間知道誰比較大，考慮二分搜，因為只要當前的長度滿足兩個排列(hash值)相同，那在更短的長度肯定相同。所以可以用二分搜找出第一個hash值不一樣的index，找到後只要對他砸模逆元就能得知那一項是多少，如果index為n，那代表兩個排列相同。

至於交換操作，可以等價成兩個單點修改，然後我們只需要一個能夠二分搜的資料結構(線段樹!)。
可是開$M+1$顆線段樹顯然會炸，注意到我們每次只修改兩個點，所以可以使用持久化線段樹去維護他。

時間複雜度$\mathcal{O}(nlog^2n+mlogn)$，空間複雜度$\mathcal{O}(mlogn)$。

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int C = 998244353, N = 5e6 + 25;
struct PersistentSegtree {
	struct node {
		int l, r;
		int v;
		node(): l(-1), r(-1) { }
		node(int x): l(-1), r(-1), v(x) {}
	} arr[N];
	vector<int> root;
	int n, t;
	void pull(int p) {
		arr[p].v = (arr[arr[p].l].v + arr[arr[p].r].v) % MOD;
	}
	int build(int l, int r, vector<ll> &w) {
		int id = t++;
		if(l == r - 1) {
			arr[id] = node(w[l]);
			return id;
		}
		int m = l + r >> 1;
		arr[id].l = build(l, m, w);
		arr[id].r = build(m, r, w);
		pull(id);
		return id;
	}
	void init(int _n, vector<ll> &w) {
		n = _n;
		root.push_back(build(0, n, w));
	}
	int edt(int id, int old_id, int l, int r, int p, int v) {
		if(r <= p || p < l)
			return id;
		if(id == old_id)
			arr[id = t++] = node(arr[old_id]);
		if(l == r - 1)
			return arr[id].v = v, id;
		int m = l + r >> 1;
		arr[id].l = edt(arr[id].l, arr[old_id].l, l, m, p, v);
		arr[id].r = edt(arr[id].r, arr[old_id].r, m, r, p, v);
		pull(id);
		return id;
	}
	void edt(int t, int p, int v) {
		if(root.size() == t)
			root.push_back(edt(root[t - 1], root[t - 1], 0, n, p, v));
		else
			edt(root[t], root[t - 1], 0, n, p, v);
	}
	ll sum(int id, int ql, int qr, int l, int r) {
		if(qr <= l || r <= ql)
			return 0;
		if(ql <= l && r <= qr)
			return arr[id].v;
		int m = l + r >> 1;
		return sum(arr[id].l, ql, qr, l, m) + sum(arr[id].r, ql, qr, m, r);
	}
	ll sum(int t, int l, int r) {
		return sum(root[t], l, r, 0, n);
	}
	int que(int id1, int id2, int l, int r) {
		if(arr[id1].v == arr[id2].v)
			return r;
		if(l == r - 1)
			return l;
		int m = l + r >> 1;
		if(arr[arr[id1].l].v != arr[arr[id2].l].v)
			return que(arr[id1].l, arr[id2].l, l, m);
		return que(arr[id1].r, arr[id2].r, m, r);
	}
	int que(int a, int b) {
		return que(root[a], root[b], 0, n);
	}
} tree;

ll mpow(ll a, int b) {
	ll res = 1;
	for(a %= MOD; b; b >>= 1, a = a * a % MOD)
		if(b & 1)
			res= res * a % MOD;
	return res;
}

signed main() { EmiliaMyWife
	int n, q;
	cin >> n >> q;
	q--;
	vector<int> arr(n);
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	
	vector<ll> owo(n), gg(n);
	owo[0] = 1;
	for(int i = 1; i < n; i++)
		owo[i] = owo[i - 1] * C % MOD;
	for(int i = 0; i < n; i++)
		gg[i] = arr[i] * owo[i] % MOD;
	
	tree.init(n, gg);
	
	gg[n - 1] = mpow(owo[n - 1], MOD - 2);
	for(int i = n - 2; ~i; i--)
		gg[i] = gg[i + 1] * C % MOD;

	for(int i = 1, x, y; i <= q; i++) {
		cin >> x >> y; x--; y--;
		swap(arr[x], arr[y]);
		tree.edt(i, x, arr[x] * owo[x] % MOD);
		tree.edt(i, y, arr[y] * owo[y] % MOD);
	}

	vector<int> ans(q + 1);
	for(int i = 0; i <= q; i++)
		ans[i] = i;
	sort(ans.begin(), ans.end(), [&](int a, int b) {
		int w = tree.que(a, b);
		//cout << "comparing " << a << ' '<< b << ' ' << w << '\n';
		if(w == n)
			return a < b;
		return tree.sum(a, w, w + 1) * gg[w] % MOD < tree.sum(b, w, w + 1) * gg[w] % MOD;
	});
	for(int a : ans)
		cout << a << ' ';
	cout << '\n';
}