题解P6163【[Cnoi2020]领域极限】

· · 题解

打 ARC 的时候做了这题，赛后知道洛谷上有这道原题，不得不说AT官方题解的做法是真的妙，所以就讲讲我赛时的贪心做法吧(???)。

先推个式子，首先把 x 按升序排序，那么有

\sum\limits_{i=1}^n\sum\limits_{j=1}^n|x_i - x_j|=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nx_j - x_i

先抛掉前面那个那个 2，然后考虑每个 x 被算了多少次，转化为

\sum\limits_{i=1}^n(n-i-(i-1))x_i=\sum\limits_{i=1}^n(-2i+n+1)x_i

也就是说，第 i 个人（按 x 递增排序后的）的位置会给答案带来一个 2i-n-1 的贡献，所以要让前一半的人尽量靠后，后一半人尽量靠前，于是考虑贪心。

最开始一定是让所有人尽量靠后，所以直到遇到某个人的右端点了再把他放下。

考虑将所有的 l 值和 r 值放到一起离散化，然后维护扫描线，对于当前扫描到的位置 p，记 vl_p 表示以 p 为左端点的人的数量，vr_p 表示以 p 为右端点的人的数量，lst 为目前确定位置的人的数量，cnt 为左端点在 p 以及 p 之前的人的数量。

那么首先 cnt \leftarrow cnt + vl_p，ans \leftarrow ans + p \sum\limits_{i=lst+1}^{lst+vr_p}(2i-n-1)，lst \leftarrow lst + vr_p，这几步应该不用多说，就是更新 lst,cnt，然后更新放在这里的答案，因为右端点就在 p 上的只能放在这上面了。

然后接下来就是比较关键的一步了，就是如果 cnt+lst \ge n+1，那么就意味着把目前挂在手上的这 cnt-lst 个人再往后放一个位置对答案的贡献开始增加，否则就是会减少。所以如果发现 cnt+lst \ge n+1 了，那么就将现在挂着的人全部放在 p 上，而再后面的人一定都是后半段了，它们要尽量靠前，所以都取左端点计算答案即可。

感觉整篇题解写的挺草率的，也不知道讲没讲明白，欢迎各位指正。

代码：

#include<cstdio>
#include<algorithm>
#define TY ll
#define MAXN 300002
#define debug if( 1 &&putchar('>'))
#define FOR(i,a,b) for(TY i=(a);i<=(b);++i)
#define fOR(i,a,b) for(TY i=(a);i<(b);++i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);--i)
#define rOF(i,a,b) for(TY i=(a);i>(b);--i)
using namespace std;
typedef long long ll;
const TY M=998244353;
typedef unsigned long long ull;
TY _abs(TY a){return a<0?-a:a;}
TY maxn(TY a,TY b){return a>b?a:b;}
TY minn(TY a,TY b){return a<b?a:b;}
TY gcd(TY a,TY b){return b?gcd(b,a%b):a;}
TY qp(TY a,TY b){TY ans=1;do{if(b&1)ans=ans*a%M;a=a*a%M;}while(b>>=1);return ans;}
char getc(){char ch=getchar();while(ch==' '||ch=='\n')ch=getchar();return ch;}
TY qr(){
    char ch=getchar();TY s=0,x=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';return x*s;
}void qw(TY a,char ch){
    if(a<0){a=-a;putchar('-');}
    if(a>9)qw(a/10,0);putchar(a%10+'0');
    if(ch)putchar(ch);
}TY n=qr(),m,l[MAXN],r[MAXN],b[MAXN<<1],ans,cnt,lst,vl[MAXN<<1],vr[MAXN<<1];
inline TY js(TY x,TY y){return (y-x)*(x+y-n);}
//将(lst,cnt]的人放在某个位置的权值和，其实循环计算也可以
int main(){
    FOR(i,1,n){b[i*2-1]=l[i]=qr();b[i<<1]=r[i]=qr();}
    sort(b+1,b+(n<<1|1));m=unique(b+1,b+(n<<1|1))-b-1;
    FOR(i,1,n){
        ++vl[l[i]=lower_bound(b+1,b+m+1,l[i])-b];
        ++vr[r[i]=lower_bound(b+1,b+m+1,r[i])-b];//预处理一些数组
    }FOR(i,1,m){
        cnt+=vl[i];
        if(lst+vr[i]+cnt>n){//如果开始转变为后半段
            ans+=b[i]*js(lst,cnt);
            FOR(j,i+1,m)fOR(k,0,vl[j])
                ans+=((++cnt)*2-n-1)*b[j];//将后面的全部取左端点
            break;//考虑完直接退出
        }fOR(j,0,vr[i])ans+=((++lst)*2-n-1)*b[i];//更新lst
    }qw(ans,0);
    return 0;
}