【赛题整理】APIO2019 简要题解

做了一下去年 APIO 的题。

口胡了一下发现可以 $60(=13+16+17+14)+100+40(=20+20)$,大概 $200$ 分拿个 Ag 的样子。

可能还是比较菜吧,唉。

哦,似乎从题目注释里面可以看出来这是毛子出的题。不明白毛子为什么又对这种题感兴趣了。

A Bridges

给定一张图,每条边有个限重。有两种操作,第一种是修改某条边的限重,第二种是询问从某个点以重量 $w$ 开始走,可以走到多少个点。$n\leq 5\times 10^4,1\leq q,m\leq 2\times 10^5$ 。

暴力分不说了,$16$ 分的链可以线段树上二分,$17$ 分的完全二叉树由于树高很低所以可以随便拿个什么数据结构来暴力维护。考虑只有询问操作的 $14$ 分。发现可以将全部的询问离线,然后和边放在一起按照权重从大到小进行排序,然后就可以直接拿个并查集来维护 size。不难理解这样做的正确性。

之后考虑满分…大概是没怎么见过的分块技巧。考虑对所有操作按时间分块,块大小为 $B$ 。那么前面的块里的修改就可以暴力改完,当前块内则按照上面 $\rm subtask4$ 的做法离线下来。注意到如果某条边在这个块里不会被修改就不管他,继续放在一起离线。对于每个询问,暴力每个修改操作,判断此时这条边是否有用。注意到此处应该按时间来对所有修改进行排序,这样就可以知道对于每条边只有最后一个修改才会有效。

这样就需要再维护一个可撤销的并查集,因为对于每一次询问都需要暴力那些修改,所以这样会带 $\log$ 。于是最后的复杂度就是

实测最后似乎在 $B=800\sim 1300$ 时效果最好。但是我写的时候由于用了 vectortuple ,常数比较大…

感觉思路还是挺直接的,想出分块来可能就 win 了。

「My-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
123
124
125
126
127
128
struct edg{
int x, y, z, id ;
edg (int a = 0, int b = 0, int c = 0, int d = 0){
x = a ; y = b ; z = c ; id = d ;
}
}E[N], e[N] ;
struct opt{
int x, y ;
int id, o ;
}op[N] ;
opt tmp[N] ;
opt pmt[N] ;
bool vis[N] ;
int n, m, q, k ;
int ans[N] ;
int sz[N] ;
int fa[N] ;
int L[N] ;
int R[N] ;
int cnt1 ;
int cnt2 ;
int ctn ;

vector <tuple<int, int, int> > stk ;

