Problem Link

题意

$n$ 个数的序列，保证数两两不同。

定义一个序列是好的，当且仅当存在一个 $i$，使得 $a_1 < a_2 < \cdots < a_i$ 且 $a_i > a_{i + 1} > \cdots > a_n$。

你可以交换相邻两个元素，问至少交换多少次才能使这个序列变成好的。

题解

考虑按照从大到小的顺序加数：每个数只能加到当前序列的最左边或者最右边。

这个有什么性质呢？考虑一个数刚加进去的时候，所有比他大的数都在他右边或左边。而前面加的数的位置是不影响当前数的插入的。

如果一个数 $a_i$ 插在序列最左边，那么所有比他大的数都在他右边。那么如果初始序列中 $i$ 左边比 $a_i$ 大的数的个数为 $k$，则 $a_i$ 需要和他们交换 $k$ 次。

右边同理，我们可以得到放入一个数 $a_i$ 的代价：

$$ p_i = \min(\sum_{j = 1}^{i - 1} [a_j > a_i], \sum_{j = i + 1}^n [a_j > a_i]) $$

最终答案即为：

$$ ans = \sum_{i = 1}^n p_i $$

求 $p$ 的话 BIT 正着、倒着扫两遍即可，记得中间要 clear。

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

代码

Link

QOJ 8052 题解。

联考 T1 考到了这个题，全机房都过了，就我不会呜呜呜。

Task

给长度为 $n$ 的排列 $a$。一次操作可以交换 $a$ 相邻的两个数，问最少多少次操作后 $a$ 满足 $\forall 1 \le i < j \le n, a_i i \le a_j j$。

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

Solution

记 $pos_{a_i} = i$。

考虑如果最终的排列 $a$ 如果满足 $a_i = i$，则一定合法，操作次数为逆序对数。

然而不止有这一种最终排列方式。如果交换两个相邻的数，变成：$1, 2, \cdots, x, x + 2, x + 1, x + 3, \cdots, n$，同样是合法的。

可以发现，最终排列一定可以 $a_i = i$ 的排列通过交换若干个不相交的相邻数得到。

考虑一个 $pos_i > pos_{i + 1}$，说明 $i$ 原本在 $i + 1$ 后面，最后只需交换成 $i + 1, i$ 即可，无需再花费一次操作交换为 $i, i + 1$。

用逆序对数减去 $\sum_{i = 1}^{n - 1}[pos_i > pos_{i + 1}]$ 即可。

复杂度 $O(n \log n)$。

Code

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, pos[N]; ll ans;
struct BIT {
    int tr[N];
    inline int lowbit(int x) { return (x & ( - x)); }
    inline void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i))  tr[i] += k; }
    inline int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))  res += tr[i];
        return res;
    }
    inline int query(int l, int r) { return query(r) - query(l - 1); }
} T;
inline void solve() {
    cin >> n, ans = 0; int x;
    _for (i, 1, n)  cin >> x, pos[x] = i, ans += T.query(x + 1, n), T.update(x, 1);
    _for (i, 1, n - 1)  if (pos[i] > pos[i + 1])  ans -- , i ++ ;
    cout << ans << "\n";
    _for (i, 1, n)  T.update(i, - 1);
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T -- )  solve();
    return 0;
}

Task

有两棵 $n$ 个点的树，称为树 A 和树 B。

有 $q$ 次询问，每次询问给出 $u, v$，求出：

$$ \max_{i = 1}^n \text{disA}_{u, i} + \text{disB}_{v, i} $$

$n \le 10^5, q \le 5 \times 10^5$。

Solution

好题。

维护树上路径最大值，很容易想到直径。但由于两棵树形态不同，这个思路行不行得通呢？

答案是肯定的。首先设树 A 的根为 $rt$。考虑对树 B 的每个点 $i$ 赋一个点权 $a_i = \text{disA}_{i, rt}$。

这样的话我们可以把询问离线，然后强制钦定树 A 的根节点为 $u$。如果询问 $u, v$，问题转化为了求 $\max a_i + \text{disB}_{v, i}$。

有一个经典结论：树上距离一个点最远的点一定是树的直径两端点之一。

有了这个结论，接下来我们就可以利用 Dynamic Diameter 的思想维护当前树的直径及其两端点、两端点的点权，从而求得答案。

