题目传送门(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],
由于 ij 多出来那部分的旗杆一定还没有放帆 (不然就不是多出来的了)
故第 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]-Lenx)
我们直接在所有值恰好等于 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原创, 转载必须以链接形式注明>原文链接<