更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638717

大意

给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。

给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。

思路

我们考虑一个小巧思。

我们将问题可以转化为将 $a \to b$ 这条路径的点染上独一无二的颜色，最终求 $a \to b$ 路径上的重边即为两端颜色相同的边的数量。

因为每次我们选的颜色都不一样，这样操作一定能够让我们通过只记录端点的颜色去统计这个值，我们通过直接维护区间的左右的端点的颜色和相邻重色的个数，我们如果区间的端点颜色重合就可以将这个答案继续累加。这个就是处理本题线段树的方式。

但是对于这个题目是在树上的操作，那就没什么说的了，直接树剖维护即可。但是如果你像我一样闲着没事的话可以用 LCT 维护，原因是这个更改 $a \to b$ 路径的过程可以用 LCT 的 split 操作非常简便的完成。至于 LCT 里面维护的内容，和线段树几乎一样，剩下就没什么了。

代码

#include<iostream>
#include<algorithm>
using namespace std;

#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;

struct node{
    int ch[2], fa;
    int col, tag;
    int lc, rc;
    int cnt; 
    int sz;
    bool rev;
    node(){
        ch[1] = ch[0] = fa = 0;
        col = tag = lc = rc = cnt = sz = 0;
        rev = false;
    }
}t[MAXN];

bool isroot(int x){
    return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}

void pushup(int x) {
    t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
    t[x].cnt = t[lc(x)].cnt + t[rc(x)].cnt;
    
    t[x].lc = lc(x) ? t[lc(x)].lc : t[x].col;
    t[x].rc = rc(x) ? t[rc(x)].rc : t[x].col;
    
    if(lc(x) && t[lc(x)].rc == t[x].col) t[x].cnt ++;
    if(rc(x) && t[rc(x)].lc == t[x].col) t[x].cnt ++;
}

void update_rev(int x){
    if(!x) return;
    swap(lc(x), rc(x));
    swap(t[x].lc, t[x].rc);
    t[x].rev ^= 1;
}

void apply_col(int x, int c){
    if(!x) return;
    t[x].col = t[x].lc = t[x].rc = t[x].tag = c;
    t[x].cnt = t[x].sz - 1;
}

void pushdown(int x){
    if(t[x].rev){
        update_rev(lc(x));
        update_rev(rc(x));
        t[x].rev = 0;
    }
    if(t[x].tag){
        apply_col(lc(x), t[x].tag);
        apply_col(rc(x), t[x].tag);
        t[x].tag = 0;
    }
}

void rotate(int x){
    int y = fa(x), z = fa(y);
    int k = (rc(y) == x);
    if(!isroot(y)) t[z].ch[rc(z) == y] = x;
    fa(x) = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    if (t[x].ch[k ^ 1]) fa(t[x].ch[k ^ 1]) = y;
    t[x].ch[k ^ 1] = y;
    fa(y) = x;
    pushup(y);
    pushup(x);
}

void pushshell(int x){
    if(!isroot(x)) pushshell(fa(x));
    pushdown(x);
}

