ds 随笔 2

不定时更新喏。

代码中可能省略了包含 #define int long long 的头。

CF1555F Good Graph

CF986E Prince's Problem

Luogu P7630 [COCI2011-2012#1] SKAKAC

CF1223F Stack Exterminable Arrays

Luogu P5439 【XR-2】永恒

CF1753F Minecraft Series

CF1555F Good Graph

题意：

若一个图中全部简单环的权重都是 $1$ ，那么我们称这个图为好图，而一个图若不是好图，那么这个图则是坏图。

最开始，图是空的。接着会有 $q$ 个询问。每个询问为以下格式

$u, v, x$ — 若不会使图变成坏图，则在点 $u$ 与点 $v$ 间加一条权值为 $x$ 的边。

对于每一个询问输出到底加不加这条边。

$n \le 3\times10^5,q\le5\times10^5$ 。

思路：

考虑维护生成树 $T$ 。

对于一条边 $u, v$ ，如果 $u, v$ 不联通，可以直接加入生成树 $T$ ；如果 $T$ 上 $u, v$ 之间路径的异或和与 $w$ 异或不为 $0$ 则肯定不能加。

我们发现如果两个环有交，那么一定可以构造出一个 $0$ 环。

因此如果 $u, v$ 之间路径上没有边属于别的环，那么加入这条边，并且在树上将这些边都标注，

否则就加不了。

时间复杂度 $O(m \log n)$ 。

code

const int N = 1e6 + 10;
int ch[N][2], fa[N];
unsigned v[N], sum[N];
mt19937 rng(random_device{}());
bool lzy[N];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
inline bool isroot(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
inline void connect(int u, int v, bool k) { ch[u][k] = v, fa[v] = u; }
inline bool get(int u) { return rc(fa[u]) == u; }
inline void pushup(int u) {
    if (u) sum[u] = sum[lc(u)] ^ v[u] ^ sum[rc(u)];
}
inline void maketag(int u) { lzy[u] ^= 1, swap(lc(u), rc(u)); }
inline void pushdown(int u) {
    if (lzy[u]) {
        if (lc(u)) maketag(lc(u));
        if (rc(u)) maketag(rc(u));
        lzy[u] = 0;
    }
}
inline void update(int u) {
    if (!isroot(u)) update(fa[u]);
    pushdown(u);
}
inline void rotate(int u) {
    bool k = get(u), kf = get(fa[u]);
    int f = fa[u];
    if (isroot(f))
        fa[u] = fa[f];
    else
        connect(fa[f], u, kf);
    connect(f, ch[u][k ^ 1], k), connect(u, f, k ^ 1);
    pushup(f), pushup(u);
}
inline void splay(int u) {
    update(u);
    for (int f = fa[u]; f = fa[u], !isroot(u); rotate(u))
        if (!isroot(f)) rotate(get(u) == get(f) ? f : u);
}
inline void access(int u) {
    for (int f = 0; u; u = fa[f = u]) splay(u), rc(u) = f, pushup(u);
}
inline void makeroot(int u) { access(u), splay(u), maketag(u); }
inline void split(int u, int v) { makeroot(u), access(v), splay(v); }
inline int find(int u) {
    access(u), splay(u), pushdown(u);
    while (lc(u)) pushdown(u = lc(u));
    return splay(u), u;
}
inline void link(int u, int v) {
    if (find(u) == find(v)) return;
    makeroot(u), fa[u] = v;
}
inline void cut(int u, int v) {
    if (find(u) != find(v)) return;
    split(u, v);
    if (lc(v) == u && !rc(u)) lc(v) = fa[u] = 0, pushup(v);
}
int n, m;
void ran(int u) {
    if (u > n) v[u] = rng();
    pushdown(u);
    if (lc(u)) ran(lc(u));
    if (rc(u)) ran(rc(u));
    pushup(u);
}
int main() {
    read(n, m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        read(u, v, w), ::v[i + n] = w, pushup(i + n);
        if (find(u) != find(v))
            link(u, i + n), link(i + n, v), println("YES"s);
        else {
            split(u, v);
            if ((sum[v] ^ w) == 1) println("YES"s), ran(v);
            else println("NO"s);
        }
    }
    return 0;
}

CF986E Prince's Problem

题意：

给你一颗树，点权 $a_i \le 10^7$ 。

每次询问 $u, v, t$ ，求 $\prod_{w\in \text{path}(u, v)} \gcd(a_w, t)$ 。

点数与询问数 $\le 10^5$ 。

思路：

对于每个质数分别算贡献就好了，我们发现 $\text{gcd}$ 实际上是次数上取 $\min$ ，枚举 $a_w$ 上的次数，然后用 $\text{ds}$ 随便维护即可。

代码很不优美，好像可以树上差分来着，，。代码复杂度 $O((q + n) \log n \log V )$ 。

code

const int V = 1e7 + 10, N = 1e5 + 10;
const ll P = 1e9 + 7;
int prime[V / 10], cnt, d[V], id[V];
bool vis[V];
inline ll qpw(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % P;
        a = a * a % P, b >>= 1;
    }
    return ans;
}
inline void init(int n) {
    vis[1] = 1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) d[prime[++cnt] = i] = i, id[i] = cnt;
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1, d[i * prime[j]] = prime[j];
            if (!(i % prime[j])) break;
        }
    }
}
int n, fa[N], dfn[N], son[N], dfncnt, siz[N], top[N], dep[N], q, mx[N], qu[N], qv[N], ql[N];
vector<int> vec[N];
long long w[N], res[N];
vector<pair<int, int> > dot[V / 10], que[V / 10];
inline void update(int u, long long v) {
    while (u <= n) w[u] += v, u += u & -u;
}
inline long long query(int u) {
    long long ans = 0;
    while (u) ans += w[u], u ^= u & -u;
    return ans;
}
inline vector<pair<int, int> > frac(int c) {
    vector<pair<int, int> > ans;
    while (d[c]) {
        int t = d[c];
        c /= d[c];
        if (ans.size() && ans.back().first == t) ++ans.back().second;
        else ans.emplace_back(t, 1);
    }
    return ans;
}
void dfs(int u) {
    dfn[u] = ++dfncnt, siz[u] = 1;
    for (int v : vec[u])
        if (v != fa[u]) {
            fa[v] = u, dep[v] = dep[u] + 1, dfs(v), siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) son[u] = v;
        }
}
void dfs2(int u) {
    for (int v : vec[u])
        if (v != fa[u]) top[v] = (v == son[u]) ? top[u] : v, dfs2(v);
}
inline int lca(int u, int v) {
    while (top[u] != top[v])
        dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
inline ll queryx(int i) { return query(dfn[qu[i]]) + query(dfn[qv[i]]) - query(dfn[ql[i]]) - query(dfn[fa[ql[i]]]); }
void work(int x) {
    for (int i = 1; i <= mx[x]; i++) {
        for (auto [v, u] : dot[x])
            if (v >= i) update(dfn[u], 1), update(dfn[u] + siz[u], -1);
        for (auto [v, u] : que[x])
            if (v >= i) res[u] = res[u] * qpw(prime[x], queryx(u)) % P;
        for (auto [v, u] : dot[x])
            if (v >= i) update(dfn[u], -1), update(dfn[u] + siz[u], 1);
    }
}
int main() {
    init(V - 10);
    read(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        read(u, v), vec[u].push_back(v), vec[v].push_back(u);
    }
    dfs(1), dfs2(top[1] = 1);
    for (int i = 1; i <= n; i++) {
        ll c;
        read(c);
        auto t = frac(c);
        for (auto [a, b] : t) dot[id[a]].emplace_back(b, i);
    }
    read(q), fill(res + 1, res + q + 1, 1);
    for (int i = 1; i <= q; i++) {
        read(qu[i], qv[i]), ql[i] = lca(qu[i], qv[i]);
        ll w;
        read(w);
        auto t = frac(w);
        for (auto [a, b] : t) que[id[a]].emplace_back(b, i), chkmax(mx[id[a]], b);
    }
    for (int i = 1; i <= cnt; i++)
        if (que[i].size()) work(i);
    for (int i = 1; i <= q; i++) println(res[i]);
    return 0;
}

P7630 [COCI2011-2012#1] SKAKAC

题意：

Mirko 和 Slavko 正在玩一个游戏。

Mirko 把一个骑士棋子放在一个 $N \times N$ 的棋盘上，蒙住 Slavko 的眼睛，接下来将骑士移动 $T$ 步，每秒走一步。之后，Slavko 必须猜出骑士的最终位置才能获胜。

这个游戏中的棋盘是特别的，因为每个格子都有一部分时间被禁止通行。更准确地说，每个格子上都有一个为正整数的标记，标有数字 $K$ 的正方形只有在第 $0,K,K \times 2,K \times 3,...$ 秒内才是允许通行的，在其他时间这个格子都禁止通行。当然，骑士只能在某个格子允许通行时走到该格子。

游戏从第 $0$ 秒开始。每秒钟 Mirko 必须将骑士移动一步（根据国际象棋的规则，骑士走日字，类似中国象棋中的马）。请帮助 Slavko 写一个程序来计算出所有 $T$ 秒过后骑士可能位于的格子。

$1 \le n \le 30$ ， $1 \le T \le 10^6$ 。

思路：

把 $30$ 位压成一个 unsigned 模拟即可。

时间复杂度随实现决定。

时间复杂度 $O(?)$ 。

原题有点卡空间

code

const int N = 32, V = 5e5 + 10;
struct Edge {};
unsigned c[N], k[9][N], cup[V][N];
int a[N][N];
unsigned mT;
int n, T, x, y;
unsigned pre[N], nxt[N];
inline void solve(int l, int r) {
    memset(cup, 0, sizeof(cup));
    if (l > r) return;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (a[i][j] > 8) {
                for (int t = a[i][j]; t <= T; t += a[i][j])
                    if (t >= l && t <= r) cup[t - l][i] |= 1u << j - 1;
            }
        }
    for (int t = l; t <= r; t++) {
        unsigned *c = cup[t - l];
        for (int k = 1; k < 9; k++)
        if (!(t % k))
        for (int i = 1; i <= n; i++) c[i] |= ::k[k][i];
        memset(nxt, 0, sizeof(nxt));
        for (int i = 1; i <= n; i++) {
            if (i + 1 <= n) nxt[i + 1] |= pre[i] << 2, nxt[i + 1] |= pre[i] >> 2;
            nxt[i - 1] |= pre[i] << 2, nxt[i - 1] |= pre[i] >> 2;
            if (i >= 2) nxt[i - 2] |= pre[i] << 1, nxt[i - 2] |= pre[i] >> 1;
            if (i + 2 <= n) nxt[i + 2] |= pre[i] << 1, nxt[i + 2] |= pre[i] >> 1;
        }
        memcpy(pre, nxt, sizeof(pre));
        for (int i = 1; i <= n; i++) pre[i] &= mT & c[i];
    }
}
int main() {
    read(n, T), mT = (1u << n) - 1, read(x, y), pre[x] |= 1u << y - 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            read(a[i][j]);     
            if (a[i][j] <= 8) k[a[i][j]][i] |= 1u << j - 1;
        }
    solve(1, T >> 1), solve((T >> 1) + 1, T);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += __builtin_popcount(pre[i]);
    println(ans);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (pre[i] & ((1u << j - 1))) println(i, j);
    return 0;
}