那么显然树 A 的根是不断变化的，所以 $a_i$ 是不断变化的。这个可以通过换根，修改的话直接在欧拉序上区间修改即可。

具体时间复杂度取决于求 LCA 的算法：

• 如果使用预处理 $O(n)$，单次查询 $O(\log n)$ 的倍增 / 树剖，时间复杂度 $O(n \log n + q \log^2 n)$，可能会被卡常；

• 如果使用预处理 $O(n \log n)$，单次查询 $O(1)$ 的 ST 表，时间复杂度 $O((n + q) \log n)$，轻松通过（建议采用此写法）。

Code

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define P pair<int, int>
#define ll long long
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, q; ll x, ans[M]; vector<P > qry[N];
namespace IO {
    static char buf[1000000], * p1 = buf, * p2 = buf, obuf[1000000], * p3 = obuf, cc[20];
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N - 5, stdin), p1 == p2) ? EOF : * p1 ++ )
    #define pc(x) (p3 - obuf < 1000000) ? ( * p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, * p3 ++ = x)
    inline int rd() {
        int val = 0, sgn = 1; char ch = gc();
        while (! isdigit(ch)) { if (ch == '-')  sgn = -1; ch = gc(); }
        while (isdigit(ch))  val = (val << 3) + (val << 1) + (ch ^ 48), ch = gc();
        return (val * sgn);
    }
    template <typename item>
    inline void print(item x){ 
        if (! x)  pc('0');
        int len = 0;
        if (x < 0)  x = - x, pc('-');
        while (x)  cc[len ++ ] = x % 10 | '0', x /= 10;
        while (len -- )  pc(cc[len]);
    }
    inline void write(long long x, char c) { print(x), pc(c); }
} using namespace IO;
struct Tree {
    int dfn_cnt, timer, sz[N], son[N], fa[N], dep[N], top[N], rk[N], dfn[N], pos[N], Log[N << 1], a[N << 1], ST[N << 1][20]; ll dis[N]; vector<P > G[N];
    inline void clear() {
        dfn_cnt = timer = 0;
        _for (i, 1, n)  dfn[i] = dis[i] = dep[i] = 0, G[i].clear();
    }
    void dfs1(int u) {
        sz[u] = 1, son[u] = - 1, a[pos[u] =  ++ timer] = u;
        for (P v : G[u])  if (v.F ^ fa[u]) {
            dep[v.F] = dep[u] + 1, dis[v.F] = dis[u] + v.S, fa[v.F] = u, dfs1(v.F), sz[u] += sz[v.F], a[ ++ timer] = u;
            if (son[u] == - 1 || sz[son[u]] < sz[v.F])  son[u] = v.F;
        }
    }
    void dfs2(int u, int Top) {
        top[u] = Top, rk[dfn[u] = ++ dfn_cnt] = u;
        if (son[u] == - 1)  return ;
        dfs2(son[u], Top);
        for (P v : G[u])  if (v.F ^ fa[u] && v.F ^ son[u])  dfs2(v.F, v.F);
    }
    inline int lca(int u, int v) {
        int U = top[u], V = top[v];
        while (U ^ V) {
            if (dep[U] >= dep[V])  u = fa[U];
            else  v = fa[V];
            U = top[u], V = top[v];
        }
        return (dep[u] < dep[v] ? u : v);
    }
    inline void pre_work() {
        Log[0] = - 1;
        _for (i, 1, n << 1)  Log[i] = Log[i >> 1] + 1;
        _for (i, 1, n << 1)  ST[i][0] = a[i];
        _for (j, 1, Log[n << 1])  _for (i, 1, (n << 1) - (1 << j) + 1)  ST[i][j] = dep[ST[i][j - 1]] < dep[ST[i + (1 << (j - 1))][j - 1]] ? ST[i][j - 1] : ST[i + (1 << (j - 1))][j - 1];
    }
    inline int query(int u, int v) {
        int l = pos[u], r = pos[v];
        if (l > r)  l ^= r ^= l ^= r;
        int k = Log[r - l + 1];
        return dep[ST[l][k]] < dep[ST[r - (1 << k) + 1][k]] ? ST[l][k] : ST[r - (1 << k) + 1][k];
    }
    inline ll dist(int u, int v) { return dis[u] + dis[v] - 2ll * dis[query(u, v)]; }
} T[2];
struct Seg_Tree {
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    #define mid ((tr[p].l + tr[p].r) >> 1)
    struct Tree { int l, r, A, B; ll tag, dis, val_A, val_B; } res, tr[N << 2];
    inline int len(int p) { return tr[p].r - tr[p].l + 1; }
    inline bool In(int p, int l, int r) { return l <= tr[p].l && tr[p].r <= r; }
    inline void push_tag(int p, ll k) { tr[p].tag += k, tr[p].val_A += k, tr[p].val_B += k; }
    inline Tree merge(Tree u, Tree v) {
        res.l = u.l, res.r = v.r, res.dis = 0;
        if ((x = T[1].dist(u.A, u.B) + u.val_A + u.val_B) > res.dis)  res.dis = x, res.A = u.A, res.B = u.B, res.val_A = u.val_A, res.val_B = u.val_B;
        if ((x = T[1].dist(u.A, v.B) + u.val_A + v.val_B) > res.dis)  res.dis = x, res.A = u.A, res.B = v.B, res.val_A = u.val_A, res.val_B = v.val_B;
        if ((x = T[1].dist(v.A, u.B) + v.val_A + u.val_B) > res.dis)  res.dis = x, res.A = v.A, res.B = u.B, res.val_A = v.val_A, res.val_B = u.val_B;
        if ((x = T[1].dist(v.A, v.B) + v.val_A + v.val_B) > res.dis)  res.dis = x, res.A = v.A, res.B = v.B, res.val_A = v.val_A, res.val_B = v.val_B;
        if ((x = T[1].dist(u.A, v.A) + u.val_A + v.val_A) > res.dis)  res.dis = x, res.A = u.A, res.B = v.A, res.val_A = u.val_A, res.val_B = v.val_A;
        if ((x = T[1].dist(u.B, v.B) + u.val_B + v.val_B) > res.dis)  res.dis = x, res.A = u.B, res.B = v.B, res.val_A = u.val_B, res.val_B = v.val_B;
        return res;
    }
    inline void push_down(int p) { if (tr[p].tag)  push_tag(lc, tr[p].tag), push_tag(rc, tr[p].tag), tr[p].tag = 0; }
    void build(int p, int l, int r) {
        tr[p].l = l, tr[p].r = r, tr[p].tag = 0;
        if (l == r) { tr[p].A = tr[p].B = T[0].rk[l], tr[p].dis = 0, tr[p].val_A = tr[p].val_B = T[0].dis[T[0].rk[l]]; return ; }
        build(lc, l, mid), build(rc, mid + 1, r), tr[p] = merge(tr[lc], tr[rc]);
    }
    void update(int p, int l, int r, ll k) {
        if (In(p, l, r)) { push_tag(p, k); return ; }
        push_down(p);
        if (l <= mid)  update(lc, l, r, k);
        if (r > mid)  update(rc, l, r, k);
        tr[p] = merge(tr[lc], tr[rc]);
    }
    Tree query(int p, int l, int r) {
        if (In(p, l, r))  return tr[p];
        push_down(p);
        if (r <= mid)  return query(lc, l, r);
        if (l > mid)  return query(rc, l, r);
        return merge(query(lc, l, r), query(rc, l, r));
    }
    #undef lc
    #undef rc
    #undef mid
} SGT;
void dfs3(int u) {
    Seg_Tree :: Tree tr = SGT.query(1, 1, n); int A = tr.A, B = tr.B; ll x, y, val_A = tr.val_A, val_B = tr.val_B;
    for (P v : qry[u])  x = T[1].dist(v.F, A), y = T[1].dist(v.F, B), ans[v.S] = max(x + val_A, y + val_B);
    for (P v : T[0].G[u])  if (v.F ^ T[0].fa[u])  SGT.update(1, 1, n, v.S), SGT.update(1, T[0].dfn[v.F], T[0].dfn[v.F] + T[0].sz[v.F] - 1, - 2ll * v.S), dfs3(v.F), SGT.update(1, 1, n, - v.S), SGT.update(1, T[0].dfn[v.F], T[0].dfn[v.F] + T[0].sz[v.F] - 1, 2ll * v.S);
}
inline void solve() {
    n = rd(), q = rd(), T[0].clear(), T[1].clear(); int u, v, w;
    _for (i, 1, n)  qry[i].clear();
    _for (o, 0, 1)  _for (i, 2, n)  u = rd(), v = rd(), w = rd(), T[o].G[u].pb(mp(v, w)), T[o].G[v].pb(mp(u, w));
    _for (o, 0, 1)  T[o].dfs1(1), T[o].dfs2(1, 1), T[o].pre_work();
    SGT.build(1, 1, n);
    _for (i, 1, q)  u = rd(), v = rd(), qry[u].push_back(mp(v, i));
    _for (i, 1, n)  sort(qry[i].begin(), qry[i].end());
    dfs3(1);
    _for (i, 1, q)  write(ans[i], '\n');
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    fwrite(obuf, p3 - obuf, 1, stdout);
    return 0;
}