int find(int x){
while (x != fa[x])
x = fa[x] ; return x ;
}
void merge(int x, int y){
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 == f2) return ;
if (sz[f1] > sz[f2]){
stk.emplace_back(f1, f2, sz[f1]) ;
fa[f2] = f1, sz[f1] += sz[f2] ;
}
else{
stk.emplace_back(f2, f1, sz[f2]) ;
fa[f1] = f2, sz[f2] += sz[f1] ;
}
}
bool comp_y(opt a, opt b){ return a.y > b.y ; }
bool comp_val(edg a, edg b){ return a.z > b.z ; }
void clear(int yz){
while (stk.size() > yz){
int x, y, z ;
tie(x, y, z) = stk.back() ;
sz[x] = z ; fa[y] = y ; stk.pop_back() ;
}
}
int main(){
cin >> n >> m ; int x, y, z ;
for (int i = 1 ; i <= m ; ++ i){
x = qr() ;
y = qr() ;
z = qr() ;
E[i] = edg(x, y, z) ;
}
cin >> q ; k = q / M + 1 ;
for (int i = 1 ; i <= k ; ++ i)
L[i] = R[i - 1] + 1, R[i] = L[i] + M - 1 ;
if (L[k] > q) -- k ; R[k] = min(R[k], q) ;
// debug(L, 1, k) ;
// debug(R, 1, k) ;
for (int i = 1 ; i <= q ; ++ i){
op[i].id = i, op[i].o = qr() ;
op[i].x = qr(), op[i].y = qr() ;
}
for (int i = 1 ; i <= k ; ++ i){
for (int j = 1 ; j <= n ; ++ j)
fa[j] = j, sz[j] = 1 ; cnt1 = cnt2 = 0 ;
for (int j = 1 ; j <= m ; ++ j) vis[j] = 0 ;
for (int j = L[i] ; j <= R[i] ; ++ j){
if (op[j].o == 1)
vis[op[j].x] = 1, tmp[++ cnt1] = op[j] ;
else pmt[++ cnt2] = op[j] ;
}
// debug(vis, 1, m) ;
ctn = 0 ; int p = 1 ;
for (int j = 1 ; j <= m ; ++ j)
if (!vis[j]) e[++ ctn] = E[j] ;
// cout << ctn << '\n' ;
sort(e + 1, e + ctn + 1, comp_val) ;
sort(pmt + 1, pmt + cnt2 + 1, comp_y) ;
for (int j = 1 ; j <= cnt2 ; ++ j){
// debug(pmt[j].x, ' ') ;
// debug(pmt[j].y, ' ') ;
// debug(p) ;
while (e[p].z >= pmt[j].y && p <= ctn)
merge(e[p].x, e[p].y), ++ p ;
// debug(fa, 1, n) ;
// debug(sz, 1, n) ;
int t = stk.size() ;
for (int h = cnt1 ; h >= 1 ; -- h){
if (tmp[h].id <= pmt[j].id && vis[tmp[h].x]){
vis[tmp[h].x] = 0 ;
if (tmp[h].y >= pmt[j].y)
merge(E[tmp[h].x].x, E[tmp[h].x].y) ;
}
}
// puts("**************************") ;
// debug(vis, 1, m) ;
// debug(fa, 1, n) ;
// debug(sz, 1, n) ;
// puts("- - - - - - - - - - - - - - -") ;
for (int h = 1 ; h <= cnt1 ; ++ h)
if (vis[tmp[h].x] && E[tmp[h].x].z >= pmt[j].y)
merge(E[tmp[h].x].x, E[tmp[h].x].y) ;
for (int h = 1 ; h <= cnt1 ; ++ h)
if (!vis[tmp[h].x]) vis[tmp[h].x] = 1 ;
// puts("********&&&&&&&&&&******") ;
// debug(vis, 1, m) ;
// debug(fa, 1, n) ;
// debug(sz, 1, n) ;
// puts("- - - -^^^^^^^^^- - - - - -") ;
// cout << find(pmt[j].x) << '\n' ;
ans[pmt[j].id] = sz[find(pmt[j].x)] ;
clear(t) ;
}
for (int j = 1 ; j <= cnt1 ; ++ j)
E[tmp[j].x].z = tmp[j].y ;
clear(0) ;
}
for (int i = 1 ; i <= q ; ++ i)
if (ans[i]) printf("%d\n", ans[i]) ;
return 0 ;
}

B Device

给定一条数轴和 $A,B$。

数轴上的每个位置都可以产生一个数对 $(x,y)$ ,其中 $x = ((t + \left\lfloor \frac{t}{B} \right\rfloor) \bmod A),y = (t \bmod B)$。

在给定 $n$ 个连续区间 $[l_i,r_i]$ 。求所有区间里有多少本质不同的位置。本质不同指产生的数对不同。

$1\le n\le 10^6,1\le A,B\le 10^{18},0\le l_i\le r_i\le 10^{18},r_i<l_{i+1}$。

大概是场上最简单的题了。推的时候可能需要细心一点。然后以下是我 xjb 推的过程

$(1)-(2)$ 可以得到

从而

那么也就是说需要两个 $t$ 之间满足

于是就可以先判一下是否存在区间长度 $\geq \Delta t$ 。如果有答案就是 $\Delta t$ ,否则考虑每个区间都可以对其取模,之后就会变成一段或者两段(取决于取模完后 $l,r$ 的大小关系),然后就变成经典的求一个区间内到底覆盖了多少个位置的问题。

「My-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

int n ;
ll ans ;
ll res ;
ll A, B ;
int tot ;
struct rgs{
ll l, r ;
rgs (ll a = 0, ll b = 0){ l = a, r = b ; }
}base[N] ;

