多段线性函数 （HG 2018.10.2 T2）

 $n\le2*10^5,li\le ri\le10^9$ 怎么做呢？ 我们可以发现，如果只有一个x的话，以y为横坐标，f(y)的值为纵坐标，画出来的图像是个"平底锅"。那么最终图像，也就是把n个平底锅拼在一起，并且两边斜的斜度都是45度。那么，可以发现，最后拼出来的图像，一定是一个单调递减再单调递增的图像，当然可能会有几段是平的。 ### 但是大致符合一个抛物线的形状 于是我们就想到了用三分来求出最小的那段平台。 具体的看代码吧，会有注释的 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int n,L=1e9+7,R=0; int l[100100],r[100100]; int s[30]; int Clac(int x) { //对于每个y，求出来的局部最小值肯定是一定的，而且很好求。。。 int sum=0; for(int i=1;i<=n;i++) { if(x<l[i]) sum+=l[i]-x; else if(x>r[i]) sum+=x-r[i]; } return sum; } signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld",&l[i],&r[i]); L=min(L,l[i]); R=max(R,r[i]); } while(L<R) { int p=L+(R-L)/3,q=R-(R-L)/3; int res1=Clac(p),res2=Clac(q); if(res1==res2 && Clac((p+q)/2)==res1) {L=p,R=q;break;}//在平台上了，注意要判断p，q中点是否值相等，不然会有bug else if(res1>res2) L=p+1;//左三分点要大，把L拉下来 else R=q-1;//反之把R拉下来 } //注意我们求出来的L和R并不是最终答案，还要往左边和右边扩展，这里扩展用到了倍增。 s[0]=1; for(int i=1;i<=30;i++) s[i]=s[i-1]*2; int tmp=Clac(L); for(int i=30;i>=0;i--) { if(s[i]>L) continue; if(Clac(L-s[i])==tmp) L-=s[i]; } for(int i=30;i>=0;i--) if(Clac(R+s[i])==tmp) R+=s[i]; printf("%lld %lld",L,R); return 0; } ```