Task

$n$ 个人 $n + 1$ 件物品，每个人 $i$ 对一件物品 $j$ 有一个喜欢程度 $a_{i, j}$。

一轮游戏从 $i$ 开始，按 $i, i + 1, \cdots, n, 1, 2, \cdots, i - 1$ 的顺序每人选走一个物品，每个人都希望他对最后剩下的物品的喜欢程度最大，答案为最后剩下的物品是哪个。对于每个 $i \in [1, n]$ 都求出答案。

对于每个 $i$，$a_{i, 1} \sim a_{i, n + 1}$ 为 $1 \sim n + 1$ 的排列。

$n \le 5000$。

Solution

发现正着想没什么思路，倒过来思考。

为了方便，记 $f_{i, j}$ 表示第 $i$ 个人喜欢程度为 $j$ 的物品编号，即 $f_{i, a_{i, j}} = j$。

假设从第 $i$ 个人开始选物品。

首先考虑最后一个人 $i - 1$。由于轮到他的时候只剩两个物品可选，那么他一定会毙掉他更讨厌的那个物品 $x_{i - 1}$。

再考虑倒数第二个人 $i - 2$。考虑分类讨论如下：

• 如果剩下的三个物品中 $i - 2$ 号人最讨厌的不为 $x_{i - 1}$，那么他会毙掉他最讨厌的物品 $x_{i - 2}$。