CF1223F Stack Exterminable Arrays

题意：

给一个序列进行栈操作，从左到右入栈，若当前入栈元素等于栈顶元素则栈顶元素出栈，否则当前元素入栈。若进行完操作后栈为空，这说这个序列是可以被消除的。

给你一个长度为 $n$ 的序列 $a$ ，问 $a$ 有多少子串是可以被消除的。

思路：

分治，哈希，然后 $\text{map}$ 。

时间复杂度 $O(n \log^2 n)$ 。

当然能做到单 $\log$ ，存在线性哈希做法。

code

const int N = 1e6 + 10;
const __uint128_t P = 1000000000000000003;
__uint128_t pw[N];
int n, m, a[N];
ull h[N];
int st[N], top;
ll ans = 0;
map<ull, int> mp;
void solve(int L, int R) {
    if (L == R) return;
    int M = L + R >> 1;
    solve(L, M), solve(M + 1, R);
    clear(mp);
    top = 0;
    for (int i = M + 1; i <= R; i++) {
        if (st[top] == a[i])
            --top;
        else
            st[++top] = a[i], h[top] = (h[top - 1] * 998244353 + a[i]) % P;
        ++mp[h[top]];
    }
    top = 0;
    for (int i = M; i >= L; i--) {
        if (st[top] == a[i])
            --top;
        else
            st[++top] = a[i], h[top] = (h[top - 1] * 998244353 + a[i]) % P;
        ans += mp[h[top]];
    }
}
inline void work() {
    ans = 0;
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    solve(1, n), println(ans);
}
int main() {
    int T;
    for (read(T); T--;) work();
    return 0;
}

