Desc.

Link.

有 $h$ 条水平道路和 $w$ 条竖直道路, 在其上行走一个单位分别花费 $a_i$ 和 $b_j$, 问从 $(1, 1)$ 到 $(h, w)$ 的最小花费.

Sol.

把步数拆到恰好拐一个弯的形状, 设从 $(i, j)$ 走到 $(i', j')$. 有两种方式, 其中一种是 $(i, j) \rightarrow (i', j) \rightarrow (i', j')$. 整理得到一个斜率形式. 合并两者凸包. (赶着回家, 写得比较草率...)

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vll a(n), b(m); rds(a), rds(b);
#define fi first
#define se second
    using pii = pair<ll, ll>;
    const auto cross = [&](const pii& a, const pii& b) {
        return a.fi*b.se-a.se*b.fi;
    };
    static int s1[100100], s2[100100], top1, top2;
    for (int i=0;i<n;++i) {
        while (top1 > 1 && cross({s1[top1]-s1[top1-1], a[s1[top1]]-a[s1[top1-1]]}, {i-s1[top1], a[i]-a[s1[top1]]}) < 0)
            top1--;
        s1[++top1] = i;
    }
    for (int i=0;i<m;++i) {
        while (top2 > 1 && cross({s2[top2]-s2[top2-1], b[s2[top2]]-b[s2[top2-1]]}, {i-s2[top2], b[i]-b[s2[top2]]}) < 0)
            top2--;
        s2[++top2] = i;
    }
    int i = 1, j = 1;
    ll ans = 0;
    while (i < top1 || j < top2) {
        if (i < top1 && (j == top2 || cross({s2[j+1]-s2[j], b[s2[j+1]]-b[s2[j]]}, {s1[i+1]-s1[i], a[s1[i+1]]-a[s1[i]]}) < 0)) {
            ans += (s1[i+1]-s1[i])*b[s2[j]];
            i++;
        } else {
            ans += (s2[j+1]-s2[j])*a[s1[i]];
            j++;
        }
    }
    cout << ans << "\n";
}

  link．

  单次询问的做法是平凡的，令 $f_i(k)$ 表示将前 $i$ 个元素划分出了 $k$ 段的最大值，有转移：

$$f_i(k) = \max\{f_{i-1}(k), \max_{0 \leqslant j < i} \{f_j(k-1)+s_i-s_j\}\}$$

  其中 $s$ 是前缀和．研究函数 $g(k) = f_n(k)$，可以发现所有的 $(k, g(k))$ 构成了一个凸包，证明考虑构造一个费用流模型：

将所有元素 $a_i$ 分拆成 $u_i$ 与 $v_i$ 两个点，令四元组 $\lang u, v, c, w\rang$ 为费用流网络上的一条边．有：

$$V_N = [1, n] \cup \{s, t\} \\ E_N = \{(u_i, v_i) \mid i \in [1, n]\} \cup \{(v_i, u_{i+1}) \mid i\in [1, n)\} \cup\{(s, u_i) \mid i \in [1, n]\} \cup \{ (v_i, t) \mid i \in [1, n] \} \\ \begin{cases} c(u_i, v_i) = 1, w(u_i, v_i) = a_i, i \in [1, n] \\ c(v_i, u_{i+1}) = 1, w(v_i, u_{i+1}) = 0, i \in [1, n) \\ c(s, u_i) = c(v_i, t) = 1, w(s, u_i) = w(v_i, t) = 0, i \in [1, n] \end{cases}$$

由于最大费用流每次增广的费用是递减的，因此 $g(k)$ 的斜率递减．

  再考虑多次询问，我们使用线段树来维护分治的过程．具体而言，线段树上的每一个结点维护的是 $g_{[l, r]}(k)$ 表示只考虑原序列的 $[l, r]$ 这一部分的 $g(k)$．但是你注意到一个事情，$[l, m]$ 和 $(m, r]$ 这两个区间要是合并成了 $[l, r]$ 这个区间，我们需要考虑跨过中点的情况．所以线段树上的每个结点一共要维护四个凸包，分别是 $g_{[l, r]}(k, 0/1, 0/1)$，表示考虑区间 $[l, r]$ 上左右端点分别有没有被划分入某一段里面的情况．

  现在我们来考虑怎么合并线段树上某个结点的两个子结点里面的四乘二等于八个凸包．注意到只有左儿子取了右端点，且右儿子取了左端点的情况合并比较特殊，其他的 15 种情况都是同理的．因为这时，左右儿子合并出来的凸包会少一段（左儿子的右端点和右儿子的左端点合并成了一段）．我们写出比较普适的另外 15 种情况（以下方程没有写出限制条件）的转移：