ll gcd(ll x, ll y){
return y ? gcd(y, x % y) : x ;
}
il bool comp(const rgs & a, const rgs & b){
return a.l == b.l ? a.r < b.r : a.l < b.l ;
}
int main(){
// freopen("05", "r", stdin) ;
// freopen("1.out", "w", stdout) ;
cin >> n >> A >> B ; tot = n ;
res = A / gcd(A, B + 1), res *= B ;
// cout << res << '\n' ;
for (int i = 1 ; i <= n ; ++ i){
base[i].l = qr(), base[i].r = qr() ;
if (base[i].r - base[i].l + 1 >= res)
return cout << res << '\n', 0 ;
base[i].r %= res ; base[i].l %= res ;
if (base[i].l > base[i].r){
base[++ tot] = rgs(base[i].l, res - 1) ;
base[i] = rgs(0, base[i].r) ;
}
}
// for (int i = 1 ; i <= tot ; ++ i)
// cout << base[i].l << " " << base[i].r << '\n' ;
n = tot ;
sort(base + 1, base + n + 1, comp) ;
ll l = base[1].l, r = base[1].r ;
for (int i = 2 ; i <= n ; ++ i){
if (base[i].l > r)
ans += r - l + 1, l = base[i].l ;
r = max(r, base[i].r) ;
}
ans += r - l + 1 ;
cout << ans << '\n' ; return 0 ;
}

C Lamps

给定一条长为 $n+1$ 的数轴,每个 $[i,i+1]$ 之间都有一盏编号为 $i$ 的灯,如果亮则意味着 $i,i+1$ 连通,否则不连通。有两种操作,每次会选择某盏灯将其状态取反,或者询问两个点 $a,b$ 从第一次操作开始有多少次操作是灭的。

$n,q\leq 3\times 10^5$ 。

orz 神仙题,大概是一堆 trick 的堆砌,然后我就啥都不会 QAQ。

考虑这东西一点也不好维护,于是就将信息抽象到二维上。具体的,可以将点对 $(a,b)$ 作为询问 $(a,b)$ 的答案。

之后考虑怎么维护。首先可以用珂朵莉树那样用 set 维护亮着的连续段。之后假设取反了 $i$ 号灯,那么假设与 $i$ 相连的连通块最左边是 $l$,与 $i+1$ 相连的连通块最左边是 $r$。那么考虑每次实际上是让

这些点连通起来。这在二维平面上就是一个左上角为 $(l,i+1)$ ,右下角为 $(i,r)$ 的矩阵。考虑如何对这个矩阵搞事情,发现很难维护这个矩阵里的连通性,于是考虑差分。具体的,如果设总时间为 $t$ ,当前时间为 $t_0$,那么可以考虑在每次开的时候将这个矩阵加上 $t-t_0$ ,关的时候减去 $t-t_0$ ,这样两次修改的 $\Delta$ 就是 $t-t_1-(t-t_2)=t_2-t_1$ 。由于一盏灯每次只会进行取反操作,所以正确性可以保证。

同时,考虑这样做的话,询问 $(a,b)$ 时可能还是两者之间此时依旧是连通的。为了计算这一部分贡献需要让询问一开始就减去 $t-t_0$ 。

然后就是一个朴素的矩阵加,单点询问了。将每个修改差分成四个之后可以直接跑 CDQ。

这样做的复杂度是 $O((n+4\cdot q)\log n\log q)$ 的。这东西…也不知道为什么就能跑得过 $1e6$ 。反正常数很恐怖。

似乎是有把一个修改拆成俩修改再 CDQ 的,这样做直接节约了一倍常数。但是我并不知道那是个什么原理…

「My-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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
int tot ;
int n, q ;
int ans[N] ;
int _bit[N] ;
int base[N] ;
char Inp[50] ;
struct qss{
int id, isq ;
int x, y, v ;
qss (int a = 0, int z = 0, int b = 0, int c = 0, int d = 0){
id = a ; isq = z ; x = b ; y = c ; v = d ;
}
}qs[N], tmp[N] ;

bool comp(const qss & a, const qss & b){ return a.id < b.id ; }

void ins(int x, int v){
for ( ; x <= n + 1 ; x += (x & -x)) _bit[x] += v ;
}
int qry(int x){
int ret = 0 ;
for ( ; x ; x -= (x & -x)) ret += _bit[x] ;
return ret ;
}
void cdq(int l, int r){
// cout << l << " " << r << '\n' ;
if (l == r) return ;
int mid = (l + r) >> 1 ;
int tl = l, tr = mid + 1 ;
cdq(l, mid) ; cdq(mid + 1, r) ;
while (tr <= r){
while (tl <= mid && qs[tl].x <= qs[tr].x){
if (!qs[tl].isq) ins(qs[tl].y, qs[tl].v) ; ++ tl ;
}
if (qs[tr].isq){
// debug(qs[tr].x) ;
// debug(qs[tr].y) ;
// debug(
ans[qs[tr].id] += qry(qs[tr].y) ;
// ) ;
} ++ tr ;
}
while (tl > l)
if (!qs[-- tl].isq) ins(qs[tl].y, - qs[tl].v) ;
tr = mid + 1 ; int tot = 0 ;
while (tl <= mid || tr <= r){
if (tr <= r && qs[tl].x >= qs[tr].x) tmp[++ tot] = qs[tr ++] ;
if (tl <= mid && qs[tl].x <= qs[tr].x) tmp[++ tot] = qs[tl ++] ;
if (tl <= mid && tr > r) tmp[++ tot] = qs[tl ++] ;
if (tr <= r && tl > mid) tmp[++ tot] = qs[tr ++] ;
}
for (int i = l ; i <= r ; ++ i) qs[i] = tmp[i - l + 1] ;
}
struct seg{
int id, l, r ;
const bool operator <(const seg &t)
const { return t.l > l ; }
seg (int L = 0, int R = 0, int idd = 0){
l = L ; r = R ; id = idd ;
}
};
int cnt ;
set <seg> s ;

