251222 lxl 讲题

P5607 [Ynoi2013] 无力回天 NOI2017

对元素出现次数进行根号分治。如果 \(cnt\ge B\)，直接 bitset 暴力，否则把 \(nB\) 个二元组都搞出来直接哈希表维护。时间复杂度 \(O(\frac{n\sqrt n}{\sqrt w})\)。可以通过微调阈值卡过。

CF407E k-d-sequence

先按 \(a_i\bmod d\) 分为若干连续段，然后只需统计段内的贡献即可。一个段合法当且仅当 \(\frac{mx-mn}{d}\le \frac{r-l}{d}+k\)。于是对 \(r\) 扫描线，用线段树维护单调栈再加一个线段树上二分即可。

P8990 [北大集训 2021] 小明的树

发现合法当且仅当黑点形成一个连通块。于是用点数减边数进行刻画，只有这玩意取到最小值 \(1\) 的时候才合法。于是用线段树维护时间轴，以及维护最小值的贡献和。为了支持区间修改，需要记一下区间最小值的数量。

P7560 [JOISC 2021] フードコート (Day1)

区间加，区间 ckmax 和单点查询可以直接使用线段树维护。先把所有询问点到最终队尾的距离求出来，然后用另一棵线段树时光倒流进行简单维护即可。

CF1814F Communication Towers

考虑线段树分治，对每个点维护一个 tag 表示给并查集中的所有儿子都加上这个 tag。在合并 fa[x]=y 时执行 tag[x]-=tag[y]，撤销时执行 tag[x]+=tag[y]，修改直接 tag[find(1)]++ 即可。

P11706 「KTSC 2020 R1」穿越

对于一组 \(a,b\) 肯定就是线段树优化 dp 模板。考虑处理多组询问，可以把一种方案的代价表示为 \(ax+by\) 表示两种操作各用了 \(x,y\) 次。注意到我们只关心 \((x,y)\) 形成的下凸壳上的点。根据经典结论下凸壳的点数是不超过 \(V^{2/3}\) 的，其中 \(V\) 表示值域。于是直接线段树维护凸壳即可做到 \(O(n^{5/3}\log n+q\log n)\)。

P5608 [Ynoi2013] 文化课

为了支持区间推平数字，我们需要记录区间内加号和乘号形成的多项式。根据经典结论这种多项式的项数肯定是 \(O(\sqrt{len})\) 的。发现线段树上区间修改的 \(O(\log n)\) 段区间的多项式项数之和其实也是 \(O(\sqrt n)\) 级别的（等比数列）。因此怎么做时间复杂度都是对的。

代码

#include<iostream>
#include<vector>
#include<cmath>
#include<cassert>
#define print(x) { cout << #x"=" << (x) << '\n'; }
#define print2(x, y) { cout << #x","#y"=" << (x) << "," << y << '\n'; }
#define ll long long
#define int unsigned int
using namespace std;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

inline void init(int a, int b) {}
inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

int n, m;
int a[N], b[N];