P5439 【XR-2】永恒

简要题意：

$\text{dep}$ 为点到根路径边数。

求

$\sum_{k = path(u, v), 1 \le u \le v \le n}\sum_{x \in K, y \in K, x < y} \text{dep}(\mathrm{LCA}(x, y))$ 。

$n \le 3 \times 10^5$ 。

思路：

对于 $\text{LCA}$ ，有个经典套路：

$x$ 到根路径（边权）权值 $+1$ ， $y$ 到根求路径（边权）权值和，那么求得的和就是答案 $\text{LCA}$ 深度。

有这个套路可以快速维护一个点和动态点集的 $\text{LCA}$ 深度和。

我们发现对于 $(u, v)$ ，如果 $(u, v)$ 不成祖孙关系，则贡献次数为 $siz(u)siz(v)$ ，这部分贡献可以用那个套路直接算，如果是祖孙关系，则贡献需要修正。

对于祖孙关系，用一次 $\text{dfs}$ 维护 $\text{dfs}$ 栈内点集与当前点权乘上一个系数加到答案中即可。

code

const int N = 1e6 + 10;
int a[N], rt1, rt2, f[N], sz[N], f2[N];
ll v[N];
int ch[N][2], fa[N], siz[N], n, m, ts[N];
ll sum[N], tag[N];
bool lzy[N];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
inline bool isroot(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
inline void connect(int u, int v, bool k) { ch[u][k] = v, fa[v] = u; }
inline bool get(int u) { return rc(fa[u]) == u; }
inline void pushup(int u) {
    if (u)
        sum[u] = sum[lc(u)] + v[u] + sum[rc(u)],
        siz[u] = siz[lc(u)] + ts[u] + siz[rc(u)];
}
inline void maketag(int u) { lzy[u] ^= 1, swap(lc(u), rc(u)); }
inline void makeadd(int u, ll v) {
    tag[u] += v, ::v[u] += (u == 1 ? 0 : v), sum[u] = sum[u] + v * siz[u];
}
inline void pushdown(int u) {
    if (lzy[u]) {
        if (lc(u)) maketag(lc(u));
        if (rc(u)) maketag(rc(u));
        lzy[u] = 0;
    }
    if (tag[u]) {
        if (lc(u)) makeadd(lc(u), tag[u]);
        if (rc(u)) makeadd(rc(u), tag[u]);
        tag[u] = 0;
    }
}
inline void update(int u) {
    if (!isroot(u)) update(fa[u]);
    pushdown(u);
}
inline void rotate(int u) {
    bool k = get(u), kf = get(fa[u]);
    int f = fa[u];
    if (isroot(f))
        fa[u] = fa[f];
    else
        connect(fa[f], u, kf);
    connect(f, ch[u][k ^ 1], k), connect(u, f, k ^ 1);
    sum[u] = sum[f], siz[u] = siz[f], pushup(f);
}
inline void splay(int u) {
    update(u);
    for (int f = fa[u]; f = fa[u], !isroot(u); rotate(u))
        if (!isroot(f)) rotate(get(u) == get(f) ? f : u);
}
inline void access(int u) {
    for (int f = 0; u; u = fa[f = u]) splay(u), rc(u) = f, pushup(u);
}
inline void makeroot(int u) { access(u), splay(u), maketag(u); }
inline void split(int u, int v) { makeroot(u), access(v), splay(v); }
inline int find(int u) {
    access(u), splay(u), pushdown(u);
    while (lc(u)) pushdown(u = lc(u));
    return splay(u), u;
}
inline void link(int u, int v) { makeroot(u), fa[u] = v; }
inline void cut(int u, int v) {
    split(u, v);
    if (lc(v) == u && !rc(u)) lc(v) = fa[u] = 0, pushup(v);
}
vector<int> vec[N], vec2[N];
void dfs(int u) {
    sz[u] = 1;
    for (int v : vec[u]) dfs(v), sz[u] += sz[v];
}
ll ans = 0;
const ll P = 998244353;
void dfsx(int u) {
    access(a[u]), splay(a[u]), ans = (ans + sum[a[u]] % P * sz[u]) % P;
    bool fl = 1;
    for (int v : vec[u]) {
        makeadd(a[u], n - sz[v] - sz[u]);
        dfsx(v);
        access(a[u]), splay(a[u]), makeadd(a[u], sz[v] + sz[u] - n);
    }
}
char str[N];
int main() {
    read(n, m);
    for (int i = 1; i <= n; i++) {
        read(f[i]);
        if (!f[i])
            rt1 = i;
        else
            vec[f[i]].push_back(i);
    }
    for (int i = 1; i <= m; i++) ts[i] = 1;
    for (int i = 1; i <= m; i++) {
        read(f2[i]), fa[i] = f2[i];
        if (!f2[i])
            rt2 = i, ts[i] = 0;
    }
    for (int i = 1; i <= m; i++) pushup(i);
    dfs(rt1), read_cstr(str + 1);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) {
        access(a[i]), splay(a[i]);
        ans = (ans + sum[a[i]] % P * sz[i]) % P;
        makeadd(a[i], sz[i]);
    }
    memset(sum, 0, sizeof(sum));
    memset(tag, 0, sizeof(tag));
    memset(v, 0, sizeof(v));
    dfsx(rt1);
    println((ans % P + P) % P);
    return 0;
}

