J Symmetrical Painting 2019牛客多校第九场

我太菜了啊，这题想了好久没想出来，队友想出来，一开始还错了，4个多小时才过，队友爆long long WA了一发，然后我数组全改成long long ，结果这题只有30mb的空间，然后我又mle了两发。。。。罚时爆炸。

其实可以知道，对于一条黑色矩形，中位线从左向右移动，那这条黑色矩形的贡献是先增大再减小的。

可以想到，中位线一定在某个矩形的左端点或者右端点或者中点上，因为每段的中间，都是递增的或者递减的或者平的函数图像，那么一定在端点取得最大值。

那么把左端点，右端点，中点离散化，然后从左到右扫，对于一条黑色矩形的左端点，则表示从这里开始每次贡献要+1，中点开始，每次贡献+1-2=-1，右端点开始每次贡献+1-2+1=0

从ty0记录在之前有多少左端点,ty1记录有多少右端点，ty2记录有多少中点。

然后就可以计算出对于每条中位线的贡献最大是多少了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int size=3e5+5;
const int lens=1e6+5;
int L[size],R[size];
int idl[size],idr[size],idmid[size];
int cnt[lens][3];
vector<int> v;
int main()
{
    int n;
    scanf("%d",&n);
    int l,r;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&L[i],&R[i]);
        L[i]=L[i]*2;
        R[i]=R[i]*2;
    }
    v.clear();
    for(int i=1;i<=n;i++)
    {
        v.push_back(L[i]);
        v.push_back(R[i]);
        v.push_back((1ll*L[i]+1ll*R[i])/2);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int sz=v.size();
    for(int i=1;i<=n;i++)
    {
        idl[i]=lower_bound(v.begin(),v.end(),L[i])-v.begin()+1;
        idr[i]=lower_bound(v.begin(),v.end(),R[i])-v.begin()+1;
        idmid[i]=lower_bound(v.begin(),v.end(),(1ll*L[i]+1ll*R[i])/2)-v.begin()+1;
    }
  
    for(int i=1;i<=n;i++)
    {
        cnt[idl[i]][0]++;cnt[idr[i]][1]++;cnt[idmid[i]][2]++;
    }
    LL ty0=cnt[1][0],ty1=cnt[1][1],ty2=cnt[1][2];
    LL ans=0;
    LL tmp=ans;
    for(int i=1;i<sz;i++)
    {
        int r=v[i],l=v[i-1];
        tmp=tmp+1LL*(r-l)*(ty0-2*ty2+ty1);
        ty0+=cnt[i+1][0],ty1+=cnt[i+1][1],ty2+=cnt[i+1][2];
//      cout<<ty0<<' '<<ty1<<' '<<ty2<<endl;
//      cout<<tmp<<endl;
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans);
}