题目传送门(BZOJ)

题解 :

温馨提示, 光标悬停在公式上可以放大

首先 : 定义单个旗杆为一列, 能互相产生推动力折扣的为一行
证明如下三个性质(希望直接看到解题步骤请跳过这部分) :

性质 1 : 旗杆顺序和答案无关

我们发现每行所能产生的推动力损耗只和这行帆的数量有关
若第 $i$ 行所具有的帆数量为 $F[i]$,
那么这行产生的答案贡献是 $\frac{F[i]\times (F[i]-1)}{2}$
总的答案就是 $\sum\limits_{i=1}^{maxHeight}\frac{F[i]\times (F[i]-1)}{2}$
这个性质的证明是从推动力损耗的定义中得来的

性质 2 : 需要在某旗杆上放一面旗时, 放在当前所有行中帆数量最少的那一行一定不会比其他行差

命题 : 由于帆越多, 损耗越大, 若存在某行 $i$ 帆数为 $x$, 另一行 $j$ 帆数 $\le x-2$,
且能从第 $i$ 行把一面帆移动到第 $j$ 行时, 移动之一定会使答案更优

证明 : 令第 $i$ 行帆数量为 $x$, 第 $j$ 行数量为 $y$, 且 $y \le x-2$
那么 原答案为 $\frac{x\times (x-1)+y\times (y-1)}{2} \cdots \qquad \qquad(1)$
挪动一面帆的答案为 $\frac{(x-1)\times(x-2)+(y+1)\times y}{2} \cdots \qquad (2)$
只需证明 $(2) < (1)$ 即可
那么 $(2)\times 2 – (1)\times 2$ 得
即 $2y-2x+3 < 0$
由 $y \le x-2$ 可得, $2y-2x+4 \le 0$, 故命题得证

故只要证明现在放和未来放等价或者不会更劣即可,
发现现在不选最小的, 未来在保证答案最优的情况下也一定会选最小的
由于每行对答案的贡献只和帆数有关, 所以现在放和未来放等价, 且未来必然会放这行, 故现在放在该行即可

性质 3 :

令每行的帆数量为 $F[i]$, 那么设最下面一行为起始行 $1$, F[]必然是一个单调不增的序列
首先我们知道可以放帆的数量一定是一个单调不增的序列
那么假设有行$i > j$, 且 $F[i] > F[j]$,
由于 $i$ 比 $j$ 多出来那部分的旗杆一定还没有放帆 (不然就不是多出来的了)
故第 $i$ 行的该面帆必然可以放在第 $j$ 行, 使得 $F[i], F[j]$ 的大小交换, 且对答案无影响


本题需要用到的性质证明完毕

由于性质(1), 我们可以从大到小把所有旗杆排个序, 不会对答案产生影响.
题目就变成了对于每个旗杆 $i$, 从最小且高度小于 $h[i]$ 的所有行中选出最小的(由性质(2)) $k[i]$ 行, 并在这些行上多放一面旗
由于性质(3), 这 $k[i]$ 行一定是从 $h[i]$ 开始向下共 $k[i]$ 行
看上去我们直接找到 $L = h[i]-k[i]+1$ 这个点, 然后把 $L \sim h[i]$ 这部分区间加 $1$ 即可
但是发现当区间加 $1$ 之后, 不一定能保证性质(3),
这种情况当且仅当 $F[L] == F[L-1]$ 时才会发生.
不过这不是什么重要的问题, 设 $x = F[L]$, 那么在 $L \sim h[i]$ 且 $F[i] < x$ 的行已经可以加 $1$ 了
设这部分加 $1$ 的长度为 $Len$, 我们只要再补 $k[i]-Len$ 个加 $1$ 即可
而帆数量恰好等于 $x$ 的行数一定大于这个 $k[i]-Len$ (从 $L$ 到刚刚加的起始点, 恰好是 $k[i]-Len$ 个 $x$)
我们直接在所有值恰好等于 $x$ 的行中, 挑选最下面的 $k[i]-Len$ 行即可,
这样就在保证选了最小的 $k[i]$ 个的情况下, 又满足了性质(3)
按这个规则把所有旗杆都做完之后, 直接统计一下每行都有多少, 计算答案即可

线段树需要维护区间最大/最小值, 支持区间修改, 支持查询权值为 $x$ 的最左/最右端点, 支持查询某点 $x$ 的权值
复杂度 $O(N\log N)$

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls p << 1#define rs p << 1|1using namespace std;const int N = 100100;char buf[100000], *p1, *p2;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)inline int read() { int x = 0; char ch = nc(); while(ch < 48) ch = nc(); while(ch > 47) x = (x<<3)+(x<<1)+(ch^48), ch = nc(); return x;}struct MAST { int h, k; bool operator < (const MAST &A) const { return h < A.h; }}a[N];struct SEGTREE { int mn[N<<2], mx[N<<2], laz[N<<2]; inline void pushUp(int p) { mn[p] = min(mn[ls], mn[rs]); mx[p] = max(mx[ls], mx[rs]); } inline void giv(int p, int c) { mn[p] += c; mx[p] += c; laz[p] += c; } inline void pushDown(int p) { if(laz[p]) { giv(ls, laz[p]); giv(rs, laz[p]); laz[p] = 0; } } int getKth(int l, int r, int p, int K) { if(l == r) return mn[p]; pushDown(p); int mid = (l+r) >> 1; if(K <= mid) return getKth(l, mid, ls, K); else return getKth(mid+1, r, rs, K); } int getLeft(int l, int r, int p, int x) { if(l == r) return l; pushDown(p); int mid = (l+r) >> 1; if(mn[ls] <= x) return getLeft(l, mid, ls, x); else return getLeft(mid+1, r, rs, x); } int getRight(int l, int r, int p, int x) { if(l == r) return l; pushDown(p); int mid = (l+r) >> 1; if(mx[rs] < x) return getRight(l, mid, ls, x); else return getRight(mid+1, r, rs, x); } void change(int l, int r, int p, int x, int y) { if(x <= l && y >= r) return giv(p, 1); pushDown(p); int mid = (l+r) >> 1; if(x <= mid) change(l, mid, ls, x, y); if(y > mid) change(mid+1, r, rs, x, y); pushUp(p); } long long getAns(int l, int r, int p) { if(l == r) return (long long)mn[p]*(mn[p]-1)/2; pushDown(p); int mid = (l+r) >> 1; return getAns(l, mid, ls)+getAns(mid+1, r, rs); }}Tr;long long ans;int n, maxHeight;int main() { n = read(); for(int i = 1; i <= n; i ++ ) a[i].h = read(), a[i].k = read(), maxHeight = max(maxHeight, a[i].h); sort(a+1, a+n+1); for(int i = 1; i <= n; i ++ ) { int K = Tr.getKth(1, maxHeight, 1, a[i].h-a[i].k+1); int L = Tr.getLeft(1, maxHeight, 1, K); int R = Tr.getRight(1, maxHeight, 1, K); if(R < a[i].h) { Tr.change(1, maxHeight, 1, R+1, a[i].h); Tr.change(1, maxHeight, 1, L, L+(a[i].k-a[i].h+R)-1); } else { Tr.change(1, maxHeight, 1, L, L+a[i].k-1); } } ans = Tr.getAns(1, maxHeight, 1); printf("%lld\n", ans);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<