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);
}