$$g_{[l, r]}(i+j, 0/1, 0/1) = \max\{g_{[l, m]}(i, 0/1, 0/1)+g_{(m, r]}(j, 0/1,0/1)\}$$

  特殊情况：

$$g_{[l, r]}(i+j-1, 0/1, 0/1) = \max\{g_{[l, m]}(i, 0/1, 0/1)+g_{(m, r]}(j, 0/1,0/1)\}$$

  这个转移怎么维护呢？看起来好像要 $O((r-l+1)^2)$ 的样子．但是如果你仔细看就会发现这是个向量加法的形式，即 $(i+j, g_3(i+j)) = (i, g_1(i))+(j, g_2(j))$，使用凸包的 Minkowski Sums 即可线性把加法做出来，再线性取一遍 max 即可．

  到这里我觉得这个题已经足够傻逼了，但这混账 300iq 比我想象中更傻逼．

  我们继续看怎么回答询问．考虑暴力，即把询问区间 $[L, R]$ 在线段树上拆出来的 $O(\log_2(R-L+1))$ 个子区间合并起来，直接取合并出来的凸壳的 $g(k)$ 就是答案．这样合并单次询问的复杂度必然与询问区间长度相关．

  再考虑不直接合并这些凸包，采用 wqs 二分去掉各个凸包选择的段数之和必须为 $k$ 这一限制，那么每个凸包可以各自独立的贪心选择最优解（其实就是各凸包与二分给出的斜率直线切点）再加和得到答案．需要注意的是每个结点四个凸包都要考虑．$O(q \log_2^3 n)$．

  考虑进一步的优化，就是平行 wqs 二分了．因为二分给出的斜率是单调的，因此各个凸包的切点变化也是单调的，使用一个指针维护而不是二分地去找可以剩一个 log．$O(q\log_2^2 n)$．

  我不知道怎样的冤种会去写这种答辩．

  link．

  我发现 Hydro OJ 意外地好用，比 darkbzoj 高明．

  考虑点积的几何意义：投影．可以发现答案就是用一根与询问向量正交的直线从沿询问向量方向无限远处向原点迫近，碰到的第一个向量就是答案．然后你会发现，如果把正交直线的方程写出来，然后解一下与集合内向量相碰撞的方程，就会得到一个结论，即询问的答案是 $\max {y \times (\frac{x}{y} \times x_i + y_i)}$，当然这个用点积的代数式可以直接得到，于是把每个向量看作一个一次函数，我们就可以自然地想到李超树来维护这个最值．
但是

  但是李超树很难支持撤销，我们考虑把撤销转化掉．一般这样的题目都有类似 “降维” 的思想，而这种操作一般通过数据结构实现．我们对操作的时间轴建一棵标记永久化的线段树，叶子结点存对应操作的信息，非叶子结点没有需要维护的信息，只需要记录懒标即可．而这个懒标在这个题里面就是一棵李超树，这个东西叫线段树分治．

  线段树分治又何尝不是一种树套树

  还剩下一个问题，李超树查询点值是个小数，怎么操作？我们把需要查询的点值离散化，并在离散化后的值域上建李超树即可，并把一次函数的 $f(x)$ 改为 $f(g(x))$，其中 $g(x)$ 是离散化后的编号到真实值域的映射．

  $O(n \log^2 n)$．

#include <iomanip>
#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
#define rep(i,a,b) for (int i(a); i<=(b); ++i)
#define drep(i,b,a) for (int i(b); i>=(a); --i)

int k[200100], b[200100];
int Id[200100], cnt;
double dat[200100], ver[200100]; // vertical coordination

double eval(int i, int x) {
    if (i == 0) return -1e18;
    return k[i] * dat[x] + b[i];
}

#define mid ((l+r)/2)
int tr[4000100], tid, lch[4000100], rch[4000100];
int upd(int u, int id, int l = 1, int r = cnt) {
    if (!u) return tr[u = ++tid] = id, u;
    if (eval(tr[u], mid) < eval(id, mid)) std::swap(tr[u], id);
    if (l < r && k[tr[u]] > k[id]) lch[u] = upd(lch[u], id, l, mid);
    else if (l < r) rch[u] = upd(rch[u], id, mid+1, r);
    return u;
}
double qry(int u, int x, int l = 1, int r = cnt) {
    if (!u) return -1e18;
    else if (l == r) return eval(tr[u], x);
    else if (mid >= x) return std::max(eval(tr[u], x), qry(lch[u], x, l, mid));
    else return std::max(eval(tr[u], x), qry(rch[u], x, mid+1, r));
}
#undef mid

