T1
主观难度：【0】
不会做的出门左转，一机房有初一小朋友正在学前缀和。
T2
主观难度：【1】
容易看出方程式 \(dp_i = dp_j + (n-j) \max_{k-j+1}^{i} a_k\)。这个式子是很容易想到斜率优化的。但是合并凸壳不太好做。
观察 Subtask 4，我们发现这个 Subtask 的答案显然等于 \(na_1\)。仔细思考后我们发现对于一个连续的不增子序列，设子序列开头为 \(i\)，中间任一元素为 \(j\)，如果你把 \(j\) 选为一段的开头那么在付出 \(a_i(n-i)\) 的代价之外你还需要付出额外的 \(a_j(n-j)\) 的代价，但是如果 \(i\) 的段包含了 \(j\) 那么只需要付出 \(a_i(n-i)\) 的代价。故对于一个连续的不增子序列，只选开头最优。
于是我们把这个序列变成了不降的，发现方程式变为了 \(dp_i = dp_j + (n-j)a_i\)，斜率优化搞搞即可。
#include <bits/stdc++.h>
#define llong long long
#define N 1000006
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n;
llong a[N], dp[N];struct Seg{llong k, b;
};
#define gety(s,x) (s.k*x+s.b)Seg val[N<<6]; int ls[N<<6], rs[N<<6], tsiz, root;
#define mid ((l+r)>>1)inline int newnode(){return ++tsiz;
}
inline void modify(Seg k, int& x = root, int l = 1, int r = 1e9){if(!x) return val[x = newnode()] = k, void();Seg k1 = val[x], k2 = k;if(gety(k1, mid) > gety(k2, mid)) swap(k1, k2);val[x] = k1;if(l == r) return;if(gety(k1, l) > gety(k2, l)) modify(k2, ls[x], l, mid );if(gety(k1, r) > gety(k2, r)) modify(k2, rs[x], mid+1, r);return;
}
inline llong query(int pos, int& x = root, int l = 1, int r = 1e9){if(!x) return 1e18+3;llong res = gety(val[x], pos);if(pos <= mid) res = min(res, query(pos, ls[x], l, mid ));else res = min(res, query(pos, rs[x], mid+1, r));return res;
}int main(){
// freopen("in.txt", "r", stdin);read(n);for(int i = 1; i <= n; ++i) read(a[i]);for(int i = 1; i <= n; ++i) a[i] = max(a[i], a[i-1]);modify({n, 0});for(int i = 1; i <= n; ++i){dp[i] = query(a[i]);modify({n-i, dp[i]});}printf("%lld", dp[n]);return 0;
}T3
主观难度：【0】
花了 2.5h 吃了一坨大的，非常美味。
容易想到维护斜率。但是碍于区间赋值操作，区间的两端不好维护。于是我们开两个线段树，一个维护实际值，一个维护斜率。就做完了。
时间复杂度 \(\mathrm O(n \log n)\)。
代码长度 6.5k。好大一坨。
#include <bits/stdc++.h>
#define llong long long
#define N 300005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, q;
int a[N];#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)class SegT1{private:struct Seg{llong k, b; bool vis;};Seg val[N<<2], tag1[N<<2], tag2[N<<2];inline void addtag1(int x, Seg k){tag2[x] = {0, 0, false};val[x] = tag1[x] = k;return;}inline void addtag2(int x, Seg k){val[x].k += k.k, tag2[x].k += k.k;val[x].b += k.b, tag2[x].b += k.b;tag2[x].vis = true;return;}inline void pushdown(int x){if(tag1[x].vis){addtag1(ls(x), tag1[x]);addtag1(rs(x), tag1[x]);tag1[x] = {0, 0, false};}if(tag2[x].vis){addtag2(ls(x), tag2[x]);addtag2(rs(x), tag2[x]);tag2[x] = {0, 0, false};}return;}public:inline void build(int x = 1, int l = 1, int r = n){tag1[x] = tag2[x] = {0, 0, false};if(l == r) return addtag1(x, {0, a[l], true});build(ls(x), l, mid), build(rs(x), mid+1, r);return;}inline void modify1(int L, int R, Seg k, int x = 1, int l = 1, int r = n){if(L <= l && R >= r) return addtag1(x, k);pushdown(x);if(L <= mid) modify1(L, R, k, ls(x), l, mid );if(R > mid) modify1(L, R, k, rs(x), mid+1, r);return;}inline void modify2(int L, int R, Seg k, int x = 1, int l = 1, int r = n){if(L <= l && R >= r) return addtag2(x, k);pushdown(x);if(L <= mid) modify2(L, R, k, ls(x), l, mid );if(R > mid) modify2(L, R, k, rs(x), mid+1, r);return;}inline llong query(int pos, int x = 1, int l = 1, int r = n){if(l == r) return val[x].k*pos+val[x].b;pushdown(x);if(pos <= mid) return query(pos, ls(x), l, mid );else return query(pos, rs(x), mid+1, r);}inline llong operator[](int pos){return query(pos);}
} val;class SegT2{private:struct Node{int l, r; int val, len1, len2;llong val1, val2;bool vis;};Node val[N<<2]; llong tag1[N<<2], tag2[N<<2];const llong NOTAG = (llong)1e18+3;Node merge(Node a, Node b){if(!a.vis) return b;if(!b.vis) return a;Node res; res.vis = true;res.l = a.l, res.r = b.r;res.val = max(a.val, b.val);if(a.val2 == b.val1) res.val = max(res.val, a.len2+b.len1);res.val1 = a.val1, res.val2 = b.val2;if(a.len1 == a.r-a.l+1 && a.val1 == b.val1) res.len1 = a.len1+b.len1;else res.len1 = a.len1;if(b.len2 == b.r-b.l+1 && a.val2 == b.val2) res.len2 = a.len2+b.len2;else res.len2 = b.len2;return res;}inline void pushup(int x){val[x] = merge(val[ls(x)], val[rs(x)]);return;}inline void addtag1(int x, llong k){tag1[x] = k, tag2[x] = NOTAG;Node res;res.l = val[x].l, res.r = val[x].r;res.val1 = res.val2 = k;res.val = res.len1 = res.len2 = val[x].r-val[x].l+1;res.vis = true;val[x] = res;return;}inline void addtag2(int x, llong k){if(tag2[x] == NOTAG) tag2[x] = 0;val[x].val1 += k, val[x].val2 += k;tag2[x] += k;return;}inline void pushdown(int x){if(tag1[x] != NOTAG){addtag1(ls(x), tag1[x]);addtag1(rs(x), tag1[x]);tag1[x] = NOTAG;}if(tag2[x] != NOTAG){addtag2(ls(x), tag2[x]);addtag2(rs(x), tag2[x]);tag2[x] = NOTAG;}}public:inline void build(int x = 1, int l = 1, int r = n-1){tag1[x] = tag2[x] = NOTAG;if(l == r) return val[x] = {l, r, 1, 1, 1, a[l+1]-a[l], a[l+1]-a[l], true}, void();build(ls(x), l, mid), build(rs(x), mid+1, r);pushup(x);}inline void modify1(int L, int R, llong k, int x = 1, int l = 1, int r = n-1){if(L <= l && R >= r) return addtag1(x, k);pushdown(x);if(L <= mid) modify1(L, R, k, ls(x), l, mid );if(R > mid) modify1(L, R, k, rs(x), mid+1, r);pushup(x);return;}inline void modify2(int L, int R, llong k, int x = 1, int l = 1, int r = n-1){if(L <= l && R >= r) return addtag2(x, k);pushdown(x);if(L <= mid) modify2(L, R, k, ls(x), l, mid );if(R > mid) modify2(L, R, k, rs(x), mid+1, r);pushup(x);return;}inline Node query(int L, int R, int x = 1, int l = 1, int r = n-1){if(L <= l && R >= r) return val[x];pushdown(x);Node res; res.vis = false;if(L <= mid) res = merge(res, query(L, R, ls(x), l, mid ));if(R > mid) res = merge(res, query(L, R, rs(x), mid+1, r));return res;}inline int evaluate(int L, int R){return query(L, R-1).val+1;}
} seg;// In all SegT options, 1 = cover, 2 = addinline int solve1(){while(q--){int op, l, r, k, b;read(op, l, r);if(op == 1 || op == 2) read(k, b);if(op == 3) puts("1");}return 0;
}int main(){// freopen("in.txt", "r", stdin);read(n, q);for(int i = 1; i <= n; ++i) read(a[i]);if(n == 1) return solve1();val.build(), seg.build();while(q--){int op, l, r; read(op, l, r);if(op == 1){ // Addllong k, b; read(b, k);b -= l*k;val.modify2(l, r, {k, b, true});if(l != r) seg.modify2(l, r-1, k);if(l != 1) seg.modify1(l-1, l-1, val[l]-val[l-1]);if(r != n) seg.modify1(r, r, val[r+1]-val[r]);}if(op == 2){ // Coverllong k, b; read(b, k);b -= l*k;val.modify1(l, r, {k, b, true});if(l != r) seg.modify1(l, r-1, k);if(l != 1) seg.modify1(l-1, l-1, val[l]-val[l-1]);if(r != n) seg.modify1(r, r, val[r+1]-val[r]);}if(op == 3){ // Evaluateif(l == r) puts("1");else printf("%d\n", seg.evaluate(l, r));}}return 0;
}T4
主观难度：【1+】
模拟赛场上糖了。
我们把每个点位能到达的区域画在图上，发现是从原点开始向左下和右下无限延伸的两条射线组成的图形。这不太好看，于是我们令 \(x_i = t_i+a_i, y_i = t_i-a_i\)，坐标系被我们旋转了 \(45 \degree\)（顺便还放大到了 \(\sqrt{2}\)，但这不重要）。于是发现一个点可达另一个点当且仅当 \(x_i \le x_j \land y_i \le y_j\)。这下方便多了。
然而 Hootime 场上做到这里不会做了。
其实接下来要求的就是最小链覆盖。我们通过 Dilworth 定理将其转化为最长反链，于是这题就变成了导弹拦截，用你喜欢的方式求出 LIS 即可。
就做完了。
#include <bits/stdc++.h>
#define llong long long
#define N 500005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, m;
struct Node{int x, y;};
Node a[N];
int tmp[N], cnt;int main(){freopen("in.txt", "r", stdin);read(m, n);for(int i = 1; i <= n; ++i) read(a[i].x);for(int i = 1; i <= n; ++i) read(a[i].y);for(int i = 1; i <= n; ++i) a[i] = {a[i].x+a[i].y, a[i].x-a[i].y};sort(a+1, a+n+1, [&](Node o1, Node o2){return o1.x>o2.x || (o1.x==o2.x&&o1.y>o2.y);});for(int i = 1; i <= n; ++i){int pos = lower_bound(tmp+1, tmp+cnt+1, a[i].y)-tmp;tmp[pos] = a[i].y;if(pos > cnt) ++cnt;}printf("%d", cnt);return 0;
}