T1 加法
最开始看了好久没想出来，先做 T2 去了，然后回来想了一会儿发现自己可能智商有点问题。
看到求最小值最大，第一反应肯定是二分，那我们怎么应该怎么 check 呢？
考虑顺次枚举序列 $A$ 中的每一个数，然后如果这个数没有达到 mid 的要求，我们肯定是要添加区间的。
那么我们怎么添加区间呢？因为我们已经枚举到了 $A_i$，所以之前的数肯定都已经满足了条件，我们就只需要考虑 $A_i$ 及后面的数了。
那么对于所有左端点小于等于 $i$ 的区间，我们就可以不考虑左端点了，要加入的就是这些区间中右端点最大的区间了。
这样的贪心是满足局部最优 = 全局最优的，我们现在只需要考虑怎么完成这个过程就可以了。
假设现在枚举到了 $i$，我们需要把左端点小于等于 $i$ 的区间中的右端点最大值求出来，这一过程可以用优先队列来完成。
那我们可以怎么去给后面的 $A$ 数组去增加值呢？最好想的当然是用树状数组或者线段树去进行维护。
但其实是可以不用的，如果这个区间被加入了答案，我们可以维护一个 sum 值，表示当前总共被增加的所有值的和。
对于被计入答案的区间的值如何在适当时减去，我们可以在 $i$ 这个点的答案计算完成后，枚举所有右端点在 $i$ 的区间，如果这个区间被记入了答案，我们减去它对答案的贡献就可以了。
至于如何判断是否被计入答案，用最简单的 bool 数组维护就行了。
时间复杂度 $O(n \log^2 n)$，代码贴在下面，具体细节请看代码(100pts)：
#define N 200005
#define LL long long
bool vis[N];
LL t,n,m,k,a,v[N];//v在这里是表示的序列A
struct Node{int l,r,num;}s1[N],s2[N];
priority_queue<pair<int,int> > q;
bool check(LL mid,int in=0,int all=0){
while(!q.empty()) q.pop();
for(int i=1;i<=m;i++) vis[i]=0;
for(int i=1,l=1,r=1;i<=n;i++){
while(l<=m&&s1[l].l<=i) q.emplace(s1[l].r,s1[l].num),l++;
while(r<=m&&s2[r].r<i) in-=vis[s2[r++].num];
while((mid-v[i]+a-1)/a-in>0){
if(q.empty()||q.top().first<i||++all>k) return 0;
in++,vis[q.top().second]=1,q.pop();
}
}
return 1;
}//s1表示按左端点从小到大排列后的区间，s2表示按右端点从小到大排列后的区间
T2 期末考试
考虑枚举是在哪一天结束的所有课程，那我们需要求的就是对于在指定的一天结束课程，会产生多少不愉快度。
首先我们来计算学生的不愉快度，这个过程我们可以通过预处理前缀和来求出。
接下来我们考虑老师的不愉快度，分两种情况进行讨论：
第一种，$B \leq A$ 的情况，明显我们只需要进行操作 2，所以只需要求出所有课程需要提前的总天数就可以了，这个过程也可以用前缀和完成。
第二种，$B > A$ 的情况，那我们就需要尽量进行操作 1，比第一种要多求的就是所有课程可以延后的总天数，这个过程仍然可以使用前缀和来完成。
值得注意的是对于测试点 13-14，因为 $C$ 太大了，所以处理过程中会炸 long long，要进行特判。
具体实现看代码，时间复杂度 $O(n \log n)$，瓶颈在排序(100pts)：
#define N 100005
#define LL long long
LL A,B,C,n,m,ans=LLONG_MAX,smin=ans,b[N],sum[N],res[N];
int main(){
scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&n,&m);
for(LL i=1,x;i<=n;i++) scanf("%lld",&x),res[x+1]++,smin=min(smin,x);
for(int i=1;i<=m;i++) scanf("%lld",b+i);
sort(b+1,b+m+1);
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
if(int l=1,r=1;C==10000000000000000ll){
while(l<=m&&b[l]<smin) l++;
while(r<=m&&b[r]<=smin) r++;
LL lc=(l-1ll)*smin-sum[l-1],rc=sum[m]-sum[r-1]-(m-r+1)*smin;
if(B<=A) return printf("%lld\n",l,r,rc*B);
return printf("%lld\n",min(lc,rc)*A+max(rc-lc,0ll)*B),0;
}
for(int i=1;i<=N-5;i++) res[i]+=res[i-1];
for(int i=1;i<=N-5;i++) res[i]+=res[i-1];
for(int i=1,l=1,r=1;i<=N-5;i++){
while(l<=m&&b[l]<i) l++;
while(r<=m&&b[r]<=i) r++;
LL lc=(l-1ll)*i-sum[l-1],rc=sum[m]-sum[r-1]-(m-r+1)*i;
if(B<=A) ans=min(ans,rc*B+res[i]*C);
else ans=min(ans,min(lc,rc)*A+max(rc-lc,0ll)*B+res[i]*C);
}
printf("%lld\n",ans);
}
T3 观光公交
先来说下 80pts 的 $O(n^2k)$ 做法。
首先，我们来想一下如果对于一个区间，我们用了一个氮气加速器后会发生什么情况：
大家都知道的是现在坐在车上的所有人都会少等 1 个单位的时间，那会不会对后面等车的人产生什么影响呢？
可以发现，只要是车到达的时候所有人都已经在车站在等了，那么就会让后面等车的人少等 1 个单位的时间。
所以对于 k 个氮气加速器，我们可以每个加速器 $O(n^2)$ 去寻找到能减少最多等待时间的区间，然后给这个区间的列车行驶时间减 1 就行了。
代码如下(80pts，原版数据 100pts)：
#define N 100005
int n,m,k,ans,d[N],t[N],x[N],y[N],ari[N],lat[N],off[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++) scanf("%d",d+i);
for(int i=1;i<=m;i++){
scanf("%d%d%d",t+i,x+i,y+i);
lat[x[i]]=max(lat[x[i]],t[i]),off[y[i]]++;
}
for(int i=1,now=0;i<=n;i++) ari[i]=now,now=max(now,lat[i])+d[i];
for(int i=1;i<=k;i++){
int smax=0,num=0;
for(int j=2;j<=n;j++){
if(!d[j-1]) continue;int sum=0;
for(int k=j;k<=n;k++){
sum+=off[k];
if(ari[k]<=lat[k]) break;
}
if(sum>smax) smax=sum,num=j;
}
d[num-1]--;
for(int j=num;j<=n;j++) if(--ari[j]<lat[j]) break;
}
for(int i=1;i<=m;i++) ans+=ari[y[i]]-t[i];
printf("%d\n",ans);
}
接下来我们来看 100pts 的 $O(n \log n)$ 做法。
现设最终答案为 ans，在初始时我们将它值赋值成 $-\sum T_i$，相当于提前把要减的值减了。
接下来我们设 $lat_i$ 表示 $i$ 车站最晚来的人，$s_i$ 表示车比 $lat_i$ 晚到的时间，$off_i$ 表示第 $i$ 个车站下的人数。
所以有 $s_i=\max(s_{i-1}+lat_{i-1}+D_{i-1}-lat_i)$，$ans+=off_i(s_{i-1}+lat_{i-1}+D_{i-1})$。
考虑一个区间 $[l,r]$，如果 $(l,r]$ 里面的 $s_i(l <i \leq r)$ 的值均大于 $0$，那么我们就可以通过使用 $\min(d_l,s_i,k)$ 个加速器来让整个区间内的到达时间减少等量的值。
这样答案就会减少这个值乘上区间内成为乘客终点的数量和（对于每个车站，所有的乘客均单独计算）。
我们把这样的区间都称作有意义的区间，即能对答案产生贡献的区间。
初始时，我们可以把原序列拆分成至多 $n$ 个极大的有意义区间，然后把它们放进优先队列里面，并以区间内成为乘客终点的数量和作为关键字做一个大顶堆。
这样我们取出的一定是单个加速器能产生最大贡献的区间。
对于每次处理完一个区间后，如果 $k \neq 0$一定会产生 $d_l<0$ 或 $s_i<0$
的情况，我们就以这里为断点，cut 成两个区间重新丢回优先队列里。
找断点的这一步可以通过线段树来维护。
这样我们这一道题基本上就处理完了，剩下的就只是代码的实现了，虽然不是很简单就是了，代码贴在下面(100pts)：
#define N 100005
#define LL long long
LL ans,s[N];
int n,m,k,lst=1,d[N],ari[N],lat[N],off[N];
struct Node{
int l,r;
friend bool operator<(Node a,Node b){return off[a.r]-off[a.l]<off[b.r]-off[b.l];}
};
priority_queue<Node> q;
struct Segment_tree{
void build(int l,int r,int p)//对s[i]进行区间最小值build
void update(int sl,int sr,int x,int l,int r,int p)//让[sl,sr]区间中的s[i]值减小x
pair<int,int> query(int sl,int sr,int l,int r,int p)//返回first为最小值，second为在s数组中的下标
}SGT;//模板省略
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++) scanf("%d",d+i);
for(int i=1,t,x,y;i<=m;i++){
scanf("%d%d%d",&t,&x,&y);
lat[x]=max(lat[x],t),off[y]++,ans-=t;
}
for(int i=2;i<=n;i++) off[i]+=off[i-1];
for(int i=2;i<=n;i++){
s[i]=max(0ll,s[i-1]+lat[i-1]+d[i-1]-lat[i]);
if(!s[i]) q.push({lst,i}),lst=i;
ans+=(LL)(off[i]-off[i-1])*(s[i-1]+lat[i-1]+d[i-1]);
}
if(lst<n) q.push({lst,n});
SGT.build(2,n,1);
while(k&&!q.empty()){
Node now=q.top();q.pop();int num=0,sum=0;
if(now.l+1<now.r){
auto tmp=SGT.query(now.l+1,now.r-1,2,n,1);
sum=tmp.first,num=tmp.second;
}
if(!num) sum=0x3f3f3f3f;
int use=min({k,d[now.l],sum}),cut=(use==d[now.l]?now.l+1:num);
ans-=(LL)use*(off[now.r]-off[now.l]),k-=use;
if(!k) break;
if(use&&now.l+1<now.r) SGT.update(now.l+1,now.r-1,use,2,n,1);
d[now.l]-=use;
if(now.l<cut) q.push({now.l,cut});
if(cut<now.r) q.push({cut,now.r});
}
printf("%lld\n",ans);
}
T4 侦察守卫
最开始我本来定义的状态是用 $dp_{i,j,0/1}$ 表示对于顶点 $i$，在 $j$ 层内是/否有侦察点时的最小值。
可惜这个状态对于祖先侦察到儿孙的情况不好转移，所以想了一下过后拆成了两个状态 $f_{i,j}$ 和 $g_{i,j}$。
其中，$f_{i,j}$ 表示 $i$ 节点的子树全被覆盖到，还能向上覆盖 $j$ 层的最小价值，而 $g_{i,j}$ 则表示 $i$ 子树的 $j$ 层以下全部被覆盖到，$j$ 层以内啥都不知道的最小价值。
让结点 $1$ 作为根节点，易得我们要求取的答案就是 $f_{1,0}/g_{1,0}$，接下来我们考虑如何转移，记当前枚举到的节点为 $x$，子节点为 $y$。
则 $f_{x,i}$ 分两种情况转移，一是用前面的子节点去覆盖上面的节点，二是用当前的子节点去覆盖上面的节点，两种情况取 min 就行了：
$f_{x,i}=\min(f_{x,i}+g_{y,i},f_{y,i+1}+g_{x,i+1})$，由定义我们还可以知道：$f_{x,i}=min({f_{x,i},f_{x,i+1}})$。
而 $g_{x,i}$ 的转移就简单了：$g_{x,i}=g_{x,i}+g_{y,i-1}$，由定义我们还可以知道：$g_{x,i}=min({g_{x,i},g_{x,i-1}})$，接下来我们要考虑的就是初始状态了：
因为 $f_{x,i}$ 会从 $f_{x,i+1}$ 转移，所以 $f_{x,d+1}=inf$，对于只有一个点且这个点还需要被监视的情况 $f_{x,0}=g_{x,0}=w_x$。
还有就是显而易见的：$f_{x,i}=w_x(1 \leq i \leq d)$，状态转移就是这样，代码贴在下面(100pts)：
void dfs(int x,int fa){
f[x][d+1]=0x3f3f3f3f;
if(vis[x]) f[x][0]=g[x][0]=w[x];//vis是否需要被监视
for(int i=1;i<=d;i++) f[x][i]=w[x]
for(auto y:v[x]){//v数组存图
if(y==fa) continue;
dfs(y,x);
for(int i=d;i>=0;i--) f[x][i]=min(f[x][i]+g[y][i],f[y][i+1]+g[x][i+1]);
for(int i=d;i>=0;i--) f[x][i]=min(f[x][i],f[x][i+1]);
g[x][0]=f[x][0];//易得，用于满足g[fa][1]的转移
for(int i=1;i<=d;i++) g[x][i]+=g[y][i-1];
for(int i=1;i<=d;i++) g[x][i]=min(g[x][i],g[x][i-1]);
}
}