历史和线段树 以XJTU2023 J题为例

/*
 * @Author: JorD
 * @LastEditTime: 2023-05-25 12:23:35
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 5e5 + 10;
struct Tag{
    unsigned add, hadd, tim;
    void merge(Tag tmp){
        hadd += tmp.hadd + add * tmp.tim;
        add += tmp.add;
        tim += tmp.tim;
    }
};
struct Segtree{
    unsigned sum, hsum;
    Tag tag;
    void update(int len, Tag u){
        tag.merge(u);
        hsum += u.hadd * len + u.tim * sum;
        sum += u.add * len;
    }
}tr[N << 2];
void pushdown(int l, int r,int p){
    int mid = l + r >> 1;
    tr[p << 1].update(mid - l + 1, tr[p].tag);
    tr[p << 1|1].update(r - mid, tr[p].tag);
    tr[p].tag = {0, 0, 0};
}
void update(int cl, int cr, int l, int r, int p, Tag t){
    if(l > cr || r < cl) return;
    if(cl <= l && r <= cr){
        tr[p].update(r - l + 1, t);
        return;
    }
    int mid = l + r >> 1;
    pushdown(l, r, p);
    update(cl, cr, l, mid, p << 1, t);
    update(cl, cr, mid + 1, r, p << 1|1, t);
    tr[p].sum = tr[p << 1].sum + tr[p << 1|1].sum;
    tr[p].hsum = tr[p << 1].hsum + tr[p << 1|1].hsum;
}
unsigned query(int cl, int cr, int l, int r, int p){
    if(l > cr || r < cl) return 0;
    if(cl <= l && r <= cr){
        return tr[p].hsum;
    }
    int mid = l + r >> 1;
    pushdown(l, r, p);
    return query(cl, cr, l, mid, p << 1) + query(cl, cr, mid + 1, r, p << 1|1);
}
void build(int l, int r, int p){
    tr[p] = {0, 0, {0,0,0}};
    if(l == r) return;
    int mid = l + r >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1|1);
}
int last[N], id[N], a[N];
void Solve(){
    int n, m; cin >> n >> m;
    rep(i, 1, n){
        int x; cin >> x;
        a[i] = x;
        last[i] = id[x];
        id[x] = i;
    }
    vector<vector<pair<int,int>>> son(n + 1);
    rep(i, 1, m){
        int l, r; cin >> l >> r;
        son[r].push_back({l, i});
    }
    build(1, n, 1);
    vector<unsigned> res(m + 1);
    rep(r, 1, n){
        update(last[r] + 1, r, 1, n, 1, {1, 0, 0});
        update(1, n, 1, n, 1, {0, 0, 1});
        for(auto [l, i] : son[r]){
            res[i] = query(l, r, 1, n, 1);
        }
    }
    rep(i, 1, m) cout << res[i] << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}

在有向图中，除了需要考虑有向意义下是否存在环，有些时候还要考虑在无向意义下是否存在环。
例如

在 这题 中就有所体现。

鸽巢原理经典问题 选数
结论就是：$n$ 个位置放 $n + 1$ 个数必定有两个位置是相同，这也说明了一定有解。

题解

可持久化Trie
建树方式参考主席树

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 6e5 + 10;
struct Trie{
    int id, cnt;
}tr[N * 30][2];
int idx, root[N];
void dfs(int x, int i, int &clone, int p){
    if(i < 0) return;
    if(!clone) clone = ++ idx;
    int c = x >> i & 1;
    tr[clone][!c] = tr[p][!c];
    tr[clone][c].cnt = tr[p][c].cnt + 1;
    tr[clone][c].id = ++ idx;
    dfs(x, i - 1, tr[clone][c].id, tr[p][c].id);
}
int query(int x, int L, int R, int i){
    if(i < 0) return 0;
    int c = x >> i & 1;
    int cnt = tr[R][!c].cnt - tr[L][!c].cnt;
    if(cnt > 0) return (1 << i) + query(x, tr[L][!c].id, tr[R][!c].id, i - 1);
    else return query(x, tr[L][c].id, tr[R][c].id, i - 1);
}
void Solve(){
    int n, m;
    cin >> n >> m;
    int last = 0;
    dfs(0, 30, root[0], 0);
    rep(i, 1, n){
        int x; cin >> x;
        last ^= x;
        dfs(last, 30, root[i], root[i - 1]);
    }
    while(m --){
        char op; cin >> op;
        if(op == 'A'){
            int x;  cin >> x;
            last ^= x;
            n ++;
            dfs(last, 30, root[n], root[n - 1]);
        }else{
            int l, r, x; cin >> l >> r >> x;
            x ^= last;
            if(l == 1) cout << query(x, 0, root[r - 1], 30) << endl;
            else cout << query(x, root[l - 2], root[r - 1], 30) << endl;
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}

/*
 * @Author: JorD
 * @LastEditTime: 2023-01-07 07:23:47
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 2e5 + 10, inf = 1e9;
struct Segtree{
    int l, r, sum;
}tr[N << 5];
int a[N], root[N], idx;
void update(int pos, int l, int r, int p, int &clone){
    clone = ++ idx;
    tr[clone]= tr[p];
    if(l == r){
        tr[clone].sum ++;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(pos, l, mid, tr[p].l, tr[clone].l);
    else update(pos, mid + 1, r, tr[p].r, tr[clone].r);
    tr[clone].sum = tr[tr[clone].l].sum + tr[tr[clone].r].sum;
}
int query(int l, int r, int L, int R, int k){
    if(l == r){
        return l;
    }
    int mid = l + r >> 1;
    int sum = tr[tr[R].l].sum - tr[tr[L].l].sum;
    if(k > sum) return query(mid + 1, r, tr[L].r, tr[R].r, k - sum);
    else return query(l, mid, tr[L].l, tr[R].l, k); 
}
void Solve(){
    int n, m;
    cin >> n >> m;
    rep(i, 1, n){
        int x; cin >> x;
        update(x, - inf, inf, root[i - 1], root[i]);
    }
    while(m --){
        int l, r, k;
        cin >> l >> r >> k; 
        cout << query(- inf, inf, root[l - 1], root[r], k) << endl;
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}

可持久化 + 动态开点权值线段树

可持久化和普通的线段树的区别就是在修改的时候额外维护这一次的修改所带来的影响。
而修改带来影响的节点只影响了最多 $logn$ 个节点， 关于这一点，可以先做一下 这题 来具体感受一下。
具体实现只需要把修改了的点额外保存下来，作为历史版本。
关于持久化就介绍到这。接下来是这题的线段树定义。

先考虑一个简单的版本，对一个数组(静态的区间)求第k小, 很容易就知道线段树的解法，建立权值线段树，维护区间中的个数，然后二分。
那么我们现在只需要解决如何得到这样的一棵线段树。
因为询问的区间是连续的，所以可以依次从1 - n插入节点，建立历史版本。
到了实际需要使用的时候， 例如需要 $[L, R]$ 的区间，我们只需要通过两颗线段树历史版本 $L-1$ 和 $R$ 这两棵树的差值就可以得到了。

剩下的具体实现看代码吧。
其中 $p$ 和 $clone$ 分别表示待修改的版本和当前版本(修改后的版本)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, inf = 1e9;
struct Segtree{
    int l, r, sum;
}tr[N << 5];
int a[N], root[N], idx;
void update(int pos, int l, int r, int p, int &clone){
    clone = ++ idx;
    tr[clone]= tr[p];
    if(l == r){
        tr[clone].sum ++;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(pos, l, mid, tr[p].l, tr[clone].l);
    else update(pos, mid + 1, r, tr[p].r, tr[clone].r);
    tr[clone].sum = tr[tr[clone].l].sum + tr[tr[clone].r].sum;
}
int query(int l, int r, int L, int R, int k){
    if(l == r){
        return l;
    }
    int mid = l + r >> 1;
    int sum = tr[tr[R].l].sum - tr[tr[L].l].sum;
    if(k > sum) return query(mid + 1, r, tr[L].r, tr[R].r, k - sum);
    else return query(l, mid, tr[L].l, tr[R].l, k); 
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++){
        int x; scanf("%d", &x);
        update(x, -inf, inf, root[i - 1], root[i]);
    }
    while(m --){
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(-inf, inf, root[l - 1], root[r], k));
    }
    return 0;
}

支持历史修改和历史查询。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 1e6 + 10;
struct Segtree{
    int l, r, cnt;
}tr[N << 5];
int n, m;
int a[N], root[N], idx;
void build(int l, int r, int &p){
    if(!p) p = ++ idx;
    if(l == r){
        tr[p].cnt = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, tr[p].l);
    build(mid + 1, r, tr[p].r);
}
void update(int pos, int l, int r, int p, int &clone, int k){
    clone = ++ idx;
    tr[clone] = tr[p];
    if(l == r){
        tr[clone].cnt = k;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(pos, l, mid, tr[p].l, tr[clone].l, k);
    else update(pos, mid + 1, r, tr[p].r, tr[clone].r, k);
}
int query(int pos, int l, int r, int p, int &clone){
    clone = ++ idx;
    tr[clone] = tr[p];
    if(l == r){
        return tr[p].cnt;
    }
    int mid = l + r >> 1;
    if(pos <= mid) return query(pos, l, mid, tr[p].l, tr[clone].l);
    else return query(pos, mid + 1, r, tr[p].r, tr[clone].r);
}
void Solve(){
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    build(1, n, root[0]);
    rep(i, 1, m){
        int v, op;
        cin >> v >> op;
        if(op == 1){
            int x, y;
            cin >> x >> y;
            update(x, 1, n, root[v], root[i], y);
        }else{
            int x;
            cin >> x;
            cout << query(x, 1, n, root[v], root[i]) << endl;
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}

距离看实际距离的，假边
原题和这题，要求输出的还是不一样的，6

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
double get(pair<double,double> a, pair<double,double> b){
    auto [x, y] = a;
    auto [sx, sy] = b;
    return sqrt((x - sx) * (x - sx) + (y - sy) * (y - sy));
}
const int N = 155;
int f[N];
int find(int x){
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}
void Solve(){
    int n;
    cin >> n;
    vector<pair<double,double>> a(n + 1);
    vector<vector<double>> g(n + 1, vector<double> (n + 1, 1e9));
    rep(i, 1, n) f[i] = i;
    rep(i, 1, n){
        auto &[x, y] = a[i];
        cin >> x >> y;
        g[i][i] = 0;
    }
    rep(i, 1, n){
        string s;
        cin >> s;
        s = ' ' + s;
        rep(j, 1, n){
            if(s[j] == '1'){
                g[i][j] = g[j][i] = get(a[i], a[j]);
                int x = find(i), y = find(j);
                if(y != j) f[x] = y;
                else f[y] = x;
            } 
        }
    }
    vector<double> dist(n + 1);
    rep(k, 1, n)
    rep(i, 1, n)
    rep(j, 1, n)
    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    double res = 1e9;
    rep(i, 1, n)
    rep(j, 1, n)
    if(find(i) == find(j))
    dist[i] = max(dist[i], g[i][j]);
    rep(i, 1, n)
    rep(j, 1, n)
    if(find(i) != find(j))
    res = min(res, dist[i] + dist[j] + get(a[i], a[j]));
    sort(dist.begin(), dist.end());
    cout << SPO(6) << max(res, dist[n]) << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}

给出两种解法，一种是维护最短路和次短路，一种是$dp$解
考虑 $dp[i][j]$ 表示从 $S$ 到 $i$ 多走了 $j$ 个单位的路径数量。
考虑转移 $dp[i][k]$ 从 $dp[j][x]$ 转移过来，有以下等式成立
$$dist[i] + k = dist[j] + x + w(i, j) $$
所以有转移方程:
$$dp[i][k] += dp[j][dist[i] - dist[j] - w + k]$$

关于$dp$的正确性

因为不存在负权、零环、因此将所有“在最短路”中的边建图后一定是个 $DAG$，并且拓扑序满足对于任意边$ (u,v,w) ，dist[u]+w=dist[v]，u$ 一定在 $v$ 之前。

$dp$解:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
void Solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> son(n + 1);
    vector<vector<pair<int,int>>> zson(n + 1);
    rep(i, 1, m){
        int a, b, c;
        cin >> a >> b >> c;
        son[a].push_back({b, c});
        zson[b].push_back({a, c});
    }
    int S, F;
    cin >> S >> F;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    vector<int> dist(n + 1, 1e9);
    dist[S] = 0;
    q.push({0, S});
    while(q.size()){
        auto [o, now] = q.top(); q.pop();
        for(auto [x, w]:son[now]){
            if(dist[x] > o + w){
                dist[x] = o + w;
                q.push({dist[x], x}); 
            }
        }
    }
    vector<vector<int>> dp(n + 1, vector<int> (2));
    // dp[i][j]表示从1到i多走了为j的路径数量
    function<int(int,int)> dfs = [&](int now, int k){
        if(k < 0) return 0;
        if(dp[now][k]) return dp[now][k];
        for(auto [x, w]:zson[now]){
            dp[now][k] += dfs(x, dist[now] - dist[x] - w + k);
        }
        return dp[now][k];
    };
    dp[S][0] = 1;
    cout << dfs(F, 0) + dfs(F, 1) << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t; cin>>t; while(t --)
    Solve();
    return 0;
}

维护最短路和次短路：

/*
 * @Author: JorD
 * @LastEditTime: 2022-12-23 16:53:30
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
struct node{
    int id, kid, dist;
    bool operator <(const node &ji) const{
        return dist > ji.dist; 
    }
};  
void Solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> son(n + 1);
    rep(i, 1, m){
        int a, b, c;
        cin >> a >> b >> c;
        son[a].push_back({b, c});
    }
    int S, F;
    cin >> S >> F;
    vector<vector<int>> dist(2, vector<int> (n + 1, 1e9));
    vector<vector<int>> js(2, vector<int> (n + 1));
    priority_queue<node> q;
    q.push({S, 0, 0});
    dist[0][S] = 0;
    js[0][S] = 1; 
    vector<vector<bool>> st(2, vector<bool> (n + 1));
    while(q.size()){
        auto [now, kid, d] = q.top(); q.pop();
        if(st[kid][now]) continue;
        st[kid][now] = true;
        for(auto [x, w]:son[now]){
            if(dist[0][x] > d + w){
                dist[1][x] = dist[0][x];
                js[1][x] = js[0][x];
                q.push({x, 1, dist[1][x]});
                dist[0][x] = d + w;
                js[0][x] = js[kid][now];
                q.push({x, 0, dist[0][x]});
            }else if(dist[0][x] == d + w){ 
                js[0][x] += js[kid][now];
            }else if(dist[1][x] > d + w){
                dist[1][x] = d + w;
                js[1][x] = js[kid][now];
                q.push({x, 1, dist[1][x]});
            }else if(dist[1][x] == d + w){
                js[1][x] += js[kid][now];
            }
        }
    }
    if(dist[1][F] == dist[0][F] + 1) cout << js[1][F] + js[0][F] << endl;
    else cout << js[0][F] << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t; cin>>t; while(t --)
    Solve();
    return 0;
}

拓扑图上dp

/*
 * @Author: JorD
 * @LastEditTime: 2022-12-23 12:50:58
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define PII pair<ll, ll>
#define siz(s) (ll)(s.size())
#define all(a) a.begin(), a.end()
#define all1(a) a.begin() + 1, a.end()
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int mod = 100003;
void Solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> son(n + 1);
    while(m --){
        int x, y;
        cin >> x >> y;
        son[x].push_back(y);
        son[y].push_back(x);
    }  
    vector<int> js(n + 1), dist(n + 1, 1e9);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    dist[1] = 0;
    js[1] = 1;
    while(q.size()){
        auto [o, now] = q.top(); q.pop();
        for(auto x:son[now]){
            if(dist[x] > o + 1){
                dist[x] = o + 1;
                js[x] += js[now];
                q.push({dist[x], x});
            }else if(dist[x] == o + 1){
                js[x] += js[now];
                js[x] %= mod;
            }
        }
    }
    rep(i, 1, n) cout << js[i] << endl;
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //int t; cin>>t; while(t --)
    Solve();
    return 0;
}