CF1083C Max Mex
求一条 \(\text{mex}\) 值最大的路径，相当于求一个最大的前缀 \(0,1,2,\cdots,k\) 使得点权为 \(0,1,\cdots,k\) 的点都可以被包含在同一条链中。
考虑使用线段树维护，第 \(i\) 个位置存树上点权为 \(i\) 的点的编号，如果我们能对每个区间求出其是否构成链以及对应链的信息，那么查询就只需要线段树上二分就行了。考虑如何合并信息，对于两个儿子区间，若任意一个区间内的点不构成链，那合起来肯定也不构成链。若两边都构成链，那么新的链的端点一定是这其中的两个，因此枚举 \(\binom{4}{2} = 6\) 种可能，判断一下剩下两个点是否在这条链上即可。
现在只需要判断一个点是否在一条链上。这是容易的，\(x\) 在链 \(u\to v\) 上的充要条件是 \(\text{dist}(x,u)+\text{dist}(x,v)=\text{dist}(u,v)\)，因此只需要快速求树上两点间距离，使用 \(\text{ST}\) 表预处理一下 \(\text{LCA}\) 即可。时间复杂度 \(O((n+q)\log n)\)。
Code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;
inline int read() {
int x = 0, w = 1;char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
const int MN = 4e5 + 5;
const int Mod = 998244353;
const int inf = 1e9;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
inline int qPow(int a, int b = Mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = ret * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ret;
}
#define dbg
int N, Q, a[MN], p[MN], dis[MN], dfn[MN], dfc, lg[MN];
pii ST[MN][20];
vector <int> e[MN];
inline void DFS(int u, int pr, int d) {
dfn[u] = ++dfc, ST[dfc][0] = mp(d, u);
for (int v : e[u]) if (v != pr) {
dis[v] = dis[u] + 1;
DFS(v, u, d + 1);
dfn[u] = ++dfc, ST[dfc][0] = mp(d, u);
}
}
inline void buildST() {
for (int i = 2; i <= dfc; i++) lg[i] = lg[i >> 1] + 1;
for (int j = 1; j <= 19; j++)
for (int i = 1; i + (1 << j) - 1 <= dfc; i++)
ST[i][j] = min(ST[i][j - 1], ST[i + (1 << j - 1)][j - 1]);
}
inline int qry(int u, int v) {
int l = dfn[u], r = dfn[v];
if (l > r) swap(l, r);
int k = lg[r - l + 1];
int q = min(ST[l][k], ST[r - (1 << k) + 1][k]).se;
return dis[u] + dis[v] - 2 * dis[q];
}
inline bool chk(int p, int x, int y) {
return qry(p, x) + qry(p, y) == qry(x, y);
}
struct Dat {
int x, y, ty;
Dat(int _x = 0, int _y = 0, int _ty = 0) : x(_x), y(_y), ty(_ty) {}
};
inline Dat operator + (const Dat x, const Dat y) {
if (x.ty == 2) return y;
if (y.ty == 2) return x;
if ((!x.ty) || (!y.ty)) return Dat(0, 0, 0);
int p = x.x, q = x.y, r = y.x, s = y.y;
if (chk(p, r, s) && chk(q, r, s)) return Dat(r, s, 1);
if (chk(p, q, s) && chk(r, q, s)) return Dat(q, s, 1);
if (chk(p, q, r) && chk(s, q, r)) return Dat(q, r, 1);
if (chk(r, p, q) && chk(s, p, q)) return Dat(p, q, 1);
if (chk(q, p, r) && chk(s, p, r)) return Dat(p, r, 1);
if (chk(q, p, s) && chk(r, p, s)) return Dat(p, s, 1);
return Dat(0, 0, 0);
}
const int MS = MN << 2;
#define ls o << 1
#define rs o << 1 | 1
#define mid ((l + r) >> 1)
#define LS ls, l, mid
#define RS rs, mid + 1, r
Dat tr[MS];
inline void pushup(int o) {
tr[o] = tr[ls] + tr[rs];
}
inline void build(int o, int l, int r) {
if (l == r) return tr[o] = Dat(p[l], p[l], 1), void();
build(LS), build(RS), pushup(o);
}
inline void upd(int o, int l, int r, int p, Dat v) {
if (l == r) return tr[o] = v, void();
(p <= mid ? upd(LS, p, v) : upd(RS, p, v)), pushup(o);
}
inline int qry(int o, int l, int r, Dat v) {
if ((tr[o] + v).ty == 1) return r;
if (l == r) return l - 1;
if ((tr[ls] + v).ty == 0) return qry(LS, v);
return qry(RS, v + tr[ls]);
}
signed main(void) {
N = read();
for (int i = 1; i <= N; i++) a[i] = read(), p[++a[i]] = i;
for (int i = 2; i <= N; i++) {
int f = read();
e[f].pb(i), e[i].pb(f);
}
DFS(1, 0, 1), buildST(), build(1, 1, N);
Q = read();
while (Q--) {
int op = read();
if (op == 1) {
int x = read(), y = read();
upd(1, 1, N, a[x], Dat(y, y, 1));
upd(1, 1, N, a[y], Dat(x, x, 1));
swap(a[x], a[y]);
} else {
printf("%lld\n", qry(1, 1, N, Dat(0, 0, 2)));
}
}
return 0;
}
CF1083D The Fair Nut's getting crazy
显然考虑枚举每个交集对答案的贡献。定义 \(\text{pre}_i\) 为 \(a_i\) 上一次出现的位置（若不存在则值为 \(0\)），\(\text{suf}_i\) 为 \(a_i\) 下一次出现的位置（若不存在则值为 \(n+1\)）。记：
\[f(i,j) = \max\{ \text{pre}_i,\cdots,\text{pre}_j \} + 1, \ g(i,j) = \min\{ \text{suf}_i,\cdots,\text{suf}_j \} - 1 \]那么答案即为
\[\sum_{i=1}^n \sum_{j=i}^n [i \geq f(i,j)][j \leq g(i,j)](i - f(i,j))(g(i,j) - j) \]考虑从大到小枚举 \(i\)，合法的 \(j\) 一定是一个区间。显然 \(f(i,j)\) 单调不降，\(g(i,j)\) 单调不升，可以双指针算出最大的 \(j\) 的位置。现在的问题是，对于当前的 \(i,j\)，如何快速计算
\[\sum_{k = i}^j (i - f(i,k)) \times (g(i,k) - k) \]把括号拆开
\[i \times \sum_{k = j}^i g(i,k) - i \times \sum_{k=i}^j k - \sum_{k=j}^i f(i,k) \times g(i,k) + \sum_{k = j}^i f(i,k) \times k \]使用线段树维护，用单调栈预处理后取 \(\max\) 和 \(\min\) 的操作就变成了区间赋值。要维护以下几种操作：\(a\) / \(b\) 序列区间赋值，求 \(a\) / \(b\) 序列区间和，求 \(a\) / \(b\) 序列 \((a/b)_i \times i\) 和，求区间 \(a_i \times b_i\) 和。打打标记容易维护，时间复杂度 \(O(n \log n)\)。
Code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;
inline int read() {
int x = 0, w = 1;char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
const int MN = 4e5 + 5;
const int Mod = 1e9 + 7;
const int inf = 1e9;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
inline int qPow(int a, int b = Mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = ret * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ret;
}
#define dbg
int N, a[MN], b[MN], lst[MN], cnt[MN], pre[MN], suf[MN], C[MN], D[MN], stk[MN], tp;
inline void inc(int &x, int y) { x += y; if (x >= Mod) x -= Mod; }
inline void dec(int &x, int y) { x -= y; if (x < 0) x += Mod; }
inline int add(int x, int y) { return x + y > Mod ? x + y - Mod : x + y; }
inline int sub(int x, int y) { return x - y < 0 ? x - y + Mod : x - y; }
inline int s2(int x) { return x * (x + 1) / 2 % Mod; }
inline int S(int l, int r) { return sub(s2(r), s2(l - 1)); }
const int MS = MN << 2;
#define ls o << 1
#define rs o << 1 | 1
#define mid ((l + r) >> 1)
#define LS ls, l, mid
#define RS rs, mid + 1, r
int tr[MS][4], tag[MS][2];
inline void pushup(int o) {
for (int i = 0; i < 4; i++) tr[o][i] = add(tr[ls][i], tr[rs][i]);
}
inline void pushtag(int o, int l, int r, int v, int ty) {
tr[o][2] = tr[o][ty ^ 1] * v % Mod;
tr[o][ty] = (r - l + 1) * v % Mod;
tag[o][ty] = v;
if (!ty) tr[o][3] = v * S(l, r) % Mod;
}
inline void pushdown(int o, int l, int r) {
for (int t = 0; t < 2; t++) if (tag[o][t]) {
pushtag(LS, tag[o][t], t), pushtag(RS, tag[o][t], t);
tag[o][t] = 0;
}
}
inline void upd(int o, int l, int r, int L, int R, int v, int ty) {
if (r < L || l > R) return;
if (L <= l && R >= r) return pushtag(o, l, r, v, ty);
pushdown(o, l, r), upd(LS, L, R, v, ty), upd(RS, L, R, v, ty), pushup(o);
}
inline int qry(int o, int l, int r, int L, int R, int ty) {
if (r < L || l > R || L > R) return 0;
if (L <= l && R >= r) return tr[o][ty];
return pushdown(o, l, r), add(qry(LS, L, R, ty), qry(RS, L, R, ty));
}
signed main(void) {
N = read();
for (int i = 1; i <= N; i++) a[i] = read(), b[i] = a[i];
sort(b + 1, b + N + 1);
int bcnt = unique(b + 1, b + N + 1) - b - 1;
for (int i = 1; i <= N; i++) a[i] = lob(b + 1, b + bcnt + 1, a[i]) - b;
for (int i = 1; i <= N; i++) pre[i] = lst[a[i]] + 1, lst[a[i]] = i;
for (int i = 1; i <= bcnt; i++) lst[i] = N + 1;
for (int i = N; i >= 1; i--) suf[i] = lst[a[i]] - 1, lst[a[i]] = i;
for (int i = N; i >= 1; i--) {
while (tp && pre[i] > pre[stk[tp]]) tp--;
C[i] = tp ? stk[tp] - 1 : N, stk[++tp] = i;
}
tp = 0;
for (int i = N; i >= 1; i--) {
while (tp && suf[i] < suf[stk[tp]]) tp--;
D[i] = tp ? stk[tp] - 1 : N, stk[++tp] = i;
}
int ans = 0;
for (int i = N, j = N; i >= 1; i--) {
upd(1, 1, N, i, C[i], pre[i], 0);
upd(1, 1, N, i, D[i], suf[i], 1);
cnt[a[i]]++;
while (cnt[a[i]] > 1) cnt[a[j]]--, j--;
inc(ans, qry(1, 1, N, i, j, 3));
inc(ans, i * qry(1, 1, N, i, j, 1) % Mod);
dec(ans, i * S(i, j) % Mod);
dec(ans, qry(1, 1, N, i, j, 2));
}
printf("%lld\n", ans);
return 0;
}
CF1083E The Fair Nut and Rectangles
因为矩形互不包含，先对所有矩形排个序，使得 \(x_i\) 单调递增，\(y_i\) 单调递减。考虑 DP，设 \(f_i\) 为选到排序后的第 \(i\) 个矩形，钦定第 \(i\) 个矩形必选的情况下面积并减去权值和的最大值为 \(f_i\)。转移枚举上一个选择的矩形是谁，则
\[f_i = \max_{0 \leq j \leq i-1} \{f_j + S_i - a_i - S_j \cap S_i \} \]其中 \(S_i = x_iy_i\)，\(S_i \cap S_j = x_jy_i\)。由单调性容易说明其正确性。然后一眼斜率优化，假设 \(i\) 的转移点为 \(j\)，那么
\[f_i = f_j + x_iy_j - x_jy_i - a_i \]移项可得
\[\underline{f_j}_y = \underline{y_i}_k \underline{x_j}_x + \underline{f_i - x_iy_i +a_i}_b \]相当于平面上若干个点 \((x_j,f_j)\)，过每个点做斜率为 \(y_i\) 的直线，我们的目标是最大化截距 \(b\)。维护上凸壳，由于 \(x\) 递增，\(y\)（斜率）递减，单调队列维护即可。时间复杂度 \(O(n \log n)\)。
Code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;
inline int read() {
int x = 0, w = 1;char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
const int MN = 2e6 + 5;
const int Mod = 1e9 + 7;
const int inf = 1e9;
const double eps = 1e-10;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
inline int qPow(int a, int b = Mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = ret * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ret;
}
#define dbg
int N, l, r, q[MN], f[MN], ans;
struct Square {
int x, y, w;
inline bool operator < (const Square &p) const {
return y > p.y;
}
} s[MN];
#define X(i) s[i].x
#define Y(i) f[i]
inline double slope(int i, int j) {
return abs(X(j) - X(i)) < eps ? inf : (Y(j) - Y(i)) / (X(j) - X(i));
}
signed main(void) {
N = read();
for (int i = 1; i <= N; i++) s[i].x = read(), s[i].y = read(), s[i].w = read();
sort(s + 1, s + N + 1);
for (int i = 1; i <= N; i++) {
while (l < r && slope(q[l], q[l + 1]) >= s[i].y) l++;
f[i] = s[i].x * s[i].y - s[i].w;
if (l <= r) f[i] = max(f[i], f[q[l]] + (s[i].x - s[q[l]].x) * s[i].y - s[i].w);
while (l < r && slope(q[r - 1], q[r]) <= slope(q[r], i)) r--;
q[++r] = i;
}
for (int i = 1; i <= N; i++) ans = max(ans, f[i]);
printf("%lld\n", ans);
return 0;
}
CF1083F The Fair Nut and Amusing Xor
首先差分，这样操作就变成了将距离为 \(k\) 的两个数 \(\oplus\) 一个值，单点修改变成了修改两个值（还是单点修改）。
考虑如何计算答案，我们可以从左往右扫，如果某个 \(a_i\) 不为 \(0\) 就将它和 \(a_{i+k}\) 一起异或 \(a_i\) 就行了。显然 \(\text{mod} \ k\) 意义下每条链都是独立的，考虑对每条链分别计算，不难发现一个数需要被操作当且仅当它的前缀异或和不为 \(0\)，我们容斥成计算前缀异或和为 \(0\) 的位置个数。无解的条件就是某条链的异或和不为 \(0\)，这个维护一下每条链最后一个位置的前缀异或值有多少个 \(0\) 就行了。
现在我们要维护两种操作：单点修改，维护前缀异或和。后者相当于是对后缀的区间修改，直接分块，散块暴力重构，整块打个 \(\mathrm{tag}\) 就行了。具体实现的时候可以把所有序列接在一起维护，只不过后缀修改就变成了区间修改，做法是一样的。时间复杂度 \(O(m \sqrt n)\)。
Code
/*
最黯淡的一个 梦最为炽热
万千孤单焰火 让这虚构灵魂鲜活
至少在这一刻 热爱不问为何
存在为将心声响彻
*/
#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define int long long
#define mem(x, v) memset(x, v, sizeof(x))
#define mcpy(x, y, n) memcpy(x, y, sizeof(int) * (n))
#define lob lower_bound
#define upb upper_bound
using namespace std;
inline int read() {
int x = 0, w = 1;char ch = getchar();
while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
const int MN = 2e5 + 5;
const int MM = 1.7e4 + 5;
const int MB = 350;
const int MS = (MN + MB - 1) / MB + 5;
const int Mod = 1e9 + 7;
const int inf = 1e9;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
inline int qPow(int a, int b = Mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = ret * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ret;
}
#define dbg
int N, M, Q, a[MN], id[MN], seq[MN], tp, bel[MN], zero;
int bl[MS], br[MS], cnt[MS][MM], tag[MS], A[MN], B[MN], lst[MN], C[MN], D[MN];
char op[10];
inline void pushdown(int x) {
for (int i = bl[x]; i <= br[x]; i++) cnt[x][D[i]]--, D[i] ^= tag[x];
tag[x] = 0;
}
inline void rebuild(int x) {
for (int i = bl[x]; i <= br[x]; i++) cnt[x][D[i]]++;
}
inline void upd(int x, int y) {
if (C[x % M]) zero--;
C[x % M] ^= y;
if (C[x % M]) zero++;
int l = id[x], r = lst[x % M];
pushdown(bel[l]);
if (bel[l] == bel[r]) {
for (int i = l; i <= r; i++) D[i] ^= y;
return rebuild(bel[l]);
}
pushdown(bel[r]);
for (int i = l; i <= br[bel[l]]; i++) D[i] ^= y;
for (int i = bl[bel[r]]; i <= r; i++) D[i] ^= y;
rebuild(bel[l]), rebuild(bel[r]);
for (int i = bel[l] + 1; i < bel[r]; i++) tag[i] ^= y;
}
inline void getans() {
int ans = 0;
for (int j = 1; j <= bel[N + 1]; j++) ans += cnt[j][tag[j]];
printf("%lld\n", N + 1 - ans);
}
signed main(void) {
N = read(), M = read(), Q = read();
for (int i = 1; i <= N; i++) A[i] = read(), a[i] ^= A[i];
for (int i = 1; i <= N; i++) B[i] = read(), a[i] ^= B[i];
for (int i = 1; i <= N + 1; i++) bel[i] = (i - 1) / MB + 1, br[bel[i]] = i;
for (int i = N + 1; i >= 1; i--) bl[bel[i]] = i;
for (int i = N + 1; i >= 1; i--) a[i] ^= a[i - 1];
for (int i = M + 1; i <= N + 1; i++) a[i] ^= a[i - M];
for (int i = N - M + 2; i <= N + 1; i++) if (C[i % M] = a[i]) zero++;
for (int i = 1; i <= M; i++)
for (int j = i; j <= N + 1; j += M) seq[id[j] = ++tp] = j, lst[i % M] = tp;
for (int i = 1; i <= bel[N + 1]; i++)
for (int j = bl[i]; j <= br[i]; j++) cnt[i][D[j] = a[seq[j]]]++;
if (zero) puts("-1");
else getans();
while (Q--) {
int x, y;
scanf("%s%lld%lld", op, &x, &y);
if (op[0] == 'a') upd(x, A[x] ^ y), upd(x + 1, A[x] ^ y), A[x] = y;
else upd(x, B[x] ^ y), upd(x + 1, B[x] ^ y), B[x] = y;
if (zero) puts("-1");
else getans();
}
return 0;
}