namespace SegT {
    struct myPair {
        int val, cnt;
        inline myPair() : val(), cnt() {}
        inline myPair(int _v, int _c) : val(_v), cnt(_c) {}
    };
    struct Node {
        /*
        sum:  区间和
        mul:  区间product，两个都是用来支持符号推平的
        lm:   左侧乘法连续段的值，用来处理合并区间时连续段的合并
        rm:   右侧乘法连续段的值
        llen: 左侧乘法连续段的长度，用来支持区间推平数字后更新 lm
        rlen: 右侧乘法连续段的长度
        lo:   最左侧那个数是啥，用来支持区间推平加法后更新 lm
        ro:   最右侧那个数是啥
        ans:  区间答案
        tag0: 0表示推平加法，1表示推平乘法，-1表示没有
        tag1: 推平数字，-1表示没有
        */
        int sum, mul, lm, rm, llen, rlen, lo, ro, rs, ans, tag0, tag1, len;
        vector<myPair> num;
        inline Node() : sum(), mul(), lm(), rm(), llen(), rlen(), lo(), ro(), rs(), ans(), tag0(-1), tag1(-1), len() {}
    } tr[4 * N];
    // query 函数的返回值类型，single 表示是否为一个段
    struct res_type {
        int ans, lm, rm, rs; bool single;
        inline res_type() : ans(), lm(), rm(), single(), rs() {};
        inline res_type(int _ans, int _lm, int _rm, int _rs, bool _single) : 
            ans(_ans), lm(_lm), rm(_rm), rs(_rs), single(_single) {}
        inline res_type(const Node &val) : ans(val.ans), lm(val.lm), rm(val.rm), rs(val.rs), single(val.llen == val.len) {}
        inline res_type operator+(const res_type &b) const {
            if(rs) return res_type(
                ((ll)rm * b.lm % MOD + ans + b.ans - rm - b.lm + MOD + MOD) % MOD,
                (ll)lm * (single ? b.lm : 1) % MOD,
                (ll)b.rm * (b.single ? rm : 1) % MOD,
                b.rs,
                single && b.single
            );
            else return res_type(
                (ans + b.ans) % MOD,
                lm,
                b.rm,
                b.rs,
                false
            );
        }
    };
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    // 多项式相加
    vector<myPair> merge(const vector<myPair> &a, const vector<myPair> &b) {
        vector<myPair> res;
        int j = 0;
        for(int i = 0; i < a.size(); i++) {
            while(j < b.size() && b[j].val < a[i].val) res.push_back(b[j++]);
            res.push_back(a[i]);
            if(j < b.size() && b[j].val == a[i].val) res.back().cnt += b[j].cnt, ++j;
        }
        while(j < b.size()) res.push_back(b[j++]);
        return res;
    }
    // 合并多项式中的两项，也即左右区间中间如果是乘号的话需要合并
    void update(vector<myPair> &a, int x, int y) {
        assert(x);
        assert(y);
        for(int i = 0; i < a.size(); i++) {
            if(a[i].val == x) a[i].cnt--;
            if(a[i].val == y) a[i].cnt--;
            if(a[i].val == x + y) { a[i].cnt++; return; }
            if(a[i].cnt == 0) {
                for(int j = i + 1; j < a.size(); j++) {
                    swap(a[j - 1], a[j]);
                }
                a.pop_back();
                i--;
            }
        }
        a.push_back({x + y, 1});
        for(int i = a.size() - 1; i >= 1; i--) {
            if(a[i].val < a[i - 1].val) swap(a[i - 1], a[i]);
        }
    }
    inline void spread0(int p, int tg) {
        tr[p].tag0 = tg;
        if(tg == 0) {
            tr[p].ans = tr[p].sum;
            tr[p].lm = tr[p].lo; tr[p].llen = 1;
            tr[p].rm = tr[p].ro; tr[p].rlen = 1;
            tr[p].num.clear();
            tr[p].num.push_back((myPair){1, tr[p].len});
        } else {
            tr[p].ans = tr[p].lm = tr[p].rm = tr[p].mul;
            tr[p].llen = tr[p].rlen = tr[p].len;
            tr[p].num.clear();
            tr[p].num.push_back((myPair){tr[p].len, 1});
        }
    }
    inline void spread1(int p, int tg) {
        tr[p].tag1 = tr[p].lo = tr[p].ro = tg;
        init(tg, tr[p].len);
        tr[p].sum = (ll)tg * tr[p].len % MOD;
        tr[p].mul = qpow(tg, tr[p].len);
        tr[p].lm = qpow(tg, tr[p].llen);
        tr[p].rm = qpow(tg, tr[p].rlen);
        tr[p].ans = 0;
        for(myPair &i : tr[p].num) add(tr[p].ans, (ll)i.cnt * qpow(tg, i.val) % MOD);
    }
    inline void push_down(int p) {
        if(~tr[p].tag0) {
            tr[lc(p)].rs = tr[p].tag0;
            tr[rc(p)].rs = tr[p].rs;
            spread0(lc(p), tr[p].tag0);
            spread0(rc(p), tr[p].tag0);
            tr[p].tag0 = -1;
        }
        if(~tr[p].tag1) {
            spread1(lc(p), tr[p].tag1);
            spread1(rc(p), tr[p].tag1);
            tr[p].tag1 = -1;
        }
    }
    inline void push_up(int p) {
        Node &l = tr[lc(p)], &r = tr[rc(p)], &cur = tr[p];
        bool md = l.rs;
        cur.sum = (l.sum + r.sum) % MOD;
        cur.mul = (ll)l.mul * r.mul % MOD;
        cur.lm = (ll)l.lm * (md && l.llen == l.len ? r.lm : 1) % MOD;
        cur.rm = (ll)r.rm * (md && r.rlen == r.len ? l.rm : 1) % MOD;
        cur.lo = l.lo; cur.llen = l.llen + (md && l.llen == l.len ? r.llen : 0);
        cur.ro = r.ro; cur.rlen = r.rlen + (md && r.rlen == r.len ? l.rlen : 0);
        cur.rs = r.rs;
        if(md == 0) cur.ans = (l.ans + r.ans) % MOD;
        else cur.ans = ((ll)l.rm * r.lm % MOD + l.ans + r.ans - l.rm - r.lm + MOD + MOD) % MOD;
        cur.num = merge(l.num, r.num);
        if(md) update(cur.num, l.rlen, r.llen);
    }
    void build(int p, int l, int r) {
        tr[p].len = r - l + 1;
        tr[p].num.reserve((int)sqrt(tr[p].len * 2) + 2);
        if(l == r) {
            tr[p].ans = tr[p].sum = tr[p].mul = tr[p].lm = tr[p].rm = tr[p].lo = tr[p].ro = a[l];
            tr[p].llen = tr[p].rlen = 1;
            tr[p].rs = b[r];
            tr[p].num.push_back((myPair){1, 1});
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void modify0(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            tr[p].rs = v;
            spread0(p, v);
            return;
        }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) modify0(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify0(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    void modify1(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            spread1(p, v);
            return;
        }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) modify1(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify1(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    res_type query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return res_type(tr[p]);
        }
        int mid = (l + r) >> 1; push_down(p);
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        return query(lc(p), l, mid, ql, qr) + query(rc(p), mid + 1, r, ql, qr);
    }
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] %= MOD;
    for(int i = 1; i <= n - 1; i++) cin >> b[i];

    SegT::build(1, 1, n);
    while(m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> x;
            SegT::modify1(1, 1, n, l, r, x % MOD);
        } else if(op == 2) {
            cin >> x;
            SegT::modify0(1, 1, n, l, r, x);
        } else {
            cout << SegT::query(1, 1, n, l, r).ans << '\n';
        }
    }

