来补个档。
CF1621G Weighted Increasing Subsequences
先离散化。对每个上升子序列计算权值是困难的，我们考虑每个位置对答案的贡献。
即我们想要知道对于每个 /(a_p/)，/(i_k/) 最远能到哪里，使得存在一个 /(x /in (i_k, n]/) 满足 /(a_x > a_i/)。容易发现，若设 /(r_p/) 为最右端的满足 /(a_{r_p} > a_p/) 的下标，那么 /(i_k < r_p/)。
于是对于每一个 /(p/) 我们需要计算 “经过 /(p/)，且最后一个元素在 /(r_p/) 之前的” 上升子序列个数，这可以容斥成 “经过 /(p/)，且最后一个元素在 /(r_p/) 或 /(r_p/) 之后” 的上升子序列个数。但由于 /(r_p/) 的定义，对于任意 /(i /in (r_p, n]/) 都有 /(a_i /leq a_p/)，这意味着这些位置不可能成为上升子序列的结尾元素，于是我们只需要计算 “经过 /(p/)，且最后一个元素位置为 /(r_p/)” 的上升子序列个数。
接下来考虑如何计数。显然考虑把子序列拆成 /(p/) 之前和 /(p/) 到 /(r_p/) 两部分，前面是好算的。/(p/) 之后的部分我们考虑倒着处理，由于 /(r_p/) 是最靠右的满足条件的下标，所以任意一个从 /(p/) 开始的子序列结尾一定不超过 /(r_p/)，只需要维护 “从 /(p/) 开始以最远位置结尾” 的子序列的方案数即可。时间复杂度 /(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, n) memset(x, v, sizeof(int) * (n))
#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;
}
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
const int MN = 2e5 + 5;
const int Mod = 1e9 + 7;
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, a[MN], pre[MN], suf[MN], ans;
vector <int> vr;
inline void add(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;
}
int c[MN], mx[MN], mxv[MN];
inline void Add1(int x, int v) { for (; x <= N; x += x & -x) add(c[x], v); }
inline int Qry1(int x) { int res = 0; for(; x; x -= x & -x) add(res, c[x]); return res; }
inline void Add2(int x, pii v) {
for (; x; x -= x & -x) {
if (mx[x] < v.fi) mx[x] = v.fi, mxv[x] = 0;
if (mx[x] == v.fi) add(mxv[x], v.se);
}
}
inline pii Qry2(int x) {
int Mx = 0, Mxv = 0;
for (; x <= N; x += x & -x) {
if (Mx < mx[x]) Mx = mx[x], Mxv = 0;
if (Mx == mx[x]) add(Mxv, mxv[x]);
}
return mp(Mx, Mxv);
}
inline void Work() {
N = read();
vr.clear(), ans = 0;
for (int i = 1; i <= N; i++) a[i] = read(), vr.pb(a[i]);
for (int i = 1; i <= N; i++) c[i] = mx[i] = mxv[i] = 0;
sort(vr.begin(), vr.end());
vr.erase(unique(vr.begin(), vr.end()), vr.end());
for (int i = 1; i <= N; i++) a[i] = lob(vr.begin(), vr.end(), a[i]) - vr.begin() + 1;
for (int i = 1; i <= N; i++) Add1(a[i], pre[i] = Qry1(a[i] - 1) + 1);
for (int i = 1; i <= N; i++) c[i] = 0;
for (int i = N; i >= 1; i--) {
Add1(N - a[i] + 1, suf[i] = Qry1(N - a[i]) + 1);
pii cur = Qry2(a[i] + 1);
if (!cur.se) cur = mp(i, 1);
dec(suf[i], cur.se), Add2(a[i], cur);
}
for (int i = 1; i <= N; i++) add(ans, pre[i] * suf[i] % Mod);
printf("%lld/n", ans);
}
signed main(void) {
int T = read();
while (T--) Work();
return 0;
}
CF1621H Trains and Airplanes
注意到从任意一点 /(x/) 开始，其在每个区域被查的次数是固定的，设为 /(s_{x,i}/)，那么 /(f(v)/) 可以写成：
/[f(v) = /sum_{i /neq z_v} /min(fine_{v,i} /times s_{v,i},pass_{v,i})
/]
但是询问很奇怪，直接写成上式并不好处理询问。考虑在同一个询问中的所有点它们的 /(s_{v,i}/)，对于这些点来说，往上走时经过的所有区域在时间轴上都形成一段区间，而 /(s_{v,i}/) 计算的就是在这段区间中 /(T/) 的倍数点出现的次数。考虑把这些线段在 /(/mathrm{mod} / T/) 意义下处理，根据每个点的深度不同，时间轴和线段的位置也不相同。设在询问中 /(s_{v,i}/) 的最小值为 /(mn_{i}/)，容易发现 /(s_{v,i}/) 的值只可能为 /(mn_i/) 或 /(mn_i + 1/)，并且当线段在 /(/mathrm{mod} / T/) 意义下左右端点相对位置不变时取 /(mn_i/)，否则取 /(mn_i + 1/)。
也就是说，在同一次询问中，不同的 /(s_{v,i}/) 至多只有 /(O(2^k)/) 种，但还是太多了。更进一步地，考虑一个类似扫描线的过程，不难发现线段的移动是连续的，同样在 /(/mathrm{mod} / T/) 意义考虑，取 /(mn_i/) 的位置恰是一个区间！也就是说，这 /(k/) 个区域把 /(/mathrm{mod} / T/) 的环分成了 /(O(k)/) 个部分，这样在同一次询问中只会有 /(O(k)/) 种不同的 /(s_{v,i}/)。
接下来只需要模拟这个过程就行了：对每个位置预处理出 /(s_{v,i}/)，然后对每个位置处理出一个二进制状态 /(/mathrm{mask}/) 表示每个区域是取 /(mn_i/) 还是取 /(mn_{i+1}/)，这样的状态至多只有 /(O(k)/) 个。然后从下往上合并出每次询问需要的状态，处理询问就很容易了。时间复杂度 /(O(nk /log k + qk^2)/)，听说能更快，但反正过了就不管了。
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;
}
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
const int MN = 2e5 + 5;
const int MK = 30;
const int Inf = 2e18;
const int Mod = 1e9 + 7;
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, T, K, Q, zone[MN], pass[MN], fine[MN]; char s[MN];
int dis[MN], fa[MN], ord[MN], dfc, up[MN], lim[MN], coef[MN][MK], mask[MN];
vector <pii> G[MN];
vector <int> vr[MN];
inline void DFS(int u) {
ord[++dfc] = u;
for (auto [v, w] : G[u]) {
if (v == fa[u]) continue;
fa[v] = u;
dis[v] = dis[u] + w;
DFS(v);
}
}
inline void Work() {
N = read();
for (int i = 1; i < N; i++) {
int u = read(), v = read(), w = read();
G[u].pb(mp(v, w));
G[v].pb(mp(u, w));
}
fa[1] = -1;
DFS(1);
K = read();
scanf("%s", s + 1);
for (int i = 1; i <= N; i++) zone[i] = s[i] - 'A' + 1;
for (int i = 1; i <= K; i++) pass[i] = read();
for (int i = 1; i <= K; i++) fine[i] = read();
T = read();
mem(up, -1);
for (int j = 1; j <= dfc; j++) {
int i = ord[j];
if (fa[i] != -1) {
if (zone[i] != zone[fa[i]]) {
up[i] = fa[i];
} else {
up[i] = up[fa[i]];
}
} else {
up[i] = -1;
}
int p = up[i];
while (p != -1) {
int nxt = up[p];
int L = dis[i] - dis[p];
int R = (nxt == -1 ? dis[i] : dis[i] - dis[nxt]);
int c = (R + T - 1) / T - (L + T - 1) / T;
int mx = (R - L + T - 1) / T;
coef[i][zone[p]] += mx;
if (c < mx) {
mask[i] |= (1 << zone[p]);
}
p = nxt;
}
}
for (int j = dfc; j >= 1; j--) {
int i = ord[j];
vr[i].pb(mask[i]);
sort(vr[i].begin(), vr[i].end());
vr[i].resize(unique(vr[i].begin(), vr[i].end()) - vr[i].begin());
if (fa[i] != -1 && zone[i] == zone[fa[i]]) {
vr[fa[i]].insert(vr[fa[i]].end(), vr[i].begin(), vr[i].end());
}
}
for (int i = 1; i <= K; i++) lim[i] = pass[i] / fine[i];
Q = read();
while (Q--) {
int op = read();
if (op == 1 || op == 2) {
string ch;
cin >> ch;
int id = ch[0] - 'A' + 1;
(op == 1 ? pass[id] : fine[id]) = read();
lim[id] = pass[id] / fine[id];
} else {
int u = read();
int ans = Inf;
for (int ms : vr[u]) {
int cur = 0;
for (int j = 1; j <= K; j++) {
int c = coef[u][j];
if (ms & (1 << j)) c--;
if (c <= lim[j]) {
cur += c * fine[j];
} else {
cur += pass[j];
}
}
ans = min(ans, cur);
}
printf("%lld/n", ans);
}
}
}
signed main(void) {
int T = 1;
while (T--) Work();
return 0;
}
原创文章，作者：端木书台，如若转载，请注明出处：https://blog.ytso.com/278510.html