void splay(int x){
    pushshell(x);
    while(!isroot(x)){
        int y = fa(x), z = fa(y);
        if(!isroot(y)) (rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x){
    for(int y = 0;x;y = x, x = fa(x)){
        splay(x);
        rc(x) = y;
        pushup(x);
    }
}

void makeroot(int x){
    access(x);
    splay(x);
    update_rev(x);
}

void split(int x, int y){
    makeroot(x);
    access(y);
    splay(y);
}

void modify(int u, int v, int c){
    split(u, v);
    apply_col(v, c);
}

void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        t[i] = node();
        t[i].col = t[i].lc = t[i].rc = -i;
        t[i].sz = 1;
    }
    for(int i = 1;i < n;i ++){
        int u, v; cin >> u >> v;
        makeroot(u); fa(u) = v;
    }
    int cur_col = 0;
    while(m --){
        int op, u, v;
        cin >> op >> u >> v;
        if(op == 1){
            modify(u, v, ++ cur_col);
            split(u, v);
            apply_col(v, ++ cur_col);
        }
		else{
            split(u, v);
            cout << t[v].cnt << "\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638674

大意

三种牌分别有 $n , m, k$ 张，要求排列后满足相同的类型的牌不相邻的方案数。

$\newcommand{\binom}[2]{{#1 \choose #2}}$

思路

这集很考察基本功，组合好题。

考虑插板法，我们首先先把这个东西转换成上面的大意之后，我们先考虑把前两个人的位置考虑好，再考虑第三个人放的位置。

先安排核桃和小 $B$ 的位置，我们先枚举 $i$ 块 H，方案数是 $\binom{n - 1}{i - 1}$，现在我们要把 $m$ 个 B 也分成若干块，插入到这 $i$ 块 H 的空隙里。

为了使得 H 块之间分开，B 块的个数 $j$ 只有三种情况：

- $j = i - 1$

- $j = i$

- $j = i + 1$

其分别对应的情况为：B 块全在 H 块中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 2}$，B 和 H 一头一尾（两种情况），方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 1} \times  2$，H 全在 B 中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i}$。然而此时的问题是，虽然 B 和 H 交错排列了，但是仍有一部分不合法的块内相邻的点，接下来我们需要做的就是将 R 插入到这个序列里面。

如果每一个 H 块内有 $x$ 个相邻的，那么就需要 $x - 1$ 个板来进行隔开，同样的对于 B 块内的也一样。所以说至少需要拿出来使得不合法变为合法的 R 需要 $(n - i) + (m - j)$ 个 R 来进行~~紧急避险~~，那么我们还能剩的 $k' = (k - n - m + i + j)$，那么我们剩下的这些 $k'$ 应该放到哪些地方呢？首先是 H 和 B 的中间是可以的，然后就是序列的开头和结尾是一定可以的，那么我们的剩余槽位是 $r = i + j$，若是 H 和 B 交错排列的话就是 $r = i + j + 1$，所以接下来的问题是把这剩下的 $k'$ 放到 $r$ 个剩余的槽位中（每个槽可以放 $0$ 个或多个），这个时候使用隔板法 $\binom{k' + r - 1}{r - 1}$，我们将其展开之后就是 $\binom{k - n - m + 2i + 2j}{i + j}$。

所以来说，对应的三种情况的总方案数就可以写出来了：

- $i = j - 1：\binom{k - n - m + 4i - 2}{2i - 1}$

- $i = j：\binom{k - n - m + 4i}{2i}$

- $i = j + 1：\binom{k - n - m + 4i + 2}{2i + 1}$

然后就没有了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 998244353;
const ll N = 2e6 + 100;

ll n, m, k;
ll fac[N + 100], inv[N + 100];
ll ans;

ll mpow(ll aa,ll bb){
	ll res = 1;
	while(bb){
		if (bb&1) res = res * aa % mod;
		aa = aa * aa % mod;
		bb >>= 1;
	}
	return res;
}

ll C(ll aa,ll bb){
	if(aa < 0 || bb < 0 || aa > bb) return 0;
	return fac[bb] * inv[aa] % mod * inv[bb - aa] % mod;
}

int main(){
	freopen("UNO.in","r",stdin);
	freopen("UNO.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	fac[0] = 1;
	for(int i = 1;i <= N;i ++) fac[i] = (fac[i - 1] * i) % mod;
	for(int i = 0;i <= N;i ++) inv[i] = mpow(fac[i], mod - 2);
	for(int i = 1;i <= n;i ++){
		ans += C(i - 1, n - 1) * C(i - 2, m - 1) % mod * C(k - n - m + 2 * i - 1, 2 * i) % mod;
		ans += C(i - 1, n - 1) * C(i - 1, m - 1) % mod * C(k - n - m + 2 * i, 2 * i + 1) % mod * 2 % mod;
		ans += C(i - 1, n - 1) * C(i, m-1) % mod * C(k - n - m + 2 * i + 1, 2 * i + 2) % mod;
	}
	cout << (ans + mod) % mod<<'\n';
	return 0;
}  

突然发现自己暑假写过这题。

显然可以考虑动态规划，但不难发现用时间做状态没前途，用站点做状态转移比较困难，而用车次做转移刚刚好。

设 $f_i$ 表示坐上列车 $i$ 的最小烦躁值，因为并没有保证 $x_i<y_i$，所以转移的顺序要按照 $p$ 来排，每次要转移的来源必须满足 $y_j=x_i,q_j\le p_i$。不难完成 $O(n^2)$ 的代码。

考虑优化，注意到转移很像斜率优化，所以使用李超线段树，每次计算完 $f_i$ 后，将 $(q_i,i)$ 放入二叉堆按 $q_i$ 排序。每次转移前，取出二叉堆中所有满足 $q_j\le p_i$ 的 $j$，然后将直线 $j$ 插入第 $y_j$ 个位置的李超树。

李超树动态开点空间复杂度 $O(n)$，时间复杂度 $O(n\log V)$。

更好的阅读体验https://www.cnblogs.com/To-Carpe-Diem/p/19635184

大意

给出 $b_{i, j} = a_{i - 1, j} + a_{i, j - 1} + a_{i - 1, j - 1} + a_{i, j}$，要求给出一组 $a$ 的可行解，保证 $0 \le a_{i, j} \le 10 ^ 6$。

思路

这集真的神了。

我们想一个问题，首先这个题我们很容易构造出一个 $a$，使其满足 $b$ 的性质，我们将 $a_{i, 1}$ 和 $a_{1, i}$ 都设为 $0$，那么我们有这样的转移式子：$a_{i, j} = b_{i - 1, j - 1} - a_{i - 1, j} - a_{i, j - 1} - a_{i - 1, j - 1}$，这样构造出来的 $a$ 是含有负数的，但是我们考虑进行调整。

这里有一个小巧思，我们考虑对于每一行和每一列进行增量的操作，加减交替，这样会得到以下这个样子的矩阵：

$\begin{pmatrix}r_1 + c_1 & -r_1 + c_2 & r_1 + c_3 & \cdots \\r_2 - c_1 & -r_2 - c_2 & r_2 - c_3 & \cdots \\r_3 + c_1 & -r_3 + c_2 & r_3 + c_3 & \cdots \\\vdots & \vdots & \vdots & \ddots\end{pmatrix}$

有什么用呢？？？我们发现 $(r_1 + c_1) + (-r_1 + c_2) + (r_2 - c_1) + (-r_2 - c_2) = 0$，那么这样我们就在不改变 $b$ 的情况下可以对 $a$ 进行调整，那么会变成类似于这样的差分约束系统：$0 \le a_{i, j} \pm r_i \pm c_i \le 10 ^ 6$，我们就直接对这样的建立差分约束系统，然后跑 SPFA 即可（注意判负环，如果有负环说明就没有答案）

代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int MAXN = 1005;
const int INF = 1000000;
int T;
int n, m;
int b[MAXN][MAXN];
int a[MAXN][MAXN];
vector<pair<int, int> > g[MAXN];
bool vis[MAXN << 1];
int dis[MAXN << 1], in[MAXN << 1];
queue<int> q;

void init(){
    while(!q.empty()) q.pop();
    for(int i = 1;i <= n + m;i ++){
        dis[i] = 0;
        vis[i] = 1;
        in[i] = 0;
        q.push(i);
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1;i < n;i ++){
        for(int j = 1;j < m;j ++){
            cin >> b[i][j];
        }
    }
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            a[i][j] = 0;
    for(int i = 2;i <= n;i ++){
        for(int j = 2;j <= m;j ++){
            a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1];
//            cout << a[i][j] << ' ';
        }
//        cout << endl;
    }
    for(int i = 1;i <= n + m + 1;i ++) g[i].clear();
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if((i + j) & 1){
                g[i].push_back(make_pair(j + n, a[i][j]));
                g[j + n].push_back(make_pair(i, INF - a[i][j]));
            }
            else{
                g[j + n].push_back(make_pair(i, a[i][j]));
                g[i].push_back(make_pair(j + n, INF - a[i][j]));
            }
        }
    }
    init();
    while(!q.empty()){
        int u = q.front(); q.pop(); vis[u] = 0;
        for(auto x : g[u]){
            int v = x.first, w = x.second;
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                	in[v] ++;
                	if(in[v] > n + m + 1){
						cout << "NO\n";
						return;
					}
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    bool flag = 1;
//    cout << "YES\n";
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if((i + j) & 1) a[i][j] += (dis[i] - dis[j + n]);
            else a[i][j] += (dis[j + n] - dis[i]);
            if(a[i][j] < 0) flag = 0;
//            cout << a[i][j] << ' ';
        }
//        cout << '\n';
    }
    if(flag){
        cout << "YES\n";
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
    }
    else cout << "NO\n";
}

