[CF1452E] Two Editorials

Description

有 (n) 个问题，有 (m) 个选手，每个选手有一个喜欢的问题区间 ([l_i,r_i])，现在有两个讲题人可以选择两个区间长度为 (k) 的区间来讲题，每个选手只能听一个讲题人的讲题，并产生他听到的喜欢的问题数量的分数。通过选择讲题人讲题的区间，最大化分数和。(n,m le 2000)

Solution

将选手按照峰值点 (l_i + r_i) 排序。暴力枚举将选手划分成两份的分界线，前半部分听第一个讲题人，后半部分听第二个讲题人。

假设现在已经划分好了 ([1,p], [p+1,m])，对于前半部分的选手，计算出每个题目被记入的次数（利用差分前缀和），然后扫一遍算出讲题人该放在哪。对于后半部分也同理。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 5005;

struct Range 
{
    int l,r;
    bool operator < (const Range &rhs)
    {
        return l+r < rhs.l+rhs.r;
    }
};

signed main()
{
    ios::sync_with_stdio(false);

    int n,m,k;
    cin>>n>>m>>k;
    
    vector <Range> participants(m+2);
    for(int i=1;i<=m;i++) cin>>participants[i].l>>participants[i].r;

    sort(participants.begin()+1,participants.begin()+m+1);

    int ans=0;

    for(int p=1;p<=m;p++)
    {
        int sec1_l=1, sec1_r=p;
        int sec2_l=p+1, sec2_r=m;

        vector <int> tmp(n+2);
        for(int i=sec1_l;i<=sec1_r;i++) 
        {
            tmp[participants[i].l]++;
            tmp[participants[i].r+1]--;
        }
        for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
        for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];

        
        int tans1=0;
        for(int i=1;i+k-1<=n;i++) tans1=max(tans1,tmp[i+k-1]-tmp[i-1]);

        for(int i=0;i<n+2;i++) tmp[i]=0;

        for(int i=sec2_l;i<=sec2_r;i++) 
        {
            tmp[participants[i].l]++;
            tmp[participants[i].r+1]--;
        }
        for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
        for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
        

        int tans2=0;
        for(int i=1;i+k-1<=n;i++) tans2=max(tans2,tmp[i+k-1]-tmp[i-1]);
        
        ans=max(ans,tans1+tans2);
    }

    cout<<ans<<endl;
    
}