根据小学芝士对于每一个区间修在中间是最优的用前缀和优化可以 计算代价然后就可以过掉绿题版本。加上一个裸的wqs二分可以以 的理论复杂度实际最慢的点也不超过400ms的速度过掉紫题版本数据真水。对于本题先wqs二分去掉选m个的限制然后抛弃修在中间是最优的想法那样不好斜率优化。这样写出一个 的dp柿子s为前缀和设 发现可以斜率优化求得。然后发现也可以斜率优化。代码#includebits/stdc.h #define int long long #define pi pairint, int using namespace std; const int N 2e6 5; int n, m, ans, mx, a[N], sum[N], dp[N], f[N], cnt1[N], cnt2[N]; struct line{ int k, b; line(int x 0, int y 0){ k x, b y; } }; struct lctree{ line l[N]; int tg[4 * N]; inline int f(int x, int id){ return l[id].k * x l[id].b; } inline void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(f(mid, id) f(mid, v)) swap(v, id); if(f(l, id) f(l, v)) update(2 * x, l, mid, id); if(f(r, id) f(r, v)) update(2 * x 1, mid 1, r, id); } inline pi query(int x, int l, int r, int k){ pi out; out.first f(k, tg[x]); out.second tg[x]; if(l r) return out; int mid (l r) 1; if(k mid) return min(out, query(2 * x, l, mid, k)); else return min(out, query(2 * x 1, mid 1, r, k)); } }tr1, tr2; inline bool check(int k){ memset(tr1.tg, 0, sizeof(tr1.tg)); memset(tr2.tg, 0, sizeof(tr2.tg)); for(int i 1; i n; i) f[i] cnt1[i] cnt2[i] 0; for(int i 1; i n; i){ pi q tr2.query(1, 1, mx 1, a[i]); f[i] i * a[i] -sum[i] q.first; cnt2[i] cnt1[q.second]; tr1.l[i] line(-a[i], i * a[i] - sum[i] f[i]); tr1.update(1, 1, n, i); q tr1.query(1, 1, n, i); dp[i] sum[i] q.first - k; cnt1[i] cnt2[q.second] 1; tr2.l[i] line(-i, sum[i] dp[i]); tr2.update(1, 1, mx 1, i); } if(cnt1[n] m) ans dp[n] m * k; return cnt1[n] m; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n m; for(int i 1; i n; i){ cin a[i]; mx max(mx, a[i]); sum[i] sum[i - 1] a[i]; } int l -2e6, r 0, res; while(l r){ int mid (l r) 1; if(check(mid)) res mid, l mid 1; else r mid - 1; } check(res); cout ans; return 0; }P8726斜率优化水题 的式子及其明显然后发现这个式子本身就是一次函数不需要做任何化简就可以直接套李超线段树。代码#includebits/stdc.h #define int long long using namespace std; const int N 5e5 5; const int M 2e4 5; int n, tot, t[N], f[N], dp[N], tg[N * 4], ans; struct line{ int k, b; line(int x 0, int y 0){ k x; b y; } }l[N]; int F(int x, int id){ return l[id].k * x l[id].b; } void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(F(mid, id) F(mid, v)) swap(id, v); if(F(l, id) F(l, v)) update(2 * x, l, mid, id); if(F(r, id) F(r, v)) update(2 * x 1, mid 1, r, id); } int query(int x, int l, int r, int k){ if(l k || r k) return -1e18; int res F(k, tg[x]); if(l r) return res; int mid (l r) 1; return max(res, max(query(2 * x, l, mid, k), query(2 * x 1, mid 1, r, k))); } signed main(){ cin n; for(int i 1; i n; i) cin t[i]; for(int i 1; i n; i) cin f[i]; l[0].b -1e18; l[tot] line(t[1], dp[1] / 2 - f[1]); update(1, 0, M, tot); for(int i 2; i n; i){ dp[i] query(1, 0, M, t[i]); ans max(ans, dp[i]); l[tot] line(t[i], dp[i] / 2 - f[i]); update(1, 0, M, tot); } cout ans; return 0; }CF1083E先按横坐标递增排序由于没有嵌套所以纵坐标肯定就是递减的。用 表示用前 个矩形的最大值。显然有 的 dp化简写成注意到 内是一次函数形式用李超线段树优化复杂度 。代码#includebits/stdc.h #define int long long using namespace std; const int N 1e6 5; int n, len, tot, d[N], tg[4 * N], dp[N]; struct rect{ int x, y, v; }r[N]; struct line{ int k, b; line(int x 0, int y 0){ k x; b y; } }l[N]; bool cmp(rect a, rect b){ return a.x b.x; } inline void init(){ sort(r 1, r n 1, cmp); for(int i 1; i n; i){ d[i] r[i].y; } sort(d 1, d n 1); len unique(d 1, d n 1) - d - 1; } inline int g(int x){ return lower_bound(d 1, d len 1, x) - d; } inline int f(int x, int id){ return l[id].k * x l[id].b; } inline void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(f(d[mid], id) f(d[mid], v)) swap(id, v); if(f(d[l], id) f(d[l], v)) update(2 * x, l, mid, id); if(f(d[r], id) f(d[r], v)) update(2 * x 1, mid 1, r, id); } inline int query(int x, int l, int r, int k){ int ans f(d[k], tg[x]); if(l r) return ans; int mid (l r) 1; if(k mid) return max(ans, query(2 * x, l, mid, k)); else return max(ans, query(2 * x 1, mid 1, r, k)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n; for(int i 1; i n; i){ cin r[i].x r[i].y r[i].v; } init(); int ans 0; for(int i 1; i n; i){ dp[i] r[i].x * r[i].y - r[i].v query(1, 1, len, g(r[i].y)); l[tot] line(-r[i].x, dp[i]); update(1, 1, len, tot); ans max(ans, dp[i]); } cout ans; return 0; }直接维护直线或线段的应用这些题可以把操作转化为维护一些直线或线段然后直接用李超线段树。P11728容易发现每一个机器人离原点的距离是关于 的一次函数。也就是说以时间为横坐标离原点的距离为纵坐标建立平面直角坐标系可以用一条条线段也就是有定义域限制的一次函数。那现在有 操作线段变成了一段折线又该怎么做呢很容易发现折线中的每一段还是一条条限制了定义域的一次函数所以本质上没区别。为了确定每一条线段的定义域需要把操作离线然后对于每一个机器人分别操作把它对应的折线一段一段加进去。注意由于是离原点的距离 的负半轴也要考虑所以函数求值时要加绝对值。另外 的值域过大但是我不想写动态开点所以写了离散化。代码#includebits/stdc.h #define int long long #define pi pairint, int using namespace std; const int N 6e5 5; int n, m, maxt, len, tot, c[N], a[N], tg[4 * N], dp[N]; vectorint ask; vectorpi cg[N]; struct line{ int k, b; line(int x 0, int y 0){ k x; b y; } }l[N]; int g(int x){ return lower_bound(a 1, a len 1, x) - a; } int f(int x, int id){ return abs(l[id].k * x l[id].b); } void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(f(a[mid], id) f(a[mid], v)) swap(id, v); if(f(a[l], id) f(a[l], v)) update(2 * x, l, mid, id); if(f(a[r], id) f(a[r], v)) update(2 * x 1, mid 1, r, id); } void modify(int x, int l, int r, int cl, int cr, int id){ if(r cl || l cr) return; if(l cl r cr) update(x, l, r, id); else { int mid (l r) 1; modify(2 * x, l, mid, cl, cr, id); modify(2 * x 1, mid 1, r, cl, cr, id); } } int query(int x, int l, int r, int k){ int ans f(a[k], tg[x]); if(l r) return ans; int mid (l r) 1; if(k mid) return max(ans, query(2 * x, l, mid, k)); return max(ans, query(2 * x 1, mid 1, r, k)); } signed main(){ cin n m; for(int i 1; i n; i){ cin c[i]; cg[i].push_back({0, 0}); } a[1] 0; for(int i 1; i m; i){ int t, k, x; string s; cin t s; maxt max(maxt, t); a[i 1] t; if(s[0] c){ cin k x; if((*cg[k].rbegin()).first t) cg[k].pop_back(); cg[k].push_back({t, x}); } else ask.push_back(t); } m; sort(a 1, a 1 m); len unique(a 1, a m 1) - a - 1; for(int i 1; i n; i){ cg[i].push_back({maxt 1, 0}); int h c[i]; for(int j 0; j cg[i].size() - 1; j){ l[tot] line(cg[i][j].second, h - cg[i][j].first * cg[i][j].second); modify(1, 0, len 1, g(cg[i][j].first), g(cg[i][j 1].first - 1), tot); h (cg[i][j 1].first - cg[i][j].first) * l[tot].k; } } for(int i 0; i ask.size(); i){ cout query(1, 0, len 1, g(ask[i])) \n; } return 0;