【训练记录】6.10 训练笔记

lxl 的题,不可做。

A

有一天,你得到了一个 $n$ 个点的树。

你感到很开心,于是记了下来和每一个点相邻的所有点中,编号最小的那个点和编号最大的那个点是什么。

然而一段时间后,你把那棵树弄丢了,但是你记录的信息还保存着。

你想得到原来的那棵树,于是尝试构造一个满足条件的解。

$1\leq n\leq 1000$ 。

写了个乱搞搞了 $50$ 分,赛后稍微魔改了一下就 $60$ 了。思路大概是跟 spfa 的松弛一样,每次用只含一个未盖信息的点增广。但很显然这种做法并不对。因为可能会存在一些点压根没在给出的信息表里出现过。于是就可以先连必要的信息,然后直接直接暴力连剩下的边。

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
#include <cstdio>

#include <cassert>

const int N = 1050 ;

int n ;
int ans ;
int cnt ;
int h, t ;
int q[N] ;
int fa[N] ;
bool vis[N] ;
int qnow[N] ;
int A[N][N] ;
int v[N][2] ;
int base[N][2] ;

bool no_sol(){ return puts("-1"), 0 ; }

int find(int x){
if (x == fa[x]) return x ;
return fa[x] = find(fa[x]) ;
}
void merge(int x, int y){
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 != f2)
fa[f2] = f1 ;
}
bool chk(int a, int b){
bool r1 = (base[a][1] > b && base[a][0] < b) ;
bool r2 = (base[b][1] > a && base[b][0] < a) ;
return (r1 && r2) ;
}
int main(){
scanf("%d", &n) ; h = 1 ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%d%d", &v[i][0], &v[i][1]) ;
if (v[i][0] == v[i][1]) q[++ t] = i ;
base[i][0] = v[i][0], base[i][1] = v[i][1] ;
}
int x, y ;
while (h <= t){
++ cnt ;
x = q[h ++] ;
y = v[x][0] ;
int &ya = v[y][0] ;
int &yb = v[y][1] ;
A[y][x] = A[x][y] = 1 ;
if (ya == yb) continue ;
if (ya == x) ya = yb, q[++ t] = y ;
else if (yb == x) yb = ya, q[++ t] = y ;
if (cnt >= 50000000) return no_sol() ;
}
for (int i = 1 ; i <= n ; ++ i) fa[i] = i ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n ; ++ j)
if (A[i][j]) ++ ans, merge(i, j) ;

for (int i = 1 ; i <= n ; ++ i) {
if (find(i) != find(base[i][0])){
merge(i, base[i][0]), ++ ans ; //printf("%d %d\n", i, base[i][0]) ;
A[i][base[i][0]] = A[base[i][0]][i] = 1 ;
}
if (find(i) != find(base[i][1])){
merge(i, base[i][1]), ++ ans ; //printf("%d %d\n", i, base[i][1]) ;
A[i][base[i][1]] = A[base[i][1]][i] = 1 ;
}
}
for (int i = 1 ; i <= n ; ++ i){
if (!A[i][base[i][0]]) return no_sol() ;
if (!A[i][base[i][1]]) return no_sol() ;
}
if (ans == n - 1){
sol : ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n ; ++ j)
if (A[i][j]) printf("%d %d\n", i, j) ;
return 0 ;
}
ans = n - 1 - ans ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n ; ++ j){
if (chk(i, j) && find(i) != find(j))
-- ans, A[i][j] = A[j][i] = 1, merge(i, j) ;
if (!ans) break ;
}
for (int i = 1 ; i <= n ; ++ i){
if (!A[i][base[i][0]]) return no_sol() ;
if (!A[i][base[i][1]]) return no_sol() ;
}
if (ans) return no_sol() ; else goto sol ;
return 0 ;
}

B

$2 \leq n \leq 10^{5}, 1 \leq m \leq 10^{5}$ 。

暴力比较好写,不难发现可以树上差分,之后肯定选经过的最多的那条边,这个过程可以枚举根然后 dfs。

但是不难发现这东西是可以简单 up and down 的,额外记录一个次大值就好了。写的时候有点小细节。

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
 
using IPT::qr ;
using IPT::qra ;
using IPT::qrs ;
using IPT::qrdb ;
using OPT::qw ;
using OPT::qwa ;
using OPT::qws ;

typedef long long ll ;

#define fr first
#define sc second

#define p_b push_back

typedef std :: vector <int> vint ;

int n, m ;
int sz[N] ;
int fa[N] ;
int son[N] ;
int dep[N] ;
int top[N] ;