int main(){
    // freopen("matrix.in", "r", stdin);
    // freopen("matrix.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19635135

大意

求前 $k$ 大的互不相同的异或和。

思路

首先，我们将其转换一下，求出前缀异或和，$s$，$s_i = s_i \oplus s_{i - 1} $，这样，对于区间 $[l, r]$ 的异或和询问就变成了 $s_r \oplus s_{l - 1}$。

知道了这个之后，我们的问题现在转化为了，在这 $n$ 个 $s$ 里面选择 $k$ 对，使得其和最大，这个时候，我们要处理的问题是对于 $s_i$ 来说，如何找到一个 $s_j$，使得其 $s_i \oplus s_j$ 的值最大。这个问题十分经典（但是我也刚知道），可以用 Trie 来处理这种动态找最大异或和的问题。

那么如何在 Trie 上维护这个东西呢？我们考虑将每个 $s_i$ 插入 Trie 里面，那么记录每个节点经过的点的个数，我们一定是希望走 $op \oplus 1$ 的位置的，但是如果没有 $op \oplus 1$ 这个位置，就走不了，且，若是左子树的大小不够，也走不了，必须走到 $sz \ge rk$ 的地方，这个才是对的。于是就类似权值线段树静态查第 $k$ 大差不多，不过此题我们要处理的是前 $2k$ 大，因为我们忽略了 $l \le r$ 的限制。

我们只需要用一个大根堆记录即可，但是每个答案都会以 $s_i$ 和 $s_j$ 为基准分别各出现一次，那么最终我们选择的答案需要除以 $2$。

代码

#include<iostream>
#include<queue>
using namespace std;

#define ll long long
const int MAXN = 5e5 + 5;
const int MAXT = MAXN * 32;

int ch[MAXT][2], cnt[MAXT];
ll s[MAXN], tot = 0, n, k;

struct node{
    int id, rk;
    ll val;
    bool operator<(const node &other)const{
        return val < other.val;
    }
};

void Insert(ll x){
    int now = 0;
    for(int i = 31;i >= 0;i --){
        int op = (x >> i) & 1;
        if(!ch[now][op]) ch[now][op] = ++ tot;
        now = ch[now][op];
        cnt[now] ++;
    }
}

ll query(ll x, int rk){
    int now = 0;
    ll res = 0;
    for(int i = 31;i >= 0;i --){
        int op = (x >> i) & 1;
        op ^= 1;
        if(!ch[now][op]){
            now = ch[now][op ^ 1];
        }
        else if(rk <= cnt[ch[now][op]]){
            res |= (1LL << i);
            now = ch[now][op];
        }
        else{
            rk -= cnt[ch[now][op]];
            now = ch[now][op ^ 1];
        }
    }
    return res;
}

int main(){
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> k;
    s[0] = 0;
    Insert(s[0]);
    for(int i = 1;i <= n;i ++){
        ll a; cin >> a;
        s[i] = s[i - 1] ^ a;
        Insert(s[i]);
    }
    
    priority_queue<node> q;
    for(int i = 0;i <= n;i ++){
        ll x = query(s[i], 1);
        q.push({i, 1, x});
    }
    ll ans = 0;
    for(int i = 1;i <= 2 * k;i ++){
        node t = q.top();
        ans += t.val;
        q.pop();
        if(t.rk < n){
            q.push({t.id, t.rk + 1, query(s[t.id], t.rk + 1)});
        }
    }
    cout << ans / 2;
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19635009

大意

给出 $n$ 张卡牌，每张卡牌都有两个权值 $a_i$ 和 $b_i$，分别对应的是正面和反面，求在至少翻 $m$ 张牌，然后求出最小的极差。

思路

我们考虑这样的事，首先，我们不考虑每一张牌的情况，我们只考虑这个先处理极差的问题，我们先把这 $2n$ 张牌记录一下类型，然后将其排序。

排完序之后，我们需要的是选择一段区间 $[L, R]$，使得 $[L, R]$ 的区间包含所有的类型，且其中间反转的牌不超过 $m$ 个，那么这个区间的 $val_R - val_L$ 就是一个合法的答案，我们要想使得这个值尽可能的小，我们不妨使用双指针的写法，固定左端点，向右查询合法右端点。

这个过程是具有单调性的，你的 $L$ 向右，$R$ 也必定向右，具体过程是这样的，如果当前的区间不合法，那么就让 $R$ 右移，使其包含所有的 $n$ 个情况，一旦包含足够，就判断是否合法，这个过程是可以在扫描的过程中动态处理的，这步判断是 $\mathcal{O}(1)$ 的，如果是合法就将 $L$ 向右收缩，这样去看看有没有更优的 $val_R - val_L$。

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1e6 + 5;
int n, m, l, r, cnt = 0;
struct node{
    long long val, id;
    bool op;
}k[MAXN << 1];
int t[MAXN << 1];
bool cmp(node x, node y){
    return x.val < y.val;
}

int main(){
    // freopen("card.in", "r", stdin);
    // freopen("card.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        cin >> k[i].val;
        k[i].id = i;
        k[i].op = 1;
    }
    for(int i = 1;i <= n;i ++){
        cin >> k[i + n].val;
        k[i + n].id = i;
        k[i + n].op = 0;
    }
    sort(k + 1, k + 2 * n + 1, cmp);
//    for(int i = 1;i <= n * 2;i ++){
//        cout << k[i].val << ' ' << k[i].id << ' ' << k[i].op << '\n';
//    }
    for(l = 0;cnt + k[l + 1].op <= m && !t[k[l + 1].id];l ++){
        cnt += k[l + 1].op;
        t[k[l + 1].id] = 1;
    }
    for(r = 2 * n + 1;cnt + k[r - 1].op <= m && !t[k[r - 1].id];r --){
        cnt += k[r - 1].op;
        t[k[r - 1].id] = 1; 
    }
    long long ans = 1e9 + 7;
	while(l >= 0) {
		ans = min(k[r - 1].val - k[l + 1].val, ans);
		t[k[l].id] = 0;
		cnt -= k[l].op;
		l --;
        for(r;cnt + k[r - 1].op <= m && !t[k[r - 1].id];r --){
            cnt += k[r - 1].op;
            t[k[r - 1].id] = 1; 
        }
	}
	cout << ans << '\n';
}