int q, rt[800100], st[200100], T;
struct request {
    int op, x, y;
} req[200100];

#define mid ((l+r)/2)
void mark(int qL, int qR, int u = 1, int l = 1, int r = q) {
    if (l > qR || r < qL) return;
    else if (l >= qL && r <= qR) rt[u] = upd(rt[u], qL);
    else mark(qL, qR, u*2, l, mid), mark(qL, qR, u*2+1, mid+1, r);
}
double qry2(int id, int u = 1, int l = 1, int r = q) {
    if (l == r) return qry(rt[u], Id[id]);
    else if (mid >= id) return std::max(qry(rt[u], Id[id]), qry2(id, u*2, l, mid));
    else return std::max(qry(rt[u], Id[id]), qry2(id, u*2+1, mid+1, r));
}
#undef mid

signed main() {
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout << std::fixed;
    cout << std::setprecision(0);
    cin >> q;
    rep(i,1,q) {
        cin >> req[i].op >> req[i].x;
        if (req[i].op == 1) {
            cin >> req[i].y;
            k[i] = req[i].x, b[i] = req[i].y;
        } else if (req[i].op == 3) {
            cin >> req[i].y;
            ver[i] = dat[++cnt] = 1.0*req[i].x/req[i].y;
        }
    }
    std::sort(dat+1, dat+cnt+1);
    cnt = std::unique(dat+1, dat+cnt+1)-dat-1;
    rep(i,1,q) {
        if (req[i].op == 1) {
            st[++T] = i;
        } else if (req[i].op == 2) {
            mark(st[req[i].x], i), st[req[i].x] = 0;
        } else {
            Id[i] = std::lower_bound(dat+1, dat+cnt+1, ver[i])-dat;
        }
    }
    rep(i,1,T)
        if (st[i]) mark(st[i], q);
    int now = 0;
    rep(i,1,q) {
        if (req[i].op == 1) now++;
        else if (req[i].op == 2) now--;
        else if (now == 0) cout << "0\n";
        else cout << req[i].y*qry2(i) << "\n";
    }
}

link。

我要放假

神仙题。

首先可以把两根轴拉成平面（which is a common trick），把决策的过程看作从 $(0, 0)$ 走到 $(n, m)$，每次可以往上走或往右走（左下为 (0, 0)，右上是 (n, m)）。考虑相对于我们走出的决策路线表现出了怎样特征的点会对答案造成贡献。对于 A 套餐的操作 $i$ 处理出 $x_i$，表示做完了 A 套餐的前 i 个操作，最多还能做到 B 套餐的 x_i 操作，同理处理出 $y_j$。

把 $(i, x_i)$，$(y_j, j)$ 看作点放到平面上，当 $(i, x_i)$ 在路径上方是获得 $p_i$ 的贡献，当 $(y_j, j)$ 在路径当中或下方时获得 $q_j$ 的贡献。可以先把 p_i 全部加上然后取反转化调整到和 q_j 同样的贡献条件。

那么现在问题是：给出平面，找出一条从 (0, 0) 到 (n, m) 的路径，使得路径当中以及以下的点权和最大。

考虑 dp，设 $f[i][j]$ 为走到 (i, j) 的最优答案。令 $s[i][j]$ 为点 $(i, j)$ 正下方以及自己的点权和，然后我们发现无论从上一行还是上一列转移写出来都不对劲（$dp[i][j] = dp[i-1][j]+f_1(i, j)+dp[i][j-1]+f_2(i, j)$ 的形式，不好优化），我们考虑从拐点转移（这一步很神奇，同时这一步也是我觉得整道题最 tricky 的地方，但是网上的题解都太草率了，给的转移也不能让我信服），写出的 transitions 是 $\displaystyle dp[i][j] = \max_{k \leqslant j}\{dp[i-1][k]\}+s[i][j]$，自己画一个先右再上的折箭头就理解了。

考察转移发现我们有太多的无用转移，注意到平面中权重非 0 的点只有 $O(n+m)$ 个，于是我们考虑非 0 点。首先把 si 拆成 $w_{0, j}+w_{1, j}+\dots +w_{i, j}$，这样我们的区间修改就是区间加定值而不是加一个毫无特征的序列了。再考虑前缀 max，因为我们是差分数组，我们只需要将 diff array 中的负项删除，并删除其影响，最后一位即是最大值。