    return 0;
}

qoj1851 Directed Acyclic Graph

发现不比 DAG 可达性更容易，因此时间复杂度至少为 \(O(\frac{n^2}{w})\)。考虑操作分块，对一个块内的 \(B\) 个操作，我们希望对每个点求出最后一次赋值操作，以及赋值操作之后 ckmin 操作的权值最小值。前者直接拓扑排序即可，后者考虑将操作按照权值重新排序，用 bitset 维护可以到达某个点并且在时间 tm 之后的所有 ckmin 操作的 bitmask 然后直接取 lowbit 即可。

块长 \(B\) 取多少不会很影响复杂度，可以直接取 \(B=w\) 这样可以用 unsigned long long 代替 bitset。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int W = 64;
typedef unsigned long long ull;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Op {
    int tp, x, y;
    inline bool operator<(const Op &b) const {
        if(tp != b.tp) return tp > b.tp;
        return y < b.y;
    }
} buf[80]; int top;

int q[N], tm[N], tq;

int n, m, nq;
int ind[N], a[N];

int que[N], hd, tl;
int tmp[N];

int mx_tm[N], mn_val[N];
int swp[N], iswp[N];

ull tm_msk[80], rch_msk[N];

inline void clear() {
    for(int i = 1; i <= n; i++) {
        mx_tm[i] = mn_val[i] = 0;
        rch_msk[i] = 0;
    }
    for(int i = 1; i <= 64; i++) {
        tm_msk[i] = 0;
    }
}
inline void init_que() {
    hd = 1, tl = 0;
    for(int i = 1; i <= n; i++) {
        tmp[i] = ind[i];
        if(tmp[i] == 0) que[++tl] = i;
    }
}

void flush_qr() {
    for(int i = 1; i <= n; i++) rch_msk[i] = 0;
    for(int i = 1; i <= top; i++) {
        rch_msk[buf[i].x] |= (1ull << i - 1);
    }
    init_que();
    while(hd <= tl) {
        int u = que[hd++];
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            rch_msk[v] |= rch_msk[u];
            if(--tmp[v] == 0) que[++tl] = v;
        }
    }
    for(int id = 1; id <= tq; id++) {
        int x = q[id];
        int res = a[x];
        for(int i = 1; i <= tm[id]; i++) {
            if(rch_msk[x] >> i - 1 & 1) {
                if(buf[i].tp == 1) res = buf[i].y;
                else res = min(res, buf[i].y);
            }
        }
        cout << res << '\n';
    }
    tq = 0;
}

