codeforces 1452E Two Editorials
题目链接：https://codeforces.com/problemset/problem/1452/E
题意：一次比赛中 2 个dalao来讲题，总共有 $m$ 个选手来听讲，题目总数为 $n$ ，编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解，两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题，这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的，第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多，其中得分是他们讲的每个题目收听的人数。
数据范围：$1 \leq n, m \leq 2000,1 \leq k \leq n$， $1 \leq l_{i} \leq r_{i} \leq n$
输出：两个人采取某种讲题方案后加一块能获得的最大分数
题解：
把每个听讲的人看成一条线段，问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看，可以 $O(n^2)$ 枚举两个人讲题的起点，之后如果能使用滑动窗口动态维护， $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后，第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话，是可以 O1 得到两个人各自的和的，但是题目要求两个人之间如果有均覆盖到的听讲者，那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作，但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况，此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例，就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候，听众对应的线段可以分为三类：（1）在iend之前结束的；（2）在iend之后开始的；（3）在iend之前开始，在iend之后结束的。
对于情况1，我们只需要在移动第二个人的窗口的时候完全不计算这些选手的贡献就可以了，因为这种情况第二个人不可能比第一个人占用更多的题目。对于情况3，我们直接加上所有的第二个人的滑动窗口内的所有值就可以了，所以这种情况可以直接用差分然后两遍前缀和来处理。比较复杂的是情况2。对于这种情况下某一个听讲的选手来说，我们从挪动出第一步开始，到某个点结束，这中间我们都是要减去第一个滑动窗口内这个选手的贡献的，因为这种情况下这名选手跑去听第二个人的讲解了。那么我们可以把这个减去作为一个权值写到另外一个数组里，然后在枚举更新答案的时候把这个权值删掉。注意我们移动到某个点之后，第二个人对于这名听课区间“跨在”中间的选手的讲题开始少于第一个人讲的题目，这时我们反而要减去第二个人这里这名选手的贡献。好在这个变化过程是连续的，我们可以把之前对第一个人减去的权值每次-1，加到sum1+sum2上，然后更新答案。也就是说，对于一名特定的，感兴趣的题目区间跨在了第一个人的讲课范围的结尾的两端的选手，我们在计算sum1和sum2之后，要加上一个负的权值，用来去掉他在两个人的覆盖区域中被min掉的那一部分。这个负权在区间上是以一个恒定值出现一段，然后开始逐渐以1的增量上升直到0，例如 -3 -3 -3 -2 -1 这样的一个序列，画出来就是一个倒梯形。至于这个负权的具体长度和数值，需要根据两个人的区间和对应的选手的区间来计算。
Ok，talk is cheap，更多的细节在代码中：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2000+5;
int pre1[maxn],pre2[maxn],pre3[maxn],pre4[maxn],l[maxn],r[maxn];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,k,ans=0;
cin>>n>>m>>k;
for(int i=1;i<=m;++i){
cin>>l[i]>>r[i];
pre1[l[i]]+=1,pre1[r[i]+1]+=-1;
}
for(int i=1;i<=n;++i){
pre1[i]+=pre1[i-1];
}
for(int i=1;i<=n;++i){
pre1[i]+=pre1[i-1];
}
for(int i=1;i<=n-k+1;++i){
int iend=i+k-1,jend=0,sum1=pre1[iend]-pre1[i-1],sum2=0;
ans=max(ans,sum1);
for(int j=0;j<=n+1;++j){
pre2[j]=pre3[j]=pre4[j]=0;
}
for(int tm=1;tm<=m;++tm){
if(r[tm]<=iend){
continue;
}else if(iend<l[tm]){
pre2[l[tm]]+=1,pre2[r[tm]+1]+=-1;
}else if(i<l[tm]){
pre2[l[tm]]+=1,pre2[r[tm]+1]+=-1;
jend=r[tm]-(iend-l[tm]);
pre4[i]+=iend-l[tm]+1;
pre3[r[tm]]+=-1,pre3[jend-1]+=1;
}
}
for(int j=1;j<=n;++j){
pre2[j]+=pre2[j-1];
}
for(int j=1;j<=n;++j){
pre2[j]+=pre2[j-1];
}
for(int j=n;j>=0;--j){
pre3[j]+=pre3[j+1];
}
for(int j=n;j>=0;--j){
pre3[j]+=pre3[j+1]+pre4[j];
}
for(int j=i+1;j<=n-k+1;++j){
sum2=pre2[j+k-1]-pre2[j-1]+pre3[j];
ans=max(ans,sum1+sum2);
}
}
cout<<ans;
}