A. 种花
枚举 \((x_2,y_0)\)，考虑 \(x_1\) 可能在哪些位置，显然是在 \(x_2\) 往上的一个极长连续 0 段上。
考虑如果固定了 \(x_1\) 的位置后怎么计算 C 形的数量，我们预处理出 \(r_{i,j}\) 表示从 \((i,j)\) 开始往右的极长 0 连续段长度，显然这个方案数就是 \((r_{x_1, \ y_0} - 1) \cdot (r_{x_2, \ y_0} - 1)\)。
结合 \(x_1\) 可能出现的位置容易用前缀和优化。F 相当于就是在 C 下面加一竖，我们再预处理出 \(d_{i,j}\) 表示从 \((i,j)\) 开始往下的极长 0 连续段长度，那么这个位置 F 的方案数 \(F_{i,j} = C_{i,j} \cdot (d_{i,j} - 1)\)。
总时间复杂度 \(\mathcal{O}(nm)\)，记得多测要清空。细节见代码。
code
#include <bits/stdc++.h>
#define mem(x, v) memset(x, v, sizeof(x))
using namespace std;
const int N = 1e3 + 5, mod = 998244353;
int n, m, c, f, C, F;
bool a[N][N];
int r[N][N], d[N][N], s[N];
void solve() {
cin >> n >> m >> c >> f;
mem(r, 0)， mem(d, 0);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= m; j++) {
if (s[j - 1] == '0') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (a[i][j] == 0) {
r[i][j] = r[i][j + 1] + 1;
} else {
r[i][j] = 0;
}
}
}
for (int j = 1; j <= m; j++) {
for (int i = n; i >= 1; i--) {
if (a[i][j] == 0) {
d[i][j] = d[i + 1][j] + 1;
} else {
d[i][j] = 0;
}
}
}
C = F = 0;
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (r[i][j] > 1) {
s[i] = s[i - 1] + (r[i][j] - 1);
} else if (r[i][j] == 1) {
s[i] = s[i - 1];
} else {
s[i] = 0;
}
int val = 0;
if (i >= 3) {
if (a[i][j] == 0 && a[i - 1][j] == 0) {
val = (val + 1ll * (r[i][j] - 1) * s[i - 2] % mod) % mod;
}
C = (C + val) % mod;
if (d[i][j] > 1) {
F = (F + 1ll * val * (d[i][j] - 1) % mod) % mod;
}
}
}
}
cout << c * C << " " << f * F << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t, id; cin >> t >> id;
while (t--) solve();
return 0;
}
B. 喵了个喵
真不会构造题
。
先考虑 \(k = 2n-2\) 怎么做，我们选一个栈当做缓冲栈，其余每个栈最多存 \(2\) 个元素，如果此时栈内元素互不相同，那么我们就可以保证缓冲栈是空栈。
假设当前栈内元素互不相同，考虑如果此时加入了栈内已有的一种元素该怎么办：对于题目的两种操作，一种可从栈顶删去相同元素，一种借助空栈可从栈底删去相同元素，于是我们始终能使得缓冲栈是空栈，即每个元素 \(t\) 都能和下一个同类元素匹配。
现在我们考虑 \(k = 2n-1\) 时该怎么做。此时可能出现的情况是，其他 \(n−1\) 个栈都有两个元素，且当前牌堆顶的元素 \(x\) 不同于当前在栈中的所有元素的情况。我们仍然希望把它放进其他栈中，并保持缓冲栈为空，但为了使之后的元素能够消掉，我们还需要保证栈内的每个元素 \(t\) 都能和下一个同类元素匹配。
我们预处理出第 \(i\) 个元素需要匹配的下一个同类元素出现的时刻 \(t_i\)（如果 \(t_i = 0\) 表示其应该和上一个同类元素匹配），那么对于任意一个栈，其中元素的 \(t_i\) 应该长成这个样子：从栈顶开始到某个位置 \(p\)，\(t_i\) 单调递增；从 \(p\) 开始到栈底，\(t_i\) 单调递减。这样就可以保证对于任意一种元素，当下一个同类元素出现的时候，其要么在栈顶，要么在栈底，都可以通过所给的两种操作匹配。
唯一剩下的问题是，我们如何将元素 \(x\) 放到栈里使得其仍然保持上面的性质。我们分类讨论：
-
如果当前存在一个栈顶元素 \(y\) 使得 \(t_x < t_y\)，那么我们直接将 \(x\) 放入该栈中。
-
否则，我们检查是否存在一个栈顶元素 \(y\) 使得 \(t_x > t_y\) 且当前栈内的元素从栈底开始 \(t_i\) 单调递增，根据操作过程，这只需要检查栈底的两个元素 \(p,q\) 是否满足 \(t_p < t_q\) 即可。
如果存在这样的栈，我们从所有这样的栈中选择栈底 \(p\) 所对应的 \(t_p\) 最大的一个，将 \(x\) 放入该栈中。
-
如果以上两种栈都不存在，那么我们将 \(x\) 放入一个空栈。
考虑证明这样操作的合法性：显然只需要考虑其他 \(n−1\) 个栈都有两个元素，且当前牌堆顶的元素 \(x\) 不同于当前在栈中的所有元素的情况。
此时如果我们需要将 \(x\) 放入缓冲栈，那么这意味着：对于所有栈，设其栈内元素 \(p_i,q_i\)，那么有 \(t_{p_i} > t_{q_i},t_x > t_{q_i}\)。也就是说，对于所有栈而言，栈顶的元素一定会先出现，于是只需要使用若干次操作 \(1\) 就可以把所有栈的栈顶消去，转化为所有栈都有一个元素的情况。
此时唯一可能不合法的情况是，我们连续往栈中放入了 \(n - 1\) 个元素，并且除了某一个栈，其余 \(n-1\) 个栈都有 \(2\) 个元素且栈内元素 \(p,q\) 满足 \(t_p < t_q\)。设剩下那个栈中的元素为 \(x\)，如果 \(t_x\) 不是所有栈底的 \(t\) 的最小值，那么某个栈底就会被卡住出不来了。
这就是为什么在第二种情况中我们需要选择栈底 \(p\) 所对应的 \(t_p\) 最大的一个栈，这样就可以保证 \(t_x\) 最小，那么把 \(t_x\) 消掉之后就又产生了一个空栈，这就证明了合法性。
使用 deque 维护栈内元素，set 维护所有空栈位置，粗略实现可以做到 \(\mathcal{O}(nm)\)。不过要带个 \(\frac{1}{2}\) 的常数，并且跑不太满，所以通过还是没有什么问题的。
code
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 2e3 + 5, M = 2e6 + 5;
typedef long long LL;
int n, m, k, a[M], p[N], nxt[M];
int c, op[M << 1], _x[M << 1], _y[M << 1];
deque <int> q[N];
void add(int x) {
++c, op[c] = 1, _x[c] = x;
}
void del(int x, int y) {
++c, op[c] = 2, _x[c] = x, _y[c] = y;
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
q[i].clear();
fill(nxt + 1, nxt + m + 1, 0);
fill(p + 1, p + k + 1, 0);
c = 0;
vector <int> _p(k + 1);
for (int i = m; i >= 1; i--) {
if (_p[a[i]]) {
nxt[i] = _p[a[i]];
_p[a[i]] = 0;
} else {
_p[a[i]] = i;
}
}
unordered_set <int> S;
for (int i = 1; i <= n; i++)
S.insert(i);
for (int i = 1; i <= m; i++) {
int cur = a[i];
if (!nxt[i]) {
int x = p[cur];
p[cur] = 0;
if (a[q[x].back()] == cur) {
add(x);
q[x].pop_back();
} else {
int y = *S.begin();
add(y);
del(x, y);
q[x].pop_front();
}
if (q[x].empty()) S.insert(x);
} else {
bool ok = false;
for (int j = 1; j <= n; j++) {
if (q[j].empty())
continue;
if (nxt[i] < nxt[q[j].back()]) {
add(j), p[cur] = j, q[j].pb(i);
ok = true;
break;
}
}
if (ok == false) {
int pos = 0;
for (int j = 1; j <= n; j++) {
if (q[j].empty())
continue;
if (nxt[i] > nxt[q[j].back()]) {
bool _ok = false;
if (q[j].size == 1)
_ok = true;
if (q[j].size() > 1) {
int it = *-- --q[j].end();
if (nxt[q[j].back()] > nxt[it])
_ok = true;
}
if (_ok == true)
if (!pos || nxt[q[j].front()] > nxt[q[pos].front()])
pos = j;
}
}
if (pos > 0) {
add(pos), p[cur] = pos, q[pos].pb(i);
ok = true;
}
}
if (ok == false) {
int x = *S.begin();
S.erase(x);
add(x);
q[x].pb(i);
p[cur] = x;
}
}
}
cout << c << endl;
for (int i = 1; i <= c; i++) {
if (op[i] == 1) {
cout << 1 << " " << _x[i] << "\n";
} else {
cout << 2 << " " << _x[i] << " " << _y[i] << "\n";
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
C. 建造军营
删去一条边使得军营不连通，则删去的边一定是原图割边。
边双缩点，称 \(x\) 被点亮当且仅当 \(x\) 对应点双存在军营。对于一个点亮的点集 \(S\)，我们在其 LCA 处统计其贡献。
考虑 DP，设 \(f_{u,0/1/2}\) 分别表示考虑点 \(u\) 的子树，钦定点 \(u\) 被点亮 / 不点亮且 \(u\) 为点集 \(S\) 的 LCA、\(u\) 子树中至少点亮一个点 的方案数。则初始值 \(f_{u,0} = (2^{s_u} - 1) \cdot 2^{e_u}，f_{u,1} = f_{u,2} = 2^{e_u}\)。
其中 \(s_u\) 为点双 \(u\) 内的点数，\(e_u\) 为 \(u\) 内的边数。
至于 \(f_{u,2}\) 的初值为什么是 \(2^{e_u}\) 我们稍后再解释，先来考虑 \(f_{u,0}\) 的转移：我们依次考虑 \((u,v)\) 这条边是否必须被保护，如果 \((u,v)\) 必须被保护，那么 \(v\) 子树内至少被点亮了一个点，这样的方案数为 \(f_{v,2}\)。否则子树内边可以任意选择是否保护，这样的方案数为 \(2^{se_v} \cdot 2\)。于是
\[f_{u,0} = \prod_{v \in \text{son}_u} (f_{v,2} + 2^{se_v} \cdot 2) \]对于 \(f_{u,2}\)，我们先考虑 \(u\) 不被点亮的情况（注意这和 \(f_{u,1}\) 不同，这里不要求 \(u\) 是 LCA），最后加上 \(f_{u,0}\)，这就是为什么初始值 \(f_{u,2} = 2^{e_u}\)。转移和 \(f_{u,0}\) 类似，容斥掉子树内所有点都不选的情况即可。
\(f_{u,1}\) 也差不多，容斥掉子树内所有点都不选的情况以及只有一个儿子子树内有点点亮的情况即可，后者可以通过前后缀积计算。
答案即为 \(\sum 2^{m - sze_u} \cdot (f_{u,1} + f_{u,2})\)，总时间复杂度 \(\mathcal{O}(n+m)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 5e5 + 5, M = 1e6 + 5, mod = 1e9 + 7;
int n, m, U[M], V[M];
int tot = 1, hd[N], nxt[2 * M], to[2 * M];
void add(int u, int v) {
to[++tot] = v, nxt[tot] = hd[u], hd[u] = tot;
to[++tot] = u, nxt[tot] = hd[v], hd[v] = tot;
}
int tim, dfn[N], low[N], col[N], cnt;
bool bri[2 * M];
void tarjan(int u, int ff) {
dfn[u] = low[u] = ++tim;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v == ff)
continue;
if (dfn[v] == 0) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
bri[i] = bri[i ^ 1] = true;
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
bool vis[N];
int szE[N], szN[N], sE[N], sN[N];
int f[N], g[N], h[N], le[N], ri[N], p[N + M];
vector <int> e[N];
void dfs(int u) {
if (vis[u] == true)
return;
vis[u] = true;
col[u] = cnt;
sN[cnt]++;
for (int i = hd[u]; i; i = nxt[i]) {
if (bri[i] == true)
continue;
int v = to[i];
dfs(v);
}
}
void calc(int u, int ff) {
szE[u] = sE[u];
szN[u] = sN[u];
vector <int> son;
for (int v : e[u]) {
if (v == ff)
continue;
calc(v, u);
son.pb(v);
szE[u] += szE[v] + 1;
szN[u] += szN[v];
}
int val = 1ll * p[sE[u]] * (p[sN[u]] - 1) % mod;
f[u] = val;
g[u] = h[u] = p[sE[u]];
for (int v : e[u]) {
if (v == ff)
continue;
int val = (g[v] + p[szE[v] + 1]);
f[u] = 1ll * f[u] * val % mod;
g[u] = 1ll * g[u] * val % mod;
h[u] = 1ll * h[u] * val % mod;
}
int L = son.size();
le[0] = 1;
for (int i = 1; i <= L; i++) {
int v = son[i - 1];
le[i] = 1ll * le[i - 1] * p[szE[v] + 1] % mod;
}
ri[L + 1] = 1;
for (int i = L; i >= 1; i--) {
int v = son[i - 1];
ri[i] = 1ll * ri[i + 1] * p[szE[v] + 1] % mod;
}
for (int i = 1; i <= L; i++) {
int v = son[i - 1];
int val = 1ll * g[v] * le[i - 1] % mod * ri[i + 1] % mod;
h[u] = (h[u] + mod - 1ll * p[sE[u]] * val) % mod;
}
h[u] = (h[u] + mod - p[szE[u]]) % mod;
g[u] = (g[u] + mod - p[szE[u]]) % mod;
g[u] = (g[u] + f[u]) % mod;
f[u] = 1ll * f[u] * p[m - szE[u]] % mod;
h[u] = 1ll * h[u] * p[m - szE[u]] % mod;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
U[i] = x;
V[i] = y;
add(x, y);
}
tarjan(1, 0);
for (int i = 1; i <= n; i++) {
if (col[i] == 0) {
cnt++, dfs(i);
}
}
for (int i = 1; i <= m; i++) {
int x = U[i], y = V[i];
if (col[x] == col[y]) {
sE[col[x]]++;
} else {
e[col[x]].pb(col[y]);
e[col[y]].pb(col[x]);
}
}
p[0] = 1;
for (int i = 1; i <= n + m; i++)
p[i] = 1ll * p[i - 1] * 2 % mod;
calc(1, 0);
int ans = 0;
for (int i = 1; i <= cnt; i++) {
ans = (ans + f[i]) % mod;
ans = (ans + h[i]) % mod;
}
cout << ans << "\n" ;
return 0;
}
D. 比赛
才发现自己还不会历史和，来抄一个 Alex_Wei 老师的题解
。
扫描线，设 \(T_{i, j}\) 表示以 \(i\) 为右端点时每个 \(j\) 作为左端点的答案。
加入 \(a_i\) 时，考虑它对 \(ra_j = \max\limits_{p = j} ^ i a_j\) 的影响，用单调栈维护，相当于若干次区间加法。加入 \(b_i\) 时同理。线段树容易维护 \(T_{i - 1}\to T_i\)。
而询问 \([l, r]\) 的答案相当于对所有 \(T_i(l\leq i\leq r)\)，查询 \(T_{i, j}(l\leq j\leq i)\) 的区间和。改变求和顺序，相当于对所有 \(l \leq j \leq r\)，查询 \(T_{i, j}(j\leq i\leq r)\) 之和。因为 \(i < j\) 时 \(T_{i, j} = 0\)，所以又可以写成 \(T_{i, j}(i\leq r)\) 之和。
维护 \(T_i\) 前缀和 \(U_i\)，即对 \(T\) 维护历史和，则询问 \([l, r]\) 相当于 \(U_r\) 区间查询 \([l, r]\)。
- 对于懒标记，维护 \((da, db, t, ha, hb, hab)\) 分别表示 \(\Delta a\)，\(\Delta b\)，求和轮数，每轮求和的 \(da\) 之和即 \(da\) 历史和，\(db\) 历史和，以及 \(da \cdot db\) 历史和。
- 对于信息，维护 \((len, sa, sb, sab, hab)\) 分别表示区间长度，区间 \(\sum a\)，区间 \(\sum b\)，区间 \(\sum ab\) 和区间 \(\sum ab\) 历史和。
时间复杂度 \(\mathcal{O}((n + q)\log n)\)，细节见代码。
code
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef pair <int, int> pi;
#define pb emplace_back
#define fi first
#define se second
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l + r) >> 1)
#define LS ls, l, mid
#define RS rs, mid + 1, r
const int N = 2.5e5, M = N << 2;
int T, n, q;
ull a[N], b[N], ans[N];
vector <pi> v[N];
int sta[N], ta, stb[N], tb;
struct laz {
ull da, db, t, ha, hb, hab;
laz operator + (const laz &x) const {
if (t == -1)
return x;
laz z;
z.da = da + x.da;
z.db = db + x.db;
z.t = t + x.t;
z.ha = ha + da * x.t + x.ha;
z.hb = hb + db * x.t + x.hb;
z.hab = hab + da * db * x.t + da * x.hb + x.ha * db + x.hab;
return z;
}
} g[M];
struct dat {
ull len, sa, sb, sab, hab;
dat operator + (const laz &x) const {
dat z;
z.len = len;
z.sa = sa + x.da * len;
z.sb = sb + x.db * len;
z.sab = sab + sa * x.db + sb * x.da + x.da * x.db * len;
z.hab = hab + sab * x.t + sa * x.hb + x.ha * sb + len * x.hab;
return z;
}
dat operator + (const dat &x) const {
return (dat) {
len + x.len, sa + x.sa, sb + x.sb, sab + x.sab, hab + x.hab
};
}
} f[M];
void up(int p) { f[p] = f[ls] + f[rs]; }
void ptag(int p, laz v) { f[p] = f[p] + v, g[p] = g[p] + v; }
void down(int p) {
if (g[p].t != -1) {
ptag(ls, g[p]), ptag(rs, g[p]);
g[p].t = -1;
}
}
void build(int p, int l, int r) {
g[p].t = -1, f[p].len = r - l + 1;
if (l == r)
return;
build(LS), build(RS);
}
void mdf(int p, int l, int r, int L, int R, laz v) {
if (L > R)
return;
if (L <= l && R >= r)
return ptag(p, v);
down(p);
if (L <= mid) mdf(LS, L, R, v);
if (R > mid) mdf(RS, L, R, v);
up(p);
}
ull qry(int p, int l, int r, int L, int R) {
if (L <= l && R >= r)
return f[p].hab;
int ret = 0;
down(p);
if (L <= mid) ret += qry(LS, L, R);
if (R > mid) ret += qry(RS, L, R);
return ret;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> T >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
v[r].pb(l, i);
}
build(1, 1, n);
a[0] = b[0] = n + 1;
for (int i = 1; i <= n; i++) {
while (ta && a[sta[ta]] < a[i]) {
mdf(1, 1, n, sta[ta - 1] + 1, sta[ta], (laz){-a[sta[ta]], 0, 0});
ta--;
}
while (tb && b[stb[tb]] < b[i]) {
mdf(1, 1, n, stb[tb - 1] + 1, stb[tb], (laz){0, -b[stb[tb]], 0});
tb--;
}
mdf(1, 1, n, sta[ta] + 1, i, (laz){a[i], 0, 0});
mdf(1, 1, n, stb[tb] + 1, i, (laz){0, b[i], 0});
mdf(1, 1, n, 1, i, (laz){0, 0, 1});
sta[++ta] = stb[++tb] = i;
for (auto [x, y] : v[i]) ans[y] = qry(1, 1, n, x, i);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
return 0;
}