• 否则，他和最后一个人最讨厌的物品是同一个物品，那么他会选择不毙掉 $x_{i - 1}$，留给最后一个人去将它选走，自己选择倒数第二讨厌的物品。这样的话他就可以保证最后剩下的物品（在还剩下的 $3$ 个物品中）是他最喜欢的。

想到这里，我们可以发现，最后一个人 $i - 1$ 选走的物品一定是他初始最讨厌的物品 $f_{i - 1, 1}$，因为前面的人即使最讨厌的物品也是它也会把该物品留给 $i - 1$ 来选。同理，若 $f_{i - 2, 1} \neq f_{i - 1, 1}$，$i - 2$ 选走的是 $f_{i - 2, 1}$，否则为 $f_{i - 2, 2}$。

于是我们便得出了暴力思路：倒着决策，当前人选走还未被选过的他最讨厌的物品。

暴力是 $O(n^3)$ 的，理论上无法通过，但跑得飞快过了。暴力 Code。

接下来考虑优化。

我们以第 $n$ 个人为例：考虑第一轮从 $1$ 开始操作，第二轮从 $2$ 开始操作，由于我们是倒着决策，那么 $n$ 的决策优先权不断降低。也就是说，假设第一轮 $n$ 最终选了 $f_{n, k_1}$ 这件物品，那么第二轮时 $n$ 选走的物品 $f_{n, k_2}$ 一定满足 $k_1 \le k_2$。

所以我们考虑开一个 $lst_i$ 记录第 $i$ 个人上一轮选择的物品为 $f_{i, lst_i}$，那么当前轮时枚举 $i$ 的决策直接从 $lst_i$ 开始枚举即可。当然，如果 $i$ 是当前轮第一个决策的人，那么强制让他从 $f_{i, 1}$ 开始选。

这样的话每个 $f_{i, j}$ 最多只会被遍历一次，复杂度被降到了 $O(n^2)$，可以通过。正解 Code。