CF1753F Minecraft Series

这个题意也不好简化呀。

Misha 受到曼哈顿地区道路的启发，在《我的世界》里建造了一座城市，其可以视为一个 $n \times m$ 的表格。城里住着 $k$ 名学生，其中第 $i$ 名学生住在第 $x_i$ 行和第 $y_i$ 列的交叉处，每名学生都有一个易怒值 $w_i$ 。由于城市的规模很大，Misha 决定将剧集的故事情节限制在发生于某个正方形区域 $s$ 中，其各边均与坐标轴平行。正方形区域的边长应当是一个 $\geqslant 1$ 且 $\leqslant \min(n, m)$ 的整数。

根据情节，主角将会来到这座城市并意外进入正方形区域 $s$ 里。主角的易怒值为 $0$ ，所以他可以利用自己的领导才能召集一个由平静、不温不火和易怒的学生们组成的团队。

为了使团队有机动性并团结紧密，团队中所有学生的易怒值必须各不相同且必须能够组成一条连续的序列。形式上说，如果存在有学生的易怒值可以组成一条形如 $ l, l+1, \ldots, -1, 1, \ldots, r-1, r $ 的序列，其中 $ l \le 0 \le r $，那么主角就能召集一个由 $r - l + 1$ 人组成的团队（主角自己也在团队中）。