/*
lyddnb
dp[i][j] = max[k <= j]{dp[i-1][k]}+s[i][j]
dp[i]: foreach j, j = premax, j += s[i][j]
*/
int n, m, p[1000100], q[1000100];
ll a[1000100], b[1000100], s[1000100], t[1000100], ans, dif[1000100];
vi<pil> g[1000100];  // g[i](x, y) point (i, x) with weight y
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
  for (int i = 1; i <= m; ++i) cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];
  for (int i = 1; i <= n; ++i) {
    if (a[i] > s[i]) continue;
    int j = upper_bound(b + 1, b + m + 1, s[i] - a[i]) - b;
    ans += p[i], g[i].eb(j, -p[i]);
  }
  for (int i = 1; i <= m; ++i) {
    if (b[i] > t[i]) continue;
    if (b[i] + a[n] <= t[i])
      ans += q[i];
    else {
      int j = upper_bound(a + 1, a + n + 1, t[i] - b[i]) - a;
      g[j].eb(i, q[i]);
    }
  }
  set<int> st;
  for (int i = 0; i <= n; ++i) {
    sort(g[i].begin(), g[i].end());
    for (auto const& [x, y] : g[i]) {
      if (x <= m) {
        if (!st.count(x)) st.insert(x), dif[x] = 0;
        dif[x] += y;
      }
    }
    for (auto const& [x, ignore] : g[i]) {
      if (x > m) continue;
      auto it = st.find(x);
      while (it != st.end() && dif[*it] < 0) {
        ll tmp = dif[*it];
        it = st.erase(it);
        if (it != st.end()) dif[*it] += tmp;
      }
    }
  }
  for (auto x : st) ans += dif[x];
  cout << ans << "\n";
}

link。

好题啊。

首先有一个类 kruskal 暴力，就是对于每一个询问，把所有边按权值大小排降序，第一个加进去成为奇环的边就是答案。注意我们不需要关注偶环长成什么样子，所以我们实际上维护的是一棵生成树。这个可以用并查集维护结点到根的边的数量来实现。

因此我们需要关注的边只有 $O(n)$ 条了（生成树），那么维护一个区间的需要关注的边的边集，具体而言就是树边和奇环上的边。考虑用线段树，合并的时候用归并即可。

int n, m, q, fa[2100], dst[2100], ms, mh;
int u[1000100], v[1000100], w[1000100];
vi<bsi<int>> md;
bool flag;
int ldr(int x) {
    if (x != fa[x]) {
        int u = ldr(fa[x]);
        dst[x] ^= dst[fa[x]];
        return fa[x] = u;
    }
    return x;
}
int mrg(int x, int y) {
    int u = ldr(x), v = ldr(y);
    if (u == v) {
        if (dst[x] == dst[y]) return 2;
        return 0;
    }
    fa[v] = u;
    dst[v] = dst[x]^dst[y]^1;
    return 1;
}
bsi<int> mrg(const bsi<int>& lhs, const bsi<int>& rhs) {
    bsi<int> qwq, res;
    merge(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(qwq), [&](int x, int y) {
        return w[x] > w[y];
    });
    for (auto i : qwq) {
        fa[u[i]] = u[i], fa[v[i]] = v[i];
        dst[u[i]] = dst[v[i]] = 0;
    }
    for (auto i : qwq) {
        int tmp = mrg(u[i], v[i]);
        if (tmp) res += i;
        if (tmp == 2) {
            flag = 1;
            break;
        }
    }
    return res;
}
void upd(int now) {
    md[now] = mrg(md[now*2], md[now*2+1]);
}
int qry(int l, int r) {
    bsi<int> res;
    flag = 0;
    for (l += ms-1, r += ms; l < r; l >>= 1, r >>= 1) {
        if (l&1) res = mrg(res, md[l++]);
        if (r&1) res = mrg(md[--r], res);
    }
    if (flag) return w[res.back()];
    return -1;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    mh = ceil(log2(m)), ms = 1<<mh;
    md = vi<bsi<int>>(ms*2, bsi<int>());
    for (int i=1; i<=m; ++i) {
        cin >> u[i] >> v[i] >> w[i];
    }
    for (int i=1; i<=m; ++i) {
        md[i+ms-1] = bsi<int>({i});
    }
    for (int i=ms-1; i>=1; --i) {
        upd(i);
    }
    for (int l,r; q--;) {
        cin >> l >> r;
        cout << qry(l, r) << "\n";
    }
}