BZOJ4700: 适者 李超线段树

BZOJ4700: 适者 李超线段树

Description
有n个士兵来攻击你。
你每次可以选择任意一个扣ATK点血。
士兵血量小于等于零就死掉，第i个士兵有bi点血。
第i个士兵如果没死会对你造成ai的伤害。
一开始你可以秒掉两个。
问你你最小扣血。

Sample Input
3 7
30 8
7 35
1 209

Sample Output
28

这道题出成我们的模拟赛了。。。
考场时候只想到一个 O ( n 2 ) O(n^2) O(n2)做法，50分滚粗。。。
有各种各样的性质。
你对于这个问题，如果他一开始不杀人那这个问题就变成国王游戏了。
国王游戏的贪心怎么搞，就微扰一下好了。
那么然后你发现可以枚举一个点作为第一个杀掉的人，再枚举一个点作为第二个杀掉的人。
以下设 x i xi xi为 ( b i + A T K − 1 ) / A T K (bi+ATK-1)/ATK (bi+ATK−1)/ATK， y i yi yi为 a i ai ai。
设第i个人在贪心完之后的答案为 o [ i ] o[i] o[i]，他会对后面所有的减掉一个 x [ i ] ∗ y [ j ] x[i]*y[j] x[i]∗y[j]，那你可以搞一个前缀和 S [ i ] S[i] S[i]表示第i~n个人的 y [ i ] y[i] y[i]总和那么他会减掉一共 o [ i ] + S [ i + 1 ] ∗ x [ i ] o[i]+S[i+1]*x[i] o[i]+S[i+1]∗x[i]，第二个人也类似。
但这样是有重复的多减了一个 x [ i ] ∗ y [ j ] x[i]*y[j] x[i]∗y[j]。
这好像是条直线吧，你好像要维护一个凸包什么的，有点麻烦。
那我就只能方了。。。
考试后，就发现师兄都写了一发李超树搞过去了
（栋老师：我下一次一定出一道只能CDQ+凸包的题！！！）
然后我也去学了发李超树。
本质其实是个线段树吗。
那么你对于一个区间，你维护一个“最优线段势”，即裸露在外面最多的线段。
然后更新分三种情况更新就好了。
时间复杂度是log吧。。。gay队说的

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long LL;
LL _min(LL x, LL y) {return x < y ? x : y;}
LL _max(LL x, LL y) {return x > y ? x : y;}
int read() {int s = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();return s * f;
}struct node {int x, y;
} a[310000];
LL S[310000], g[310000], o[310000];
struct tnode {int lc, rc, c;
} t[60 * 310000]; int cnt, rt[310000];
struct line {LL k, b;
} L[310000]; int pl;
LL maxx;bool cmp(node a, node b) {return a.x * b.y < b.x * a.y;}LL Line(int x, int p) {return (LL)x * L[p].k + L[p].b;
}void Link(int &u, int l, int r, int p) {if(!u) u = ++cnt;if(!t[u].c) {t[u].c = p; return ;}if(l == r) return ;int mid = (l + r) / 2;LL L1 = Line(l, t[u].c), R1 = Line(r, t[u].c);LL L2 = Line(l, p), R2 = Line(r, p);if(L2 >= L1 && R2 >= R1) {t[u].c = p; return ;}LL M1 = Line(mid, t[u].c), M2 = Line(mid, p);if(M1 >= M2) {if(L1 >= L2) Link(t[u].rc, mid + 1, r, p);else Link(t[u].lc, l, mid, p);} else {if(L1 <= L2) Link(t[u].rc, mid + 1, r, t[u].c);else Link(t[u].lc, l, mid, t[u].c);t[u].c = p;}
}void Merge(int &u1, int u2, int l, int r) {if(!u1 || !u2) {u1 = u1 + u2; return ;}Link(u1, l, r, t[u2].c);int mid = (l + r) / 2;Merge(t[u1].lc, t[u2].lc, l, mid);Merge(t[u1].rc, t[u2].rc, mid + 1, r);
}void query(int u, int l, int r, int p) {if(!u || !t[u].c) return ;if(l == r) return ;int mid = (l + r) / 2;maxx = _max(maxx, Line(p, t[u].c));if(p <= mid) query(t[u].lc, l, mid, p);else query(t[u].rc, mid + 1, r, p);
}int main() {int n = read(), ATK = read();for(int i = 1; i <= n; i++) {a[i].y = read();a[i].x = (read() + ATK - 1) / ATK;} sort(a + 1, a + n + 1, cmp);LL ans = 0, sum = 0;for(int i = 1; i <= n; i++) {sum += a[i].x;ans += (sum - 1) * a[i].y;o[i] = (sum - 1) * a[i].y;} for(int i = n; i >= 1; i--) S[i] = S[i + 1] + a[i].y;for(int i = 1; i <= n; i++) g[i] = (LL)S[i + 1] * a[i].x;for(int i = n; i >= 1; i--) {L[++pl].k = -(LL)a[i].y;L[pl].b = g[i] + o[i];Link(rt[i], 0, 10000, pl);Merge(rt[i], rt[i + 1], 0, 10000);}LL minn = ans;for(int i = 1; i < n; i++) {LL hh = ans - g[i] - o[i]; maxx = 0;query(rt[i + 1], 0, 10000, a[i].x);minn = _min(minn, hh - maxx);
//		for(int j = i + 1; j <= n; j++) {
//			minn = _min(minn, hh - g[j] - o[j] + a[i].x * a[j].y);
//		}} printf("%lldn", minn);return 0;
}