void flush() {
    clear();
    for(int i = 1; i <= W; i++) swp[i] = i;
    sort(swp + 1, swp + 1 + W, [](int i, int j){ return buf[i] < buf[j]; });
    for(int i = 1; i <= W; i++) iswp[swp[i]] = i;
    for(int i = W; i >= 0; i--) {
        tm_msk[i] = tm_msk[i + 1];
        if(buf[i].tp == 2) tm_msk[i] |= (1ull << iswp[i] - 1);
    }
    for(int i = 1; i <= W; i++) {
        if(buf[i].tp == 1) mx_tm[buf[i].x] = i;
        rch_msk[buf[i].x] |= (1ull << iswp[i] - 1);
    }
    init_que();
    while(hd <= tl) {
        int u = que[hd++];
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            mx_tm[v] = max(mx_tm[v], mx_tm[u]);
            rch_msk[v] |= rch_msk[u];
            if(--tmp[v] == 0) que[++tl] = v;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(mx_tm[i]) a[i] = buf[mx_tm[i]].y;
        ull tmp = rch_msk[i] & tm_msk[mx_tm[i]];
        if(tmp) a[i] = min(a[i], buf[swp[__builtin_ffsll(tmp)]].y);
    }
    top = 0;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> nq;
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v);
        ind[v]++;
    }

    while(nq--) {
        int op, x, y;
        cin >> op;
        if(op == 1) {
            cin >> x >> y;
            buf[++top] = (Op){1, x, y};
        } else if(op == 2) {
            cin >> x >> y;
            buf[++top] = (Op){2, x, y};
        } else if(op == 3) {
            cin >> x;
            q[++tq] = x;
            tm[tq] = top;
        }
        if(top == W) flush_qr(), flush();
    }
    flush_qr();

    return 0;
}

P7881 [Ynoi2006] rmpq

考虑操作分块，每 \(B=\sqrt n\) 个修改操作分一块。发现一个块会将整个平面分为 \(O(B^2)=O(n)\) 份。考虑如何求出 \(O(n)\) 个小块每块的 Data，考虑对时间分治，合并两个子问题可以做到 \(O(B^2)\)，时间复杂度就是 \(T(n)=2T(\frac{n}{2})+O(n^2)\)。查询时把之前的所有块扫一遍，每个块内分别二分答案，操作次数是不带 \(\log\) 的。

为了进一步优化，考虑二进制分组 trick，这样合并的复杂度和分治是一样的，但是散块的 \(O(B)\) 个操作合并成了 \(O(\log B)\) 个块，可以让操作次数更少。

AT_abc369_g [ABC369G] As far as possible

发现贪心是对的，每次选最远的一个点加入，可以证明它一定不会被之后删掉。发现第一次取的是以 \(1\) 开头的长链，第二次取的是第二长的长链，以此类推。于是直接把所有长链搞出来排序即可。

P12462 [Ynoi Easy Round 2018] 星野爱久爱海

问题的关键是最大的最小斯坦纳树具有可合并性，然后随便维护区间信息就是对的。

我们尝试证明其可合并性。考虑证明向集合 \(S\) 中加入一个点 \(x\)，不会向最优解中添加除了 \(x\) 之外的其它节点。由于插入 \(x\) 后点集的直径至少有一端是在原先的集合中，考虑以这个点为根进行长剖，分讨一下插入 \(x\) 之后的几种情况（可能会影响若干条长链），然后再分讨删掉的最短的那条重链在哪，感觉差不多能证出来。

由于具有结合律，所以可以用线段树维护。也可以 st 表套分块做到线性。

CF1476G Minimum Difference

发现出现次数只有不同的 \(O(\sqrt n)\) 种。因此直接带修莫队 \(O(\sqrt n)\) 回答单次询问做完了。

P9991 [Ynoi Easy Round 2023] TEST_107

简单支配对和线段树上二分。

P9809 [SHOI2006] 作业 Homework

简单根号分治