Day1 T1 方格染色(color)
容易发现相对难处理的是斜线，但是我们发现斜线不超过 \(5\) 条，那么对于这一部分我们可以拆贡献，然后暴力做。
具体而言，先算出斜线减去横/竖线的面积，再算出横竖线面积并即可。
对于第一部分，考虑将斜线按照 \(y - x\) 分类，不同类斜线之间不会相互影响，同类斜线先去掉相交的情况，对于不交的斜线贡献也是独立的，对于它们再枚举横线和竖线，用 \(\text{set}\) 对相交点判重即可。
对于第二部分，我们只需考虑横线和竖线，考虑强化成任意矩形也是可做的，并且这是洛谷的扫描线板子，直线离散化 + 线段树即可。
时间复杂度 \(O(q \log q)\)。
Code
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
int cid, n, m, q, t;
int p[N];
struct R {
int type, x1, y1, x2, y2;
};
struct E {
int x, l, r, v;
};
vector<R> vr;
map<int, vector<R>> mp;
vector<E> ve;
namespace Seg {
#define lc (k << 1)
#define rc ((k << 1) + 1)
const int T = N * 4;
int val[T], tag[T], sum[T];
void Build (int k, int L = 1, int R = t) {
if (L == R) {
val[k] = p[L] - p[L - 1];
return;
}
int mid = (L + R) >> 1;
Build(lc, L, mid);
Build(rc, mid + 1, R);
val[k] = val[lc] + val[rc];
}
void Add (int k, int l, int r, int x, int L = 1, int R = t) {
if (l <= L && r >= R) {
tag[k] += x;
}
else {
int mid = (L + R) >> 1;
if (l <= mid) {
Add(lc, l, r, x, L, mid);
}
if (r > mid) {
Add(rc, l, r, x, mid + 1, R);
}
}
if (tag[k]) {
sum[k] = val[k];
}
else {
if (L == R)
sum[k] = 0;
else
sum[k] = sum[lc] + sum[rc];
}
}
#undef lc
#undef rc
}
int main () {
// freopen("color.in", "r", stdin);
// freopen("color.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> cid >> n >> m >> q;
for (int i = 1, t; i <= q; ++i) {
R r;
cin >> r.type >> r.x1 >> r.y1 >> r.x2 >> r.y2;
if (r.type != 3)
vr.push_back(r);
else
mp[r.y1 - r.x1].push_back(r);
}
LL ans = 0;
for (auto i : mp) {
int del = i.first;
vector<R> v = i.second;
sort(v.begin(), v.end(), [&](R a, R b) -> bool {
return a.x1 < b.x1;
});
vector<R> tmp;
for (auto j : v) {
if (tmp.empty() || j.x1 > tmp.back().x2) {
tmp.push_back(j);
}
else {
tmp.back().x2 = max(tmp.back().x2, j.x2);
tmp.back().y2 = tmp.back().x2 + del;
}
}
for (auto j : tmp) {
set<pair<int, int>> s;
for (auto k : vr) {
pair<int, int> p;
if (k.type == 1) {
p = {k.y1 - del, k.y1};
}
else {
p = {k.x1, k.x1 + del};
}
if (j.x1 <= p.first && p.first <= j.x2 && k.x1 <= p.first && p.first <= k.x2 && k.y1 <= p.second && p.second <= k.y2) {
s.insert(p);
}
}
ans += j.x2 - j.x1 + 1 - s.size();
}
}
// cout << ans << '\n';
for (auto i : vr) {
p[++t] = i.y1 - 1, p[++t] = i.y2;
}
sort(p + 1, p + t + 1);
t = unique(p + 1, p + t + 1) - p - 1;
// for (int i = 1; i <= t; ++i) {
// cout << p[i] - p[i - 1] << ' ';
// }
// cout << '\n';
for (auto &i : vr) {
i.y1 = lower_bound(p + 1, p + t + 1, i.y1) - p;
i.y2 = lower_bound(p + 1, p + t + 1, i.y2) - p;
// cout << i.x1 << ' ' << i.x2 << ' ' << i.y1 << ' ' << i.y2 << '\n';
ve.push_back((E){i.x1, i.y1, i.y2, 1});
ve.push_back((E){i.x2 + 1, i.y1, i.y2, -1});
}
Seg::Build(1);
auto cmp = [&](E a, E b) -> bool {
return a.x < b.x;
};
sort(ve.begin(), ve.end(), cmp);
int lst = 0;
for (auto i : ve) {
// cout << i.x << ' ' << i.l << ' ' << i.r << ' ' << i.v << ' ' << Seg::sum[1] << '\n';
ans += 1ll * (i.x - lst) * Seg::sum[1];
lst = i.x;
Seg::Add(1, i.l, i.r, i.v);
}
cout << ans << '\n';
return 0;
}
Day1 T2 桂花树(tree)
考虑用虚树刻画 \(\text{LCA}\) 的限制，题目中的条件等价于：
-
编号在 \([1, n]\) 中的点构成的虚树点集为其本身。
-
\(\forall i \in [n + 1, n + m]\)，编号在 \([1, i]\) 中的点构成的虚树中，所有点的编号 \(\le i + k\)。
容易发现 \([1, n]\) 中点的相对位置肯定是不变的，考虑在此基础上添加 \(n + 1, n + 2, \ldots, n + m\)。
设 \(f_{i, S}\) 表示：已经在树上加入了 \([1, n + i]\) 中的所有结点，对于 \([n + i + 1, n + i + k]\) 中的每个位置 \(x\)，我们用一个 \(01\) 变量表示，我们是否已在树上钦定了一个编号不超过 \(x\) 的点，状压成 \(S\)，在这种情况下，方案数是多少。
转移有四种，下面令 \(c = n + i + \text{popcount}(S)\)，表示当前树上的结点数：
-
将 \(i + 1\) 挂在一个结点下面作为叶子，方案数为 \(c\)。
-
将 \(i + 1\) 插入在某条边中，方案数为 \(c - 1\)。
-
将 \(i + 1\) 填入到某个已经钦定的位置中，此时我们枚举 \(S\) 中所有为 \(1\) 的位置转移即可。
-
对于某条边进行分裂，考虑一条树边 \((u, v)\)，其中 \(u\) 为 \(v\) 的祖先，我们强制将 \(i + 1\) 挂在 \(v\) 旁边，并钦定一个结点 \(w\) 作为 \(i + 1\) 和 \(v\) 的 \(\text{LCA}\)，此时我们要求 \(w \le i + k + 1\)，这个限制可以加入到 \(S\) 中。对于每条边我们都可以这么做，方案数为 \(c - 1\)。
特别地，如果我们已经钦定了一个 \(\le i + 1\) 的点，那么第 \(1, 3, 4\) 种转移都是无效的，第 \(2\) 种转移也不能将 \(i + 1\) 填入其他位置中。
时间复杂度 \(O(mk2^k)\)。
Code
#include <iostream>
using namespace std;
const int M = 3005, S = (1 << 10);
const int Mod = 1e9 + 7;
int n, m, k;
int f[M][S];
int main () {
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int cid, T;
cin >> cid >> T;
while (T--) {
cin >> n >> m >> k;
for (int i = 1, f; i < n; cin >> f, ++i);
if (m == 0) {
cout << 1 << '\n';
continue;
}
f[0][0] = 1;
fill(f[1], f[m] + (1 << k), 0);
for (int i = 0; i < m; ++i) {
for (int s = 0; s < (1 << k); ++s) {
int c = n + i + __builtin_popcount(s);
if (!(s & 1))
(f[i + 1][s >> 1] += f[i][s] * (c * 2 - 1ll) % Mod) % Mod;
for (int j = 0, t; j < k; ++j) {
if ((!(s & 1) || !j) && ((s >> j) & 1))
t = (s >> 1) ^ (!j ? 0 : 1 << (j - 1)), (f[i + 1][t] += f[i][s]) %= Mod;
}
if (!(s & 1) && k)
(f[i + 1][(s >> 1) | (1 << (k - 1))] += f[i][s] * (c - 1ll) % Mod) %= Mod;
}
}
cout << f[m][0] << '\n';
}
return 0;
}
Day2 T1 贸易(trade)
注意到向上走的路径只有一条，所以令 \(z = \text{LCA}(x, y)\)，我们可以将 \(dis(x, y)\) 拆成 \(dis(x, z) + dis(z, y)\)。
比较麻烦的是在枚举 \(x, y\) 求和的时候我们要求 \(x\) 能到达 \(y\)，首先观察到它等价于 \(z\) 能到达 \(y\)，于是考虑枚举 \(y, z\)，枚举量是 \(O(2^nn)\) 的，令 \(z\) 向非 \(y\) 祖先的 \(z\) 的儿子移动一条边后，得到的结点是 \(u\)，那么合法的 \(x\) 形如 \(z\) 和 \(u\) 的子树（可以画个 \(\text{LCA}\) 图理解一下）。
首先看前一部分 \(dis(x, z)\)，容易预处理一个结点 \(u\) 的子树内所有点到 \(u\) 的距离和 \(pre\)，再设 \(siz\) 表示子树内结点个数，第一部分贡献显然就是 \(pre_u + a_u \times siz_u\)（考虑 \(u\) 子树内所有点须先走到 \(u\)，再从 \(u\) 向上走一条边到达 \(z\)）。
第二部分 \(dis(z, y)\)，考虑枚举了 \(z, y\)，这个值是固定的，那么只需计数有多少个 \(x\) 满足要求，而显然 \(x\) 的个数为 \(siz_u + 1\)，所以我们现在的问题就变成了，对于每一个点，求每一个祖先到自己的最短路。
我们当然可以枚举一个起点。从它开始在它子树内跑最短路，这样入队次数是 \(O(2^nn)\) 的，复杂度是对的，但是考虑对于一对点 \(u, v\)，\(u\) 是 \(v\) 的祖先，从 \(u\) 到 \(v\) 的最短路可能形如，先从 \(u\) 跳到某一个 \(u\) 的祖先 \(t\)，从 \(t\) 走一条非树边到 \(s\)，再从 \(s\) 到 \(v\)，这种情况最短路会出 \(u\) 的子树。
注意到 \(s\) 一定是 \(u\) 子树内的点，并且从 \(t\) 跳到 \(s\) 后不会再向上走出 \(u\) 子树，否则没必要跳这条边，不如直接走出子树。所以我们枚举 \(u\) 子树内点 \(v\)，我们要求的是 \(u\) 到 \(v\) 的最短路，我们枚举关于 \(v\) 的边 \(w \rightarrow v\)，需要满足 \(w\) 在 \(u\) 子树外，那么存在一条 \(u \rightarrow w \rightarrow v\) 的路径，长度为 \(sum_u - sum_w + c(u, v)\)，其中 \(sum\) 为树边前缀和，\(c(u, v)\) 表示 \(u\) 到 \(v\) 的边权，特殊处理即可。此外不存在最短路会出 \(u\) 子树的情况。
时间复杂度 \(O(2^nn^2)\)。
Code
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#define lc (k << 1)
#define rc ((k << 1) | 1)
using namespace std;
using LL = long long;
const int L = 18, N = (1 << L) + 5;
const int Mod = 998244353;
const LL Inf = 1e18;
int n, m, ans;
int a[N], siz[N], pre[N], dep[N];
LL dis[N][L], sum[N];
vector<pair<int, int>> e[N], r[N];
void Dfs (int k) {
sum[k] = sum[k >> 1] + a[k];
siz[k] = 1;
if (lc < (1 << n)) {
dep[lc] = dep[rc] = dep[k] + 1;
Dfs(lc), Dfs(rc);
siz[k] += siz[lc] + siz[rc];
pre[k] = (pre[lc] + pre[rc] + 1ll * a[lc] * siz[lc] + 1ll * a[rc] * siz[rc]) % Mod;
}
}
int main () {
// freopen("trade.in", "r", stdin);
// freopen("trade.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 2; i < (1 << n); ++i) {
cin >> a[i];
}
for (int i = 1, u, v, w; i <= m; ++i) {
cin >> u >> v >> w;
e[u].push_back({v, w});
r[v].push_back({u, w});
}
Dfs(1);
fill(dis[0], dis[(1 << n)] + L, Inf);
for (int l = 0; l < n; ++l) {
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
for (int i = 1; i < (1 << n); ++i) {
if (dep[i] == l)
q.push({0, i});
}
for (int i = 1, j; i < (1 << n); ++i) {
if (dep[i] <= l) continue;
for (j = i; dep[j] > l; j >>= 1) {
}
for (auto k : r[i]) {
int v = k.first, w = k.second;
if (v < j)
q.push(pair<LL, int>({sum[j] - sum[v] + w, i}));
}
}
while (!q.empty()) {
pair<LL, int> t = q.top();
q.pop();
int u = t.second;
LL d = t.first;
if (d < dis[u][l]) {
dis[u][l] = d;
if (dep[u] > l)
q.push({d + a[u], u >> 1});
for (auto i : e[u]) {
int v = i.first, w = i.second;
q.push({d + w, v});
}
}
}
}
int ans = 0;
for (int y = 1; y < (1 << n); ++y) {
ans = (ans + pre[y]) % Mod;
for (int z = y >> 1, d = dep[y] - 1; z && dis[y][d] != Inf; z >>= 1, --d) {
int u = (((y >> (dep[y] - dep[z * 2])) == z * 2) ? z * 2 + 1 : z * 2);
ans = (ans + pre[u] + 1ll * a[u] * siz[u] + (dis[y][d] % Mod) * (siz[u] + 1)) % Mod;
}
}
cout << ans << '\n';
return 0;
}
Day2 T2 字符串(string)
下面记 \(s_{i \sim j}\) 表示 \(s\) 的第 \(i\) 个字符到第 \(j\) 个字符构成的子串，$< $ 表示比较字典序大小。
注意到 \(s_{i \sim {i + l - 1}} < s_{i + 2l - 1 \sim i + l}\) 的限制等价于 \(s_{i \sim {i + 2l - 1}} < s_{{i + 2l - 1} \sim i}\)，也就是这个字符串正着读字典序比倒着读小。
继续放缩限制，考虑先计数 \(p = i + 2l - 1(1 \le l \le r)\) 的数量，满足 \(s_{i \sim n} < s_{p \sim 1}\)，再减去不合法的部分，即 \(s_{i \sim p}\) 构成回文串，且 \(s_{i \sim n} > s_{p \sim 1}\)。
先考虑第一部分，注意到问题是前缀与后缀比较字典序大小的形式，所以构造 \(T = s + a + \overline{s} + b\)，并对 \(T\) 后缀排序。其中 \(a\) 和 \(b\) 是任意小于字符集的字符，且满足 \(a < b\)，这是模拟空串以避免不必要的麻烦。
由于合法的 \(p\) 构成一段区间中所有下标为奇数/偶数的位置，先奇偶分类，那么查询相当于求区间中 \(x\) 的个数，满足 \(rk_x > rk_i\)，这个是二维数点，扫描线即可。
再考虑第二部分，由于 \(s_{i \sim p}\) 构成回文串，那么 \(s_{i \sim n} > s_{p \sim 1}\) 等价于考虑偶回文中心 \(t\) 和 \(t + 1\)，满足 \(s_{t + 1 \sim n} > s_{t \sim 1}\)。
那么我们直接枚举回文中心 \(t, t + 1\)，\(s_{t + 1 \sim n} > s_{t \sim 1}\) 的限制用前面的 SA 就可处理。但新增了两个限制，一是 \(s_{i \sim t} = s_{p \sim {t + 1}}\)（能构成回文串），二是从 \(i\) 开始的 \(r\) 个串中包含以 \(t, t + 1\) 为回文中心的串。
第一个限制我们可以先 Manacher 处理出 \(len_i\) 表示以 \(i, i + 1\) 为回文中心时的最长回文半径，那么若 \(i \in [t - len_t + 1, t]\) 则一定构成回文串。第二个限制相当于 \(i + r - 1 \ge t\)，合起来又是一个二维偏序，还是扫描线即可。
时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
const int N = 2e5 + 5;
int n, q;
char s[N], t[N];
int x[N], r[N], ans[N], len[N];
int sa[N], rk[N], tmp[N], cnt[N], la[N * 2];
namespace Part1 {
void Build_SA (int len) {
iota(sa + 1, sa + len + 1, 1);
sort(sa + 1, sa + len + 1, [&](int i, int j) -> bool {
return s[i] < s[j];
});
rk[sa[1]] = 1;
for (int i = 2; i <= len; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
for (int l = 1; l < len; l <<= 1) {
int t = 0;
for (int i = len - l + 1; i <= len; ++i) {
tmp[++t] = i;
}
for (int i = 1; i <= len; ++i) {
if (sa[i] > l) {
tmp[++t] = sa[i] - l;
}
}
fill(cnt, cnt + len + 1, 0);
for (int i = 1; i <= len; ++i) {
++cnt[rk[i]];
}
for (int i = 1; i <= len; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = len; i; --i) {
sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
copy(rk + 1, rk + len + 1, la + 1);
rk[sa[1]] = 1;
for (int i = 2; i <= len; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (la[sa[i]] != la[sa[i - 1]] || la[sa[i] + l] != la[sa[i - 1] + l]);
}
}
}
int Irk (int x) { return n * 2 + 3 - rk[x]; }
struct C {
int p, v, o, x, id;
};
struct BIT {
int c[N * 2];
void Clear () { fill(c, c + n * 2 + 2, 0); }
void Add (int x, int y) {
for (; x <= n * 2 + 2; x += (x & -x)) {
c[x] += y;
}
}
int Query (int x) {
int res = 0;
for (; x; x -= (x & -x)) {
res += c[x];
}
return res;
}
} b[2];
void Main () {
Build_SA(n * 2 + 2);
vector<C> cv;
for (int i = 1; i <= q; ++i) {
int x = ::x[i], r = ::r[i];
int ql = n * 2 - x + 3 - r * 2, qr = n * 2 - x + 1;
if (ql > 1) cv.push_back(C({ql - 1, -1, (x ^ 1) & 1, Irk(x), i}));
cv.push_back(C({qr, 1, (x ^ 1) & 1, Irk(x), i}));
}
sort(cv.begin(), cv.end(), [&](C a, C b) -> bool {
return a.p < b.p;
});
b[0].Clear(), b[1].Clear();
auto it = cv.begin();
for (int i = 1; i <= n * 2 + 2; ++i) {
b[i & 1].Add(Irk(i), 1);
while (it != cv.end() && it->p == i) {
ans[it->id] += it->v * b[it->o].Query(it->x - 1);
++it;
}
}
}
}
namespace Part2 {
void Manacher () {
t[1] = '#';
for (int i = 1; i <= n; ++i) {
t[i * 2] = s[i];
t[i * 2 + 1] = '#';
}
fill(len + 1, len + n * 2 + 2, 0);
for (int i = 1, d = 0, r = 0; i <= n * 2 + 1; ++i) {
if (r >= i) {
len[i] = min(len[d * 2 - i], r - i + 1);
}
while (i - len[i] > 0 && i + len[i] <= n * 2 + 1 && t[i - len[i]] == t[i + len[i]]) {
++len[i];
}
if (i + len[i] - 1 > r) {
d = i, r = i + len[i] - 1;
}
}
}
int Get_len (int i) {
return (len[i * 2 + 1] - 1) / 2;
}
struct A {
int p, x, v;
};
struct C {
int p, x, id;
};
struct BIT {
int c[N];
void Clear () { fill(c, c + n + 1, 0); }
void Add (int x, int y) {
for (; x <= n; x += (x & -x)) {
c[x] += y;
}
}
int Query (int x) {
int res = 0;
for (; x; x -= (x & -x)) {
res += c[x];
}
return res;
}
} b;
void Main () {
Manacher();
vector<A> av;
vector<C> cv;
for (int i = 1; i < n; ++i) {
if (rk[i + 1] >= rk[n * 2 + 2 - i]) continue;
av.push_back(A({i - Get_len(i) + 1, i, 1}));
av.push_back(A({i + 1, i, -1}));
}
for (int i = 1; i <= q; ++i) {
cv.push_back(C({x[i], x[i] + r[i] - 1, i}));
}
sort(av.begin(), av.end(), [&](A a, A b) -> bool {
return a.p < b.p;
});
sort(cv.begin(), cv.end(), [&](C a, C b) -> bool {
return a.p < b.p;
});
auto ia = av.begin();
auto ic = cv.begin();
b.Clear();
while (ia != av.end() || ic != cv.end()) {
if (ia != av.end() && (ic == cv.end() || ia->p <= ic->p)) {
b.Add(ia->x, ia->v), ++ia;
}
else {
ans[ic->id] -= b.Query(ic->x), ++ic;
}
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int tid, T;
cin >> tid >> T;
while (T--) {
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
copy(s + 1, s + n + 1, s + n + 2);
reverse(s + n + 2, s + n * 2 + 2);
s[n + 1] = 'a' - 1, s[n * 2 + 2] = 'a' - 2;
fill(ans + 1, ans + q + 1, 0);
for (int i = 1; i <= q; ++i) {
cin >> x[i] >> r[i];
}
Part1::Main();
Part2::Main();
for (int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
}
return 0;
}