1129考试总结
TESknight的模拟赛, TESknight太巨辣!!!!%%%
T1
题目链接
单调栈.
毒瘤出题人TESknight把数据改成了(n <= 1e7), 后来因为学校机子太烂限制了dalao出的题, 迫不得已改成了(1e6).%%%
我们考虑一个数字对那些区间有影响, 假设这个数字为(x), 那么这个数字是可以作为区间([l, r])的最小值的, (l)表示(x)左边第一个小于(x)的数的下一位, (r)表示(x)右边第一个小于(x)的数的上一位, 如果不存在那么就是(1, n).
然后我们可以用单调栈(O(n))的求出每个数字的([l,r]), 设区间长度为(len)的答案是(ans[len]), 那么我们就可以用这个数字来更新(ans[r - l + 1]), 具体一点就是(ans[r - l + 1] = max(ans[r - l + 1], x)).
最后我们再从(n)到1扫一遍, (ans[i] = max(ans[i+1], ans[i])).因为小区间的答案只可能比大区间的答案大, 不可能比大区间的答案小.复杂度(O(n)).
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e6 + 5;
int n, top;
int a[N], r[N], l[N], sta[N], ans[N];
int main() {
n = read();
for(register int i = 1;i <= n; i++) a[i] = read();
for(register int i = 1;i <= n; i++) {
while(top && a[sta[top]] > a[i]) r[sta[top --]] = i - 1;
sta[++ top] = i;
}
while(top) r[sta[top --]] = n;
for(register int i = n;i >= 1; i--) {
while(top && a[sta[top]] > a[i]) l[sta[top --]] = i + 1;
sta[++ top] = i;
}
while(top) l[sta[top --]] = 1;
for(register int i = 1;i <= n; i++) ans[r[i] - l[i] + 1] = max(ans[r[i] - l[i] + 1], a[i]);
for(register int i = n;i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
for(register int i = 1;i <= n; i++) printf("%d ", ans[i]);
return 0;
}
T2
题目链接
乱搞.
对于两个点(x, y), 他们在原图上的距离是(dis).如果(dis)为偶数, 那么这两个点在新图上的最短路径一定是(dis / 2), 奇数就是((dis + 1) / 2);
所以我们要求这个东西 : (displaystyle sum_{i = 1}^{n} sum_{j = i+ 1} ^ {n} ( dis(i, j) + [dis(i, j) \% 2 == 1]) / 2).
前一部分(ans = displaystyle sum_{i = 1}^{n} sum_{j = i+ 1} ^ {n} dis(i, j))很好求, 直接考虑每条边的贡献就好了, 那么后半部分(displaystyle sum_{i = 1}^{n} sum_{j = i+ 1} ^ {n} [dis(i, j) \% 2 == 1])怎么求呢?
后半部分的含义其实是找出两个点在原图中距离为奇数的点对的个数, 我们可以把(dis(i,j))换成(l_i + l_j - 2*l_{lca}), (l_x)表示(x)到根的距离.然后我们分析这个东西的奇偶性, 可以发现后边(2*l_{lca})对奇偶性没有影响, 所以我们只需要找(l_i, l_j)奇偶性不同的点对就好了, 换句话说, 我们统计(l_x)为奇数的点的个数(num), 那么奇偶性不同的点对个数就是(num * (n - num)).
所以最后的答案是是((ans + num * (n - num)) / 2).复杂度(O(n + m))
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 3e5 + 5, inf = 1e9;
int n, cnt, num;
long long ans, sum[N];
int d[N], dep[N], siz[N], head[N];
struct edge { int to, nxt; } e[N << 2];
void add(int x, int y) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y;
}
void get_tree(int x, int fa) {
dep[x] = dep[fa] + 1; siz[x] = 1;
if(dep[x] & 1) num ++;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa) continue ;
get_tree(y, x); siz[x] += siz[y];
ans += 1ll * siz[y] * (n - siz[y]);
}
}
int main() {
n = read();
for(register int i = 1, x, y;i < n; i++) x = read(), y = read(), add(x, y), add(y, x);
get_tree(1, 0);
printf("%lld
", (ans + 1ll * num * (n - num)) / 2);
return 0;
}
T3
题目链接
数据结构优化DP.
设(f[i][j])表示将前(i)个分成(j)份的最优答案, (w[i][j])表示区间([i,j])里不同数字的个数, 那么很容易列出方程:
(f[i][j] = max(f[i][j], f[k][j - 1] + w[k + 1][i])).
考虑优化. 主要优化求(w)的过程.我们预处理一个数组(pre), (pre[i])表示在(i)位置上出现的数字(a_i)上一次出现的位置.那么我们可以知道这个数字对区间([pre[i], i- 1])是有贡献的.
现在我们就可以直接用线段树维护啦!我们每次将分(j - 1)份的答案存入线段树中, 然后不断这些([pre[i], i- 1])区间进行加一, 这便是线段树区间加法和询问区间最大值的板子了.
#include <bits/stdc++.h>
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int M = 4e4 + 5;
int n, k, num;
int a[M], f[M][55], las[M], pre[M];
struct { int Max, tag; } t[M << 2];
void build(int o, int l, int r, int k) {
t[o].tag = 0;
if(l == r) { t[o].Max = f[l][k]; return ; }
build(ls(o), l, mid, k); build(rs(o), mid + 1, r, k);
t[o].Max = max(t[ls(o)].Max, t[rs(o)].Max);
}
void modify(int o, int k) { t[o].Max += k; t[o].tag += k; }
void down(int o) {
if(t[o].tag) modify(ls(o), t[o].tag), modify(rs(o), t[o].tag), t[o].tag = 0;
}
void change(int o, int l, int r, int x, int y) {
if(x <= l && y >= r) { modify(o, 1); return ; }
down(o);
if(x <= mid) change(ls(o), l, mid, x, y);
if(y > mid) change(rs(o), mid + 1, r, x, y);
t[o].Max = max(t[ls(o)].Max, t[rs(o)].Max);
}
int query(int o, int l, int r, int x, int y) {
if(x <= l && y >= r) return t[o].Max;
down(o); int res = 0;
if(x <= mid) res = max(res, query(ls(o), l, mid, x, y));
if(y > mid) res = max(res, query(rs(o), mid + 1, r, x, y));
return res;
}
int main() {
n = read(); k = read();
for(register int i = 1;i <= n; i++) a[i] = read();
for(register int i = 1;i <= n; i++) pre[i] = las[a[i]], las[a[i]] = i;
for(register int j = 1;j <= k; j++) {
build(1, 0, n, j - 1);
for(register int i = 1;i <= n; i++) {
change(1, 0, n, pre[i], i - 1);
if(i >= j) f[i][j] = query(1, 0, n, 0, i - 1);
}
}
printf("%d", f[n][k]);
return 0;
}
T4
题目链接
树剖 + 线段树.
这题一眼看上去没思路, 所以我们需要转换所求答案的形式.
对于一个(displaystyle sum_{i= l}^{r} dep[lca(i,z)]), 我们可以知道这个式子的含义就是每一个节点(i)与(z)到根的重复路径的长度之和.所以我们可以对每个(i)从下往上走, 每经过一条边就把这条边的权值加一, 最后统计一下从(z)到根每条边的权值和就好了.
但是呢这也不好统计, 因为有多组询问, 涉及到了边权减法操作, 所以我们继续转换形式.
(displaystyle sum_{i= l}^{r} dep[lca(i,z)] = displaystyle sum_{i= 1}^{r} dep[lca(i,z)] - displaystyle sum_{i= 1}^{l - 1} dep[lca(i,z)]).我们把一组询问转换成了两组询问, 并且这些询问都有一个共同的特点 : 下界为1. 这意味着我们将不会涉及到减法操作.
我们把所有询问离线下来, 并且都拆成两个询问, 按照上界从小到大排序. 然后从1开始往里加点, 并不断地修改边权, 询问, 实现方法可以用树剖.
#include <bits/stdc++.h>
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 2e5 + 5, mod = 201314;
int n, m, cnt, tot;
int fa[N], hav[N], top[N], siz[N], dfn[N], dep[N], ans1[N], ans2[N], head[N];
struct edge { int to, nxt; } e[N];
struct ques {
int u, z, f, id;
ques() {}
ques(int x, int y, int Z, int k) { id = x; u = y; z = Z; f = k; }
friend int operator < (const ques &a, const ques &b) { return a.u < b.u; }
} q[N << 1];
struct tree { int sum, tag; } t[N << 2];
void add(int x, int y) {
e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y;
}
void get_tree(int x, int Fa) {
fa[x] = Fa; siz[x] = 1; dep[x] = dep[Fa] + 1;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == Fa) continue ;
get_tree(y, x); siz[x] += siz[y];
if(siz[y] > siz[hav[x]]) hav[x] = y;
}
}
void get_top(int x, int topic) {
dfn[x] = ++ tot; top[x] = topic;
if(hav[x]) get_top(hav[x], topic);
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == fa[x] || y == hav[x]) continue ;
get_top(y, y);
}
}
void up(int o) { t[o].sum = (t[ls(o)].sum + t[rs(o)].sum) % mod; }
void modify(int o, int l, int r, int k) {
t[o].sum = (t[o].sum + 1ll * (r - l + 1) * k % mod) % mod;
t[o].tag = (t[o].tag + k) % mod;
}
void down(int o, int l, int r) {
if(t[o].tag) modify(ls(o), l, mid, t[o].tag), modify(rs(o), mid + 1, r, t[o].tag), t[o].tag = 0;
}
void change(int o, int l, int r, int x, int y) {
if(x <= l && y >= r) { modify(o, l, r, 1); return ; }
down(o, l, r);
if(x <= mid) change(ls(o), l, mid, x, y);
if(y > mid) change(rs(o), mid + 1, r, x, y);
up(o);
}
int query(int o, int l, int r, int x, int y) {
if(x <= l && y >= r) return t[o].sum;
down(o, l, r); int res = 0;
if(x <= mid) res = (res + query(ls(o), l, mid, x, y)) % mod;
if(y > mid) res = (res + query(rs(o), mid + 1, r, x, y)) % mod;
return res;
}
void change_path(int x) {
int y = 1;
while(top[x] != top[y]) {
change(1, 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]];
}
change(1, 1, n, dfn[y], dfn[x]);
}
int query_path(int x) {
int res = 0, y = 1;
while(top[x] != top[y]) {
res = (res + query(1, 1, n, dfn[top[x]], dfn[x])) % mod; x = fa[top[x]];
}
res = (res + query(1, 1, n, dfn[y], dfn[x])) % mod;
return res;
}
int main() {
n = read(); m = read();
for(register int i = 2;i <= n; i++) add(read() + 1, i); cnt = 0;
for(int i = 1, l, r, z;i <= m; i++) {
l = read(); r = read() + 1; z = read() + 1;
q[++ cnt] = ques(i, l, z, 0);
q[++ cnt] = ques(i, r, z, 1);
}
sort(q + 1, q + cnt + 1);
get_tree(1, 0); get_top(1, 1); tot = 1;
for(int i = 1, sss;i <= cnt; i++) {
while(tot <= q[i].u) change_path(tot ++);
sss = q[i].id;
if(q[i].f) ans1[sss] = query_path(q[i].z);
else ans2[sss] = query_path(q[i].z);
}
for(int i = 1;i <= m; i++) printf("%d
", (ans1[i] - ans2[i] + mod) % mod);
return 0;
}