GXOI2019

GXOI2019

与或和

还是考虑分别考虑每一位, 然后这道题的本质就变成了求全是一的子矩阵的个数. 分别考虑每一列, 设\(a_i\)为对于这一列的第\(i\)行最多向前延伸的格数, 并且使得这些格子都是一, 则问题变成求下式 : \[ \sum _ {i = 1} ^ n\sum_{j = i} ^ n\min_{i \le k \le j}\{a_k\} \] 单调栈求一下对于每个\(a_i\)左边第一个比它,右边第一个小于等于它的值的位置.

复杂度\(O(n^2 \log W)\).(\(W\)为值域)

代码:

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
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) (int)(x.size())

typedef long long ll;

using namespace std;

const int maxn = 1e3 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int n, a[maxn][maxn], tMatrix, ansand, ansor;
bool b[maxn][maxn], c[maxn][maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int mul(int a, int b, int c) { return 1ll * a * b % P * c % P; }

inline int Solve(bool a[maxn][maxn], int rnt = 0) {
static int g[maxn], st[maxn], top, l[maxn], r[maxn];
memset(g, 0, sizeof(g)); g[0] = g[n + 1] = -inf;
// cerr << "--------------------------------" << endl;
/*
rep(i, 1, n) {
rep(j, 1, n) cerr << a[i][j] << " ";
cerr << endl;
}
*/
// cerr << "Start : " << endl;
rep(j, 1, n) {
rep(i, 1, n) g[i] = a[i][j] ? g[i] + 1 : 0;
// rep(i, 1, n) cerr << g[i] << " ";
// cerr << endl << endl << endl;
int CON = 0;
st[top = 1] = 0;
rep(i, 1, n) {
while(g[st[top]] >= g[i]) top--;
l[i] = st[top] + 1; st[++top] = i;
}
st[top = 1] = n + 1;
dep(i, n, 1) {
while(g[st[top]] > g[i]) top--;
r[i] = st[top] - 1; st[++top] = i;
rnt = pls(rnt, mul(mul(r[i] - i + 1, i - l[i] + 1), g[i]));
// cerr << "l[" << i << "] = " << l[i] << ", r[" << i << "] = " << r[i] << endl;
// CON += r[i] - i + 1, i - l[i] + 1;
}
// cerr << CON << endl;
} return rnt;
}

int main() {
n = read();
rep(i, 1, n) rep(j, 1, n) a[i][j] = read();
tMatrix = mul(n * (n + 1) / 2, n * (n + 1) / 2);
// cerr << tMatrix << endl;
rep(t, 0, 30) {
rep(i, 1, n) rep(j, 1, n) b[i][j] = a[i][j] >> t & 1;
rep(i, 1, n) rep(j, 1, n) c[i][j] = b[i][j] ^ 1;
int base = (1 << t) % P;
// cerr << base << endl;
int A = Solve(b), B = Solve(c);
// cerr << "A = " << A << ", B = " << B << endl;
ansand = pls(ansand, mul(base, A));
ansor = pls(ansor, mul(base, dec(tMatrix, B)));
// cerr << "OK ON " << t << endl;
} cout << ansand << " " << ansor;
return 0;
}

宝牌一大堆

不玩雀魂,看不懂题面,告辞.

特技飞行

首先这是一个二合一..

\(a,b\)\(c\)的贡献是两个相互独立的贡献,可以分别求解.并且得分的极值只取决于\(a,b\),和\(c\)无关.

先考虑\(a,b\)贡献的极值:

因为对向交换擦身而过的次数总和是个定值,所以我们要求的就是在满足条件的情况下最大最小化对向交换擦身而过的次数就好了,这里我们考虑只对向交换.

对向交换的最大次数:

这个就是交点的个数,也就是说我们只要一直对向交换最后的位置一定是合法的.

这个可以感性理解一下就是:最上面和最下面的直线一直对向交换形成的轨迹一定是一个凸壳,所以这两个的位置一定是合法的,然后我们去掉这两条直线后问题又变成了原问题.所以最后的位置一定是合法的.

对向交换的最小次数:

将初始位置和结束位置离散化后的数组的每个置换,对于每个置换的最小交换次数为置换大小-1,且每个置换之间的是互不影响的,所以最小次数就是交点数-置换数.

再考虑\(c\)的贡献:

Solution1:

直接上\(\text{KDT}\)就好了.

Solution2:

将坐标系旋转\(45\)°后,哈曼顿限制的区域就是一个正方形,直接二维数点就好了.

我这种辣鸡肯定写KDT啊...

代码:

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
/*
* 3085.cpp
* This file is part of 3085
*
* Copyright (C) 2019 - ViXbob
*
* 3085 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3085 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3085. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-12;
const double ze = 0;

int n, A, B, C, sx, ex, sy[maxn], ey[maxn], pos[maxn], coc, to[maxn], cnt, tot, k, R, inq[maxn];
ll ans = 0;
bool vis[maxn], D;
set<int> s;
map<int, int> mp;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int dcmp(double x, double y) { return fabs(x - y) <= eps ? 0 : (x < y ? -1 : 1); }

struct Point {
double x[2];
Point(double a = 0, double b = 0) { x[0] = a; x[1] = b; }
bool operator < (const Point &t) const {
return x[D] < t.x[D] || (x[D] == t.x[D] && x[D ^ 1] < t.x[D ^ 1]);
}
double operator ^ (const Point &t) const { return x[0] * t.x[1] - x[1] * t.x[0]; }
Point operator - (const Point &t) const { return Point(x[0] - t.x[0], x[1] - t.x[1]); }
inline void print() { printf("%.10lf %.10lf\n", x[0], x[1]); }
} a[maxn];

Point calc(double sy0, double ey0, double sy1, double ey1) {
Point A(sx, sy0), B(ex, ey0), C(sx, sy1), D(ex, ey1);
double S0 = (C - A) ^ (B - A), S1 = (B - A) ^ (D - A);
double xp = sx + (ex - sx) * S0 / (S0 + S1);
double Fr = (xp - sx) * ey0 + (ex - xp) * sy0;
double Se = ex - sx;
return Point(xp, Fr / Se);
}

namespace KDT {
struct Node {
Node *ls, *rs;
double mxx, mnx, mxy, mny, x, y;
int siz, id, del;
Node(double a = 0, double b = 0, int c = 0) {
mxx = mnx = x = a;
mxy = mny = y = b;
siz = 1; ls = rs = NULL;
id = c; del = 0;
}

inline void pushup(Node* &t) {
mxx = max(mxx, t -> mxx);
mnx = min(mnx, t -> mnx);
mxy = max(mxy, t -> mxy);
mny = min(mny, t -> mny);
siz += t -> siz;
}

inline void update() {
mxx = mnx = x;
mxy = mny = y;
siz = !inq[id];
if(ls) pushup(ls);
if(rs) pushup(rs);
}

inline double mnDis(Node* &x) const {
double a = max(mnx - x -> x, ze) + max(x -> x - mxx, ze);
double b = max(mny - x -> y, ze) + max(x -> y - mxy, ze);
return a + b;
}

inline double mxDis(Node* &x) const {
double a = max(fabs(x -> x - mnx), fabs(x -> x - mxx));
double b = max(fabs(x -> y - mny), fabs(x -> y - mxy));
return a + b;
}
} *root, *now;

inline Node* Build(int l, int r, bool type) {
if(l > r) return NULL;
int mid = l + r >> 1; D = type;
nth_element(a + l, a + mid, a + 1 + r);
Node *rnt = new Node(a[mid].x[0], a[mid].x[1], mid);
rnt -> ls = Build(l, mid - 1, type ^ 1);
rnt -> rs = Build(mid + 1, r, type ^ 1);
rnt -> update(); return rnt;
}

inline int query(Node* &x) {
int rnt = 0;
// Point(x -> x, x -> y).print();
if(dcmp(fabs(x -> x - now -> x) + fabs(x -> y - now -> y), R) <= 0 && !inq[x -> id])
rnt++, inq[x -> id] = 1;
if(x -> ls && dcmp(x -> ls -> mnDis(now), R) <= 0 && x -> ls -> siz) {
if(dcmp(x -> ls -> mxDis(now), R) <= 0) rnt += x -> ls -> siz, x -> ls -> siz = 0;
else rnt += query(x -> ls);
}
if(x -> rs && dcmp(x -> rs -> mnDis(now), R) <= 0 && x -> rs -> siz) {
if(dcmp(x -> rs -> mxDis(now), R) <= 0) rnt += x -> rs -> siz, x -> rs -> siz = 0;
else rnt += query(x -> rs);
}
x -> update(); return rnt;
}
}

using KDT :: root;
using KDT :: now;
using KDT :: Node;

int main() {
// freopen("aero20.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); A = read(); B = read(); C = read(); sx = read(); ex = read();
rep(i, 1, n) sy[i] = read();
rep(i, 1, n) pos[++coc] = ey[i] = read(), mp[ey[i]] = sy[i];
sort(pos + 1, pos + 1 + coc);
rep(i, 1, n) to[i] = lower_bound(pos + 1, pos + 1 + coc, ey[i]) - pos;
rep(i, 1, n) if(!vis[i]) {
cnt++;
for(int j = i; !vis[j]; j = to[j]) vis[j] = 1;
}
rep(i, 1, n) {
if(i > 1) {
auto it = s.upper_bound(ey[i]);
for( ; it != s.end(); ++it) {
a[++tot] = calc(sy[i], ey[i], mp[*it], *it);
// a[tot].print();
}
}
s.insert(ey[i]);
}
// return 0;
root = KDT :: Build(1, tot, 0);
k = read();
// cerr << k << endl;
rep(i, 1, k) {
// cerr << "---------------------" << endl;
int x = read(), y = read(); R = read();
now = new Node(x, y);
ans += KDT :: query(root);
delete now;
// cerr << ans << endl;
}
// cerr << ans << endl;
// cerr << tot << endl;
ll ans0 = ans * C + tot * A, ans1 = ans * C + (n - cnt) * A + (tot - n + cnt) * B;
cout << min(ans0, ans1) << " " << max(ans0, ans1) << endl;
return 0;
}

逼死强迫症

首先知道如果只能放\(n\)\(1\times 2\)的砖块的话,方案数就是\(f[n+1]\)\(f\)为斐波那契数列.

我们定义一个整体为不能直接从中间的一个位置竖着切开.

然后我们知道如果放两块\(1\times 1\)的砖块的话只有可能是若干个横着放的砖块加上两块\(1 \times 1\)的砖块所形成的整体.并且对于这个整体而言如果长为奇数和长为偶数都只有两种放法.

所以我们枚举中间的包含两块\(1 \times 1\)的砖块所形成的整体的长的长度,再枚举这个整体左侧放了多少个\(1\times 2\)的砖块

则有: \[ \begin{aligned}&2\times\sum_{i=3}^{n}\sum_{j=0}^{n-i}f[j]\times f[n-i-j]\\=&2\times\sum_{i=0}^{n-3}\sum_{j=0}^{n-i-3}f[i]\times f[j]\end{aligned} \] 这里设\(f[i] = fib[i+1]\).

然后前缀和一下就可以做到每次询问\(O(n)\).有\(50\)分.

又因为\(\sum_{i=1}^nfib[i]=fib[n+2]-1\), 所以有: \[ \begin{aligned}2\times \sum_{i=0}^{n-3}f[i]\times (f[n-i-1]-1)\end{aligned} \]\(A[i]=\sum_{j=0}^{i-3}f[j]\times (f[i-j-1]-1)\). \[ \begin{aligned}A[i+1]&=\sum_{j=0}^{i-2}f[j]\times(f[i-j]-1)\\&=\sum_{j=0}^{i-3}f[j]\times(f[i-j-1]+f[i-j-2]-1)+f[i-2]\\&=\sum_{j=0}^{i-3}f[j]\times f[i-j-1]+\sum_{j=0}^{i-4}f[j]\times(f[i-j-2]-1)+f[i-2]\\&=A[i]+A[i-1]+\sum_{j=0}^{i-3}f[j]+f[i-2]\\&=A[i]+A[i-1]+f[i-1]+f[i-2]-1\\&=A[i]+A[i-1]+f[i]-1\end{aligned} \] 然后矩阵快速幂就好了.

为什么大家都说很水????好吧,是我太菜了....

代码:

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
/*
* 3086.cpp
* This file is part of 3086
*
* Copyright (C) 2019 - ViXbob
*
* 3086 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3086 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3086. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int T, n;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

struct Matrix {
int H, W;
vector<vector<int> > mat;
Matrix(int a = 0, int b = 0) {
H = a; W = b;
mat.resize(H);
rep(i, 0, H - 1) mat[i].resize(W);
}

vector<int> &operator [] (const int x) { return mat[x]; }

Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
rep(i, 0, H - 1) rep(j, 0, t.W - 1) rep(k, 0, W - 1)
rnt[i][j] = pls(rnt[i][j], 1ll * mat[i][k] * t.mat[k][j] % P);
return rnt;
}

Matrix operator ^ (ll k) const {
Matrix rnt = (*this), x = (*this);
for(ll i = k - 1; i; i >>= 1, x = x * x) if(i & 1) rnt = rnt * x;
return rnt;
}
} A, Trans;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read();
while(T--) {
n = read();
if(n <= 2) { puts("0"); continue; }
A = Matrix(1, 5);
Trans = Matrix(5, 5);
A[0][2] = 1; A[0][3] = 1; A[0][4] = P - 1;
Trans[1][0] = 1;
Trans[0][1] = Trans[1][1] = Trans[2][1] = Trans[3][1] = Trans[4][1] = 1;
Trans[3][2] = 1;
Trans[2][3] = Trans[3][3] = 1;
Trans[4][4] = 1;
Trans = Trans ^ (n - 2);
A = A * Trans;
printf("%d\n", 1ll * A[0][1] * 2 % P);
}
return 0;
}
/*
*/

旅行者

很经典的一个模型.

我们先考虑另外一个东西:如果我们知道两个点集\(A,B\).我们想求\(\min_{x\in A, y \in B}\{dis(x,y)\}\)可以直接搞一个源点连\(A\)集合中的点,\(B\)集合中的点连汇点,然后跑最短路就好了.(反着也要跑一遍,因为是有向图)

现在这道题就是只有一个大集合,我们想找到一种合适的划分方式使得最优解的两个点刚好一个在\(A\)中,一个在\(B\)中就可以完美的解决这个问题了.

又因为这两个点的标号一定不同所以把两个数看成二进制的话也就是说,对于它们俩来说一定有一个二进制位是不同的,所以我们枚举每一个二进制位然后按照\(01\)划分这个集合的话,一定存在一种情况将它们两个划分开来.对于每一种划分我们都直接\(\text{Dijkstra}\)一下来更新答案.

最终复杂度为\(O(n\log^2 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
/*
* 3087.cpp
* This file is part of 3087
*
* Copyright (C) 2019 - ViXbob
*
* 3087 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3087 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3087. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 15;
const int P = 998244353;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, k, Case, mx, S, T;
vector<pair<int, int> > G[maxn];
vector<int> List;
ll ans, dis[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void Dijkstra(int i, int S, int T, int type) {
priority_queue<pair<ll, int> > q;
memset(dis, 0x3f, sizeof(ll) * (T + 5));
for(auto u : List) if(u >> i & 1) type ? G[S].pb(mp(u, 0)) : G[u].pb(mp(T, 0));
else type ? G[u].pb(mp(T, 0)) : G[S].pb(mp(u, 0));
q.push(mp(dis[S] = 0, S));
while(q.size()) {
int u = q.top().second; ll now = -q.top().first; q.pop();
if(dis[u] != now) continue;
for(auto v : G[u]) if(dis[v.first] > dis[u] + v.second) {
dis[v.first] = dis[u] + v.second;
q.push(mp(-dis[v.first], v.first));
}
}
ans = min(ans, dis[T]); G[S].clear(); G[T].clear();
for(auto u : List) if(~u >> i & 1 & type) G[u].pop_back();
else if (u >> i & 1 & ~type) G[u].pop_back();
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
Case = read();
while(Case--) {
n = read(); m = read(); k = read(); List.clear();
S = n + 1; T = S + 1;
ans = 0x3f3f3f3f3f3f3f3f; mx = 0;
rep(i, 1, n + 2) G[i].clear();
rep(i, 1, m) {
int x = read(), y = read(), w = read();
G[x].pb(mp(y, w));
}
rep(i, 1, k) List.pb(read()), mx = max(mx, *List.rbegin());
for(int i = 0; mx >> i; i++) {
Dijkstra(i, S, T, 1);
Dijkstra(i, S, T, 0);
} cout << ans << endl;
}
return 0;
}
/*
001
011
110
*/

旧词

回想LNOI2014_LCA.我们直接把一个点到根节点的路径上的每个点都加上一,然后查询一个点和其他点的\(\text{lca}\)的深度和就可以直接转化为查询这个点到根节点的路径上的节点的点权和了.

这个东西本质上是差分了一下.

推而广之,这道题一样这样搞:

我们先离线询问,然后每次加入一个点实际上就是把这个点到根节点的路径上的所有点\(i\)的点权都加上了\(a_i\). \[ a_i=dep_i^k-dep_{fa_i}^k \] 这个东西那线段树和树剖维护一下就好了.

秒水题真爽

代码:

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
167
168
169
170
/*
* 3088.cpp
* This file is part of 3088
*
* Copyright (C) 2019 - ViXbob
*
* 3088 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 3088 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 3088. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int n, q, k, fa[maxn], dep[maxn], w[maxn], depk[maxn], coc;
int pos[maxn], dfn[maxn], son[maxn], top[maxn], size[maxn], ans[maxn];
vector<int> G[maxn];
vector<pair<int, int> > Q[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

inline void dfs(int x) {
depk[x] = ksm(dep[x], k);
w[x] = dec(depk[x], depk[fa[x]]);
size[x] = 1;
for(auto v : G[x]) {
dep[v] = dep[x] + 1; dfs(v);
size[x] += size[v];
if(size[v] > size[son[x]]) son[x] = v;
}
if(!son[x]) son[x] = x;
}

inline void dfs(int x, int f) {
top[x] = f; dfn[++coc] = x;
pos[x] = coc;
if(son[x] ^ x) dfs(son[x], f);
for(auto v : G[x]) if(v != son[x]) dfs(v, v);
}

#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
struct Node {
int s, sum, tag;
} t[maxn << 2];

inline void pushtag(int p, int x) {
t[p].sum = pls(t[p].sum, 1ll * t[p].s * x % P);
t[p].tag = pls(t[p].tag, x);
}

inline void pushdown(int p) {
if(t[p].tag) {
pushtag(ls, t[p].tag);
pushtag(rs, t[p].tag);
t[p].tag = 0;
}
}

inline void Build(int l, int r, int p) {
if(l == r) return (void)(t[p].s = w[dfn[r]]);
Build(l, mid, ls); Build(mid + 1, r, rs);
t[p].s = pls(t[ls].s, t[rs].s);
}

inline void modify(int l, int r, int ql ,int qr, int p, int x) {
if(l == ql && r == qr) return pushtag(p, x);
pushdown(p);
if(qr <= mid) modify(l, mid, ql, qr, ls, x);
else if(ql > mid) modify(mid + 1, r, ql, qr, rs, x);
else modify(l, mid, ql, mid, ls, x), modify(mid + 1, r, mid + 1, qr, rs, x);
t[p].sum = pls(t[ls].sum, t[rs].sum);
}

inline int query(int l, int r, int ql, int qr, int p) {
if(l == ql && r == qr) return t[p].sum;
pushdown(p);
if(qr <= mid) return query(l, mid, ql, qr, ls);
else if(ql > mid) return query(mid + 1, r, ql, qr, rs);
else return pls(query(l, mid, ql, mid, ls), query(mid + 1, r, mid + 1, qr, rs));
}
#undef ls
#undef rs
#undef mid

inline void ChainModify(int x, int y) {
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
modify(1, coc, pos[top[x]], pos[x], 1, 1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
modify(1, coc, pos[x], pos[y], 1, 1);
}

inline int ChainQuery(int x, int y, int rnt = 0) {
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
rnt = pls(rnt, query(1, coc, pos[top[x]], pos[x], 1));
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
rnt = pls(rnt, query(1, coc, pos[x], pos[y], 1));
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); q = read(); k = read();
rep(i, 2, n) G[fa[i] = read()].pb(i);
dep[1] = 1; dfs(1);
rep(i, 1, q) {
int x = read(), y = read();
Q[x].pb(mp(y, i));
}
dfs(1); dfs(1, 1);
Build(1, coc, 1);
rep(i, 1, n) {
ChainModify(1, i);
for(auto v : Q[i]) ans[v.second] = ChainQuery(1, v.first);
}
rep(i, 1, q) printf("%d\n", ans[i]);
return 0;
}