ll ans ;
ll f[N] ;
ll g[N] ;
int h[N] ;
int ch[N] ;
int tag[N] ;

vint E[N] ;

void dfs1(int x, int da){
dep[x] = dep[da] + 1 ;
sz[x] = 1, fa[x] = da ;
for (auto y : E[x]){
if (y == da) continue ;
dfs1(y, x) ; sz[x] += sz[y] ;
if (sz[y] > sz[son[x]]) son[x] = y ;
}
}
void dfs2(int x, int tp){
top[x] = tp ;
if (son[x])
dfs2(son[x], tp) ;
for (auto y : E[x])
if (y != fa[x] && y != son[x]) dfs2(y, y) ;
}
int lca(int x, int y){
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]]) swap(x, y) ;
x = fa[top[x]] ;
}
if (dep[x] > dep[y])
swap(x, y) ; return x ;
}
void solve1(int x){
for (auto y : E[x]){
if (y != fa[x]){
solve1(y) ;
tag[x] += tag[y] ;
}
}
}
void solve2(int x){
ll sv = 0 ;
int mv = 0 ;
int cmv = 0 ;
for (auto y : E[x]){
if (y == fa[x])
continue ; solve2(y) ;
f[x] += f[y], sv += tag[y] ;
if (tag[y] > tag[mv]) cmv = mv, mv = y ;
else if (tag[y] > tag[cmv]) cmv = y ;
}
ch[x] = cmv, h[x] = mv ;
g[x] = sv, f[x] += sv - tag[mv] ;
}
void solve3(int x){
ans = min(ans, f[x]) ; ll t ;
for (auto y : E[x]){
if (y == fa[x]) continue ;
if (y == h[x])
t = -tag[ch[x]] ;
else t = -tag[y] ;
t += f[x] - f[y] ;
if (tag[y] > tag[h[y]])
f[y] += tag[h[y]], ch[y] = h[y], h[y] = y ;
else {
f[y] += tag[y] ;
if (tag[y] > tag[ch[y]]) ch[y] = y ;
}
f[y] += t ;
solve3(y) ;
}
}
int main(){
qr(n), qr(m) ;
int x, y, z ; tag[0] = 0 ;
for (int i = 1 ; i < n ; ++ i)
qr(x), qr(y), E[x].p_b(y), E[y].p_b(x) ;
dfs1(1, 0), dfs2(1, 1) ; ans = 1ll << 60 ;
for (int i = 1 ; i <= m ; ++ i){
qr(x), qr(y) ; z = lca(x, y) ;
tag[z] --, tag[z] --, tag[x] ++, tag[y] ++ ;
}
solve1(1) ;
solve2(1) ;
solve3(1) ;
qw(ans) ;
return 0 ;
}

C

对于这个数列的一段连续子序列 $a_l,a_{l+1},⋯,a_r$ ,如果存在一组整数 $x<y$ 使得 $x$ 和 $y$ 没有出现在 $a_l$ 到 $a_r$ 中,并且 $x+1,x+2,⋯,y−1x+1,x+2,⋯,y−1$ 都出现在了 $a_l$ 到 $a_r$ 中,那么我们称 $(x,y)$ 是一个合法的数对。

你需要处理 $m$ 次询问,每次询问 $l,r,c$ ,你需要回答对于 $a_l,a_{l+1},⋯,a_r$ 满足 $y=x+c$ 的合法的数对数量。

$1 \leq n, m, a_{i} \leq 1000000,2 \leq c \leq 10$ 。

毒瘤题…据说是 lxl 出给 SD 省队集训 2019 的题。

大概是有 $50$ 分左右是可以莫队的?然而正解是十分强大的线段树/BIT维护扫描线。

$9$ 个树状数组,分别维护对于每个左端点 $c-1=1,2,3\cdots9$ 时的答案,这样就可以直接用 BIT 计算出右端点。考虑左端点从右边到左边移动过程中,新加入一个数 $v$ 的时候,必然是原来的某些长度为 $t$ 的连续段变成了长度为 $t+k$ 的连续段。于是就考虑维护每个数随着左端点从右往左扫、上一次出现的位置。这样每次就可以把 $v-10\sim v+10$ 都扫一遍,记一下数字的出现情况,然后每次暴力找一下新产生的连续段,维护一下就好了。

写的时候大概有点细节,比如说按照 last[c] 排序后如果区间里存在两个 $v$ ,那么之后的贡献一定算过了。

于是最后的复杂度就是 $O(n\times c\log n)$ ,可以通过本题。

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>

#include <vector>

#include <algorithm>

const int N = 1000010 ;

