想不到好标题了。
有句话怎么说来着，罗马不是一天建成的，是一天天建成的。
还有什么，Do in Rome as the Romans' do，还有一句，All roads leads to Rome。
A. 连续的零 zero
http://222.180.160.110:1024/contest/4647/problem/1
做个前缀和，看看任意一个长度为 \(k\) 的区间中有几个 \(1\)。复杂度 \(\mathcal O(n)\)。
namespace XSC062 {
using namespace fastIO;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, res = inf;
int a[maxn], s[maxn];
int min(int x, int y) {
return x < y ? x : y;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%1d", &a[i]);
s[i] = s[i - 1] + a[i];
if (i >= m)
res = min(res, s[i] - s[i - m]);
}
print(res, '\n');
return 0;
}
} // namespace XSC062
B. 反回文串 anti
http://222.180.160.110:1024/contest/4647/problem/2
当 \(n\) 为奇时，中间的元素一定和自己相等，故无解。
当数量最多的一个字符个数超过 \(\dfrac n2\) 时，由鸽巢得无解。
剩下的情况一定有解。
证明
可以找到一种合法的构造方式。我们列出一个列数为 \(2\)，行数为 \(\dfrac n2\) 的表格，将所有相同字母排列在一起，按照从左到右，从上到下的方式将字母填入表格，最后将第 \(i\) 行第一列的字母填入 \(a_i\)，第 \(i\) 行第二列的字母填入 \(a_{n-i+1}\)，即可完成构造。
一种字母只在第一列或第二列出现当然合法，如果从第一列持续到第二列，因为任意字母出现次数不超过 \(\dfrac n2\) 次，所以同一行的两列不会出现同一种字母。
这叫什么，有字证明。
感觉可以拿去出一道类似于「找到字符串字典序最小的反回文串」之类的小水题
然后现在我们知道有解了，怎么找到最优解呢。
比如有一组 \((a_i,a_{n-i+1})=(\texttt a, \texttt a)\)，还有一组 \((a_j, a_{n-j+1})=(\texttt b, \texttt b)\)，那我们直接把 \(a_i\) 和 \(a_j\) 交换，皆大欢喜。
这就说明我们需要把值不相等的非法 \(a_i\) 与 \(a_j\) 配对。
然后我们就可以沿用证明中的构造方式，分组配对，一定最优，每组代价为 \(1\)。
同一行两个值 \(v\) 相等，因为已经最优了，所以不能再在非法串中寻找答案。应该找合法对中某个值交换，每组代价为 \(2\)。具体和谁交换我们不用担心，只要找到一组 \((a_i,a_{n-i+1})\) 满足 \(a_i\ne v\) 且 \(a_{n-i+1}\ne v\) 就可以了，然后我们又知道 \(v\) 的个数 \(\ne \dfrac n2\)，假设 \(\dfrac n2\) 对中每队都有至少一个 \(v\)，由于当前这一对有两个相同的 \(v\)，那么 \(v\) 的个数就会大于 \(\dfrac n2\)，矛盾了，所以一定能找到。
对于非法总对数是奇数的情况，我们要钦定一个非法对强制让其和合法对交换，贪心一下取非法对数量最多的 \(v\) 的某一对最优。
namespace XSC062 {
using namespace fastIO;
const int maxm = 35;
const int maxn = 2e5 + 5;
char s[maxn];
int cnt[maxm], p[maxn];
int T, n, tot, res, now;
int main() {
scanf("%d", &T);
while (T--) {
tot = 0;
scanf("%d %s", &n, s + 1);
if (n & 1) {
puts("-1");
continue;
}
memset(cnt, 0, sizeof (cnt));
for (int i = 1; i <= n; ++i)
++cnt[s[i] - 'a' + 1];
for (int i = 1; i <= 26; ++i) {
if (cnt[i] * 2 > n) {
puts("-1");
goto noSol;
}
}
memset(cnt, 0, sizeof (cnt));
for (int i = 1; i * 2 <= n; ++i) {
if (s[i] == s[n - i + 1])
++cnt[s[i] - 'a' + 1], ++tot;
}
std::sort(cnt + 1, cnt + 27,
std::greater<int>());
res = now = 0;
if (tot & 1) {
res = 1, --cnt[1];
std::sort(cnt + 1, cnt + 27,
std::greater<int>());
}
for (int i = 1; i <= 26; ++i) {
while (cnt[i]--) {
if (++now > tot / 2) {
if (i == p[now - tot / 2])
res += 2;
else ++res;
}
else p[now] = i;
}
}
print(res, '\n');
noSol: ;
}
return 0;
}
} // namespace XSC062
C. 除与减 divsub
http://222.180.160.110:1024/contest/4647/problem/3
小数学，还好。
假设 \(n=d\times k^p\)，其中 \(k\nmid d\)，那么我们分两种情况讨论。
-
\(p=0\)，即 \(k\nmid n\)，那么 \(n\bmod k=1\)，即 \(k\mid (n-1)\)。
这个时候问 \(k\) 的个数就相当于是在问 \(n-1\) 除 \(1\) 以外的因子个数。假设 \(n-1={x_1}^{p_1}{x_2}^{p_2}\cdots {x_m}^{p_m}\)，那么答案为 \((\prod p_i+1)-1\)，减去的是 \(1\)。
-
\(p\ne 0\)，\(k\mid n\)。
这个时候好像并没有什么好的转化。好消息是 \(n\) 的范围是 \(10^{12}\)，根号枚举因数复杂度跑得过。所以我们就可以暴力判定 \(n\) 的所有因数是否满足条件。
时间复杂度，\(\mathcal O(\sqrt n\times \log n)\)，枚举因数是根号，算次数（也就是算 \(d\)）是 \(\log\)。
#define int long long
namespace XSC062 {
using namespace fastIO;
int n, m, res, cnt;
int main() {
read(n), m = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
m = n;
while (m % i == 0) m /= i;
if (m % i == 1) ++res;
if (i * i != n) {
m = n;
while (m % (n / i) == 0)
m /= (n / i);
if (m % (n / i) == 1) ++res;
}
}
}
m = n - 1, cnt = 1;
for (int i = 2; i * i <= m; ++i) {
if (m % i == 0) {
int now = 0;
while (m % i == 0)
++now, m /= i;
cnt *= now + 1;
}
}
if (m != 1) cnt *= 2;
print(res + cnt, '\n');
return 0;
}
} // namespace XSC062
#undef int
D. 图书管理员 librarian
http://222.180.160.110:1024/contest/4647/problem/4
[SDOI2008] 郁闷的小 J。
关于这个，我们发现自己不会考场现冲主席树。哎，打 CDQ 又怕写挂。
我们发现这道题的修改都是单点的，询问也只关于某一种颜色，不同的颜色之间没有影响。
于是我们可以把操作离线下来，初始视作将某颜色在某位置增加，修改视作将某颜色在某位置删除，将另一颜色在该位置增加，将所有操作按颜色离散化分类然后 vector 下来，对于所有颜色从前到后树状数组做一遍操作就能 \(\mathcal O(n\log n+q\log n)\) 解决。
树状数组清空是肯定不能 memset 的，复杂度不对。那么怎么办呢？把所有操作撤回去就可以了。
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 5;
struct __ {
int ty, l, r, v;
__() {}
__(int t1, int l1, int r1, int v1 = 0) {
if (t1 == 0)
ty = 0, l = l1, v = r1;
else ty = 1, l = l1, r = r1, v = v1;
}
};
char ty;
std::map<int, int> tab;
std::vector<__> q[maxn];
int n, m, tot, x, y, v, id;
int Bit[maxn], a[maxn], res[maxn];
int lowbit(int x) { return x & -x; }
void add(int x, int v) {
for (; x <= n; x += lowbit(x))
Bit[x] += v;
return;
}
int ask(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += Bit[x];
return res;
}
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (!tab.count(a[i]))
tab[a[i]] = ++tot;
a[i] = tab[a[i]];
q[a[i]].emplace_back(0, i, 1);
}
while (m--) {
scanf("%1s", &ty);
if (ty == 'C') {
read(x), read(y);
if (!tab.count(y))
tab[y] = ++tot;
y = tab[y];
q[a[x]].emplace_back(0, x, -1);
q[a[x] = y].emplace_back(0, x, 1);
}
else {
++id;
read(x), read(y), read(v);
if (!tab.count(v)) continue;
v = tab[v];
q[v].emplace_back(1, x, y, id);
}
}
for (int i = 1; i <= tot; ++i) {
for (auto &j : q[i]) {
if (j.ty == 0) add(j.l, j.v);
else {
res[j.v] =
ask(j.r) - ask(j.l - 1);
}
}
for (auto &j : q[i])
if (j.ty == 0) add(j.l, -j.v);
}
for (int i = 1; i <= id; ++i)
print(res[i], '\n');
return 0;
}
} // namespace XSC062
E 会单独开一篇。
F. 树 tree
http://222.180.160.110:1024/contest/4647/problem/6
CF916E。
大分讨给我整不会了，更给我整不会的是下来过后发现这只是个小分讨。
更新子树和子树查询我们都会。换根 DP 我们也都写过，都知道换根并不会对子树结构产生大的影响。所以应当是能根据已知信息推测出子树在原树上对应的点集的。
记 \(r\) 为当前树根，\(\text {LCA}(x,y)\) 为 \(x,y\) 在 \(1\) 为根时的 LCA，\(\text {LCA}'(x,y)\) 表示 \(x,y\) 在 \(r\) 为根时的 LCA。
那么对于 \(\text {LCA}'(x,y)\)，肯定是要讨论 \(x,y\) 和 \(r\) 的位置关系的。
- \(\text {LCA}(x,y)\) 是 \(r\) 的子孙。此时 \(\text {LCA}'(x,y) = \text {LCA}(x,y)\)。
- \(\text {LCA}(x,y)\) 是 \(r\) 的祖先。那么说明至少有一个点不是 \(r\) 的子孙。此时 \(\text {LCA}(x,y)'\) 的值为 \(r\) 为另一个点的 LCA。
整理可得 \(\text {LCA}'(x,y)\) 是 \(\text {LCA}(x,y)\)、\(\text {LCA}(x,r)\) 和 \(\text {LCA}(y,r)\) 中的深度最大者。
对于以 \(r\) 为根时的子树 \(x\)：
- \(x=r\)，此时子树为整棵树。
- \(\text {LCA}(x,r)\ne x\)，即 \(r\) 不为 \(x\) 的子孙，此时子树就是以 \(1\) 为根是的子树 \(x\)。
- \(\text {LCA}(x,y)=x\)，即 \(r\) 为 \(x\) 的子孙，此时子树是整棵树除开 \(x\) 包含 \(r\) 的儿子及其子孙。修改和查询的时候容斥一下就好。这个时候的子树倍增跳一下就能找到。
然后就是常规线段树维护了。时间复杂度 \(\mathcal O(n\log n)\)。
namespace XSC062 {
using namespace fastIO;
const int maxm = 35;
const int maxn = 1e5 + 5;
#define lt (p << 1)
#define rt (lt | 1)
struct _ { int l, r, u, d; };
_ t[maxn << 2];
int f[maxn][maxm];
std::vector<int> g[maxn];
int a[maxn], dfn[maxn], rfn[maxn];
int n, q, r, ty, x, y, v, si, now;
int top[maxn], dep[maxn], tab[maxn];
void swap(int &x, int &y) {
x ^= y ^= x ^= y;
return;
}
void DFS(int x) {
dep[x] = dep[f[x][0]] + 1;
dfn[x] = ++now, tab[now] = x;
for (auto i : g[x]) {
if (i == f[x][0]) continue;
f[i][0] = x;
for (int j = 1; j <= si; ++j)
f[i][j] = f[f[i][j - 1]][j - 1];
DFS(i);
}
rfn[x] = now;
return;
}
void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
return;
}
void pushdown(int p) {
if (t[p].d) {
t[lt].d += t[p].d;
t[rt].d += t[p].d;
t[lt].u += t[p].d *
(t[lt].r - t[lt].l + 1);
t[rt].u += t[p].d *
(t[rt].r - t[rt].l + 1);
t[p].d = 0;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].u = a[tab[l]];
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void add(int p, int x, int v) {
t[p].u += v;
if (t[p].l == t[p].r) return;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) add(lt, x, v);
else add(rt, x, v);
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d += v;
t[p].u += (t[p].r - t[p].l + 1) * v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) add(lt, l, r, v);
if (r > mid) add(rt, l, r, v);
pushup(p);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int res = 0,
mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) res = ask(lt, l, r);
if (r > mid) res += ask(rt, l, r);
return res;
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = si; ~i; --i) {
if (dep[f[x][i]] >= dep[y])
x = f[x][i];
}
if (x == y) return x;
for (int i = si; ~i; --i) {
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void Add(int x, int v) {
int rlca = LCA(r, x);
if (x == r) add(1, 1, n, v);
else if (rlca != x)
add(1, dfn[x], rfn[x], v);
else {
add(1, 1, n, v);
int p = r;
for (int i = si; ~i; --i) {
if (dep[f[p][i]] >= dep[x] + 1)
p = f[p][i];
}
add(1, dfn[p], rfn[p], -v);
}
return;
}
void tAdd(int x, int y, int v) {
int llca = LCA(r, x), rlca = LCA(r, y),
ulca = LCA(x, y);
if (dep[llca] >= dep[rlca] &&
dep[llca] >= dep[ulca]) Add(llca, v);
else if (dep[rlca] >= dep[llca] &&
dep[rlca] >= dep[ulca]) Add(rlca, v);
else Add(ulca, v);
return;
}
int tAsk(int x) {
int rlca = LCA(r, x);
if (x == r) return t[1].u;
if (rlca != x)
return ask(1, dfn[x], rfn[x]);
int p = r;
for (int i = si; ~i; --i) {
if (dep[f[p][i]] >= dep[x] + 1)
p = f[p][i];
}
return t[1].u - ask(1, dfn[p], rfn[p]);
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(n), read(q), r = 1;
si = log(n) / log(2.0);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i < n; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
dep[0] = 1, DFS(1), dep[0] = 0;
bld(1, 1, n);
while (q--) {
read(ty);
if (ty == 1) read(r);
else if (ty == 2) {
read(x), read(y), read(v);
tAdd(x, y, v);
}
else {
read(x);
print(tAsk(x), '\n');
}
}
return 0;
}
} // namespace XSC062
#undef int