int main(){
cin >> n >> q ;
int x, y, b, c ;
s.insert(seg(0, 0, 0)) ;
for (int i = 1 ; i <= n + 1 ; ++ i)
s.insert(seg(i, i, ++ cnt)) ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%1d", &base[i]) ;
if (base[i]){
auto l = -- s.lower_bound(seg(i, 0, 0)) ;
auto r = s.lower_bound(seg(i + 1, 0, 0)) ;
if (l -> r < i) ++ l ; int L = l->l, R = r->r ;
//cout << L << " " << R << '\n' ;
++ tot, qs[tot] = qss(tot, 0, L, i + 1, q) ;
++ tot, qs[tot] = qss(tot, 0, i + 1, i + 1, -q) ;
++ tot, qs[tot] = qss(tot, 0, L, R + 1, -q) ;
++ tot, qs[tot] = qss(tot, 0, i + 1, R + 1, q) ;
s.erase(l) ;
if (r != l)
s.erase(r) ;
s.insert(seg(L, R, ++ cnt)) ;
}
}
memset(ans, -1, sizeof(ans)) ;
for (int i = 1 ; i <= q ; ++ i){
scanf("%s", Inp + 1) ;
if (Inp[1] == 'q'){
++ tot ;
x = qr(), y = qr() ;
auto l = -- s.lower_bound(x) ;
auto r = -- s.lower_bound(y) ;
if (l -> r < x) ++ l ;
if (r -> r < y) ++ r ;
qs[tot] = qss(tot, 1, x, y, 0) ;
ans[tot] = (l == r) ? -(q - i) : 0 ;
}
else {
x = qr() ;
if (base[x]){
auto y = -- s.lower_bound(seg(x, 0, 0)) ;
if (y -> r < x) ++ y ; int l = y -> l, r = y -> r ;
// cerr << l << " " << r << '\n' ;
++ tot, qs[tot] = qss(tot, 0, l, x + 1, i - q) ;
++ tot, qs[tot] = qss(tot, 0, x + 1, x + 1, q - i) ;
++ tot, qs[tot] = qss(tot, 0, l, r + 1, q - i) ;
++ tot, qs[tot] = qss(tot, 0, x + 1, r + 1, i - q) ;
s.erase(y) ;
s.insert(seg(l, x, ++ cnt)) ;
s.insert(seg(x + 1, r, ++ cnt)) ;
}
else {
auto l = -- s.lower_bound(seg(x, 0, 0)) ;
auto r = -- s.lower_bound(seg(x + 1, 0, 0)) ;
if (l -> r < x) ++ l ;
if (r -> r < x + 1) ++ r ;
int L = l -> l, R = r -> r ;
// cerr << L << " " << R << '\n' ;
++ tot, qs[tot] = qss(tot, 0, L, x + 1, q - i) ;
++ tot, qs[tot] = qss(tot, 0, x + 1, x + 1, i - q) ;
++ tot, qs[tot] = qss(tot, 0, L, R + 1, i - q) ;
++ tot, qs[tot] = qss(tot, 0, x + 1, R + 1, q - i) ;
s.erase(l) ;
if (l != r)
s.erase(r) ;
s.insert(seg(L, R, ++ cnt)) ;
}
base[x] ^= 1 ;
}
}
// for (int i = 1 ; i <= tot ; ++ i)
// cout << qs[i].x << " " << qs[i].y << " " << qs[i].v << '\n' ;
// debug(tot) ;
cdq(1, tot) ;
for (int i = 1 ; i <= tot ; ++ i)
if (~ans[i]) printf("%d\n", ans[i]) ;
return 0 ;
}