using namespace std ;

namespace IPT {

const int L = 1 << 21;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) end = buf + fread(front = buf, 1, L, stdin);
return (front == end) ? -1 : *(front++);
}
template <typename T>
inline void qr(T &x) {
char ch = GetChar(), lst = 0; x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = GetChar();
if (lst == '-') x = -x;
}
template <typename T>
void qra(T *const __ary, int __n) {
for (int i = 0; i < __n; ++i) qr(__ary[i]);
}
template <typename T>
int qrs(T *p) {
T *beg = p;
do *p = GetChar(); while (!isalnum(*p));
do *(++p) = GetChar(); while (isalnum(*p));
*p = 0;
return p - beg;
}
template <typename T>
void qrdb(T &x) {
char ch = GetChar(), lst = 0; x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = GetChar(); }
if (ch == '.') {
ch = GetChar();
for (double t = 0.1; isdigit(ch); t *= 0.1) {
x += (t * (ch - '0'));
ch = GetChar();
}
}
if (lst == '-') x = -x;
}

} // namespace IPT

namespace OPT {

const int L = 30;
char buf[L];

template <typename T>
inline void qw(T x, const char aft = 0) {
if (x < 0) { x = -x, putchar('-'); }
int top = 0;
do { buf[++top] = static_cast<char>(x % 10 + '0'); } while (x /= 10);
while (top) putchar(buf[top--]);
if (aft) putchar(aft);
}
template <typename T>
void qwa(T *const __ary, int __n, const char e1, const char e2) {
int __dn = __n - 1;
for (int i = 0; i < __dn; ++i) qw(__ary[i], e1);
qw(__ary[__dn], e2);
}
template <typename T>
void qws(T *p, const int __n, const char ed) {
for (int i = 0; i < __n; ++i) putchar(p[i]);
if (ed) putchar(ed);
}
template <typename T>
void qws(T *p, const char ed) {
while (*p) putchar(*p++);
if(ed) putchar(ed);
}

} // namespace OPT

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;

struct qs{
int id ;
int val ;
int l, r ;
}q[N] ;
int n, m ;
int ans[N] ;
int base[N] ;
int last[N] ;
int _less[11] ;
int _more[11] ;
int _b[11][N] ;
vector <pair<int, int> > buc ;

#define fr first
#define sc second
#define m_k make_pair

inline bool comp(const qs &a, const qs &b){ return a.l > b.l ; }

inline void add(int c, int x, int v){
if (c > 10) return ;
for ( ; x <= n ; x += (x & -x)) _b[c][x] += v ;
}
inline int qry(int c, int x){
int ret = 0 ;
for ( ; x ; x -= (x & -x)) ret += _b[c][x] ; return ret ;
}
int x, y, z, l, r ;
int main(){
qr(n) ; qr(m) ;
fill(last, last + N, n + 1) ;
for (int i = 1 ; i <= n ; ++ i) qr(base[i]) ;
for (int i = 1 ; i <= m ; ++ i)
q[i].id = i, qr(q[i].l), qr(q[i].r), qr(q[i].val), q[i].val -- ;
sort(q + 1, q + m + 1, comp) ; int p = 1 ;
for (int i = n ; i >= 1 ; -- i){
fill(_less, _less + 11, 0) ;
fill(_more, _more + 11, 0) ; buc.clear() ;
for (int j = max(0, base[i] - 10) ; j <= base[i] + 10 ; ++ j)
buc.push_back(m_k(last[j], j)) ; buc.push_back(m_k(n + 1, 0)) ;
sort(buc.begin(), buc.end()) ; l = r = 0 ; add(1, i, 1) ;
for (auto j : buc){
z = l + r + 1 ;
x = j.fr, y = j.sc ;
if (y == base[i] || x > n){
add(l, x, 1), add(r, x, 1) ;
add(l + r + 1, x, -1) ;
break ;
}
if (y < base[i])
_less[base[i] - y] = 1 ;
else _more[y - base[i]] = 1 ;
if (_less[l + 1]){
add(l, x, 1) ;
while (_less[l + 1]) ++ l ;
add(l, x, -1) ;
}
if (_more[r + 1]){
add(r, x, 1) ;
while (_more[r + 1]) ++ r ;
add(r, x, -1) ;
}
if (z != l + r + 1)
add(z, x, -1), add(l + r + 1, x, 1) ;
}
while (q[p].l == i && p <= m)
ans[q[p].id] = qry(q[p].val, q[p].r), ++ p ;
last[base[i]] = i ;
}
qwa(ans + 1, m, '\n', '\n') ; return 0 ;
}