请注意，不一定要把正方形区域 $s$ 内的所有学生都加入团队。

Misha 觉得这个团队至少应该容纳 $t$ 人。他很想知道：这个表格里有多少个正方形区域可供主角召集一个团队？请帮他算一算。

思路：

这个题很难啊！！！

枚举正方形中心，对中心在同一条对角线上的正方形双指针。

然后，做完了！

很妙。

复杂度 $O(nm \sqrt k + k \sqrt {nm})$ 。

code

const int N = 4e4 + 10, K = 1e6 + 10;
set<int> s;
int p, n, m, k, t, mx, mn;
inline int id(int x, int y) { return (x - 1) * m + y; }
vector<int> c[N];
int pos[K];
struct Block {
    int v[K], vm[K];
    inline void update(int u, int val) { --u, vm[u >> 10] -= !!v[u], v[u] += val, vm[u >> 10] += !!v[u]; }
    inline int mex() {
        for (int i = 0; i <= (k + 1 >> 10); i++)
            if (vm[i] != p) {
                for (int j = i * p; j < (i + 1) * p; j++)
                    if (!v[j]) return j;
                return -1;
            }

        return -1;
    }
} ba, bb;
int fl = 0;
inline void update(int u, int val) {
    if (u > mx || u < mn || !u) return;
    if (u < 0)
        ba.update(-u, val);
    else
        bb.update(u, val);
}
inline int mex() { return ba.mex() + bb.mex() + 1; }
map<int, vector<int> > mp;
int main() {
    read(n, m, k, t), p = max(1.0, sqrt(k)), p = 1024;
    s.insert(0);
    for (int i = 1; i <= k; i++) {
        int x, y, v;
        read(x, y, v), c[id(x, y)].push_back(v), s.insert(v);
    }
    while (s.count(mn)) --mn;
    while (s.count(mx)) ++mx;
    for (int i = 0; i <= k + 1; i++) pos[i] = i / p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) mp[j - i].push_back(i);
    int ans = 0;
    for (auto &[u, k] : mp) {
        int l = 0;
        for (int r = 0; r < k.size(); r++) {
            for (int j = k[l]; j < k[r]; j++) {
                for (int v : c[id(k[r], j + u)]) update(v, 1);
                for (int v : c[id(j, k[r] + u)]) update(v, 1);
            }
            for (int v : c[id(k[r], k[r] + u)]) update(v, 1);
            // cout << "mex:" << mex() << endl;
            while (l <= r && mex() >= t) {
                for (int j = k[l] + 1; j <= k[r]; j++) {
                    for (int v : c[id(k[l], j + u)]) update(v, -1);
                    for (int v : c[id(j, k[l] + u)]) update(v, -1);
                }
                for (int v : c[id(k[l], k[l] + u)]) update(v, -1);
                l++;
            }
            ans += min(k[r], k[r] + u) - (r - l + 1);
        }
        if (l < k.size()) {
            int cl = k[l], cr = k.back();
            for (int i = cl; i <= cr; i++)
                for (int j = cl + u; j <= cr + u; j++)
                    for (int v : c[id(i, j)]) update(v, -1);
        }
    }
    println(ans);
    return 0;
}

ds-随笔-2

ds 随笔 2

CF1555F Good Graph

CF986E Prince's Problem

P7630 [COCI2011-2012#1] SKAKAC

CF1223F Stack Exterminable Arrays

P5439 【XR-2】永恒

CF1753F Minecraft Series