【算法】离散化

【题解】

答案一定存在于区间的左右端点、与区间左右端点距离0.5的点上

于是把所有坐标扩大一倍，排序（即离散化）。

让某个点的前缀和表示该点的答案。

初始sum=∑c[i]

在l[i]处加上a[i]-c[i]，在r[i]+1处加上b[i]-a[i]。

从左到右计算sum并比较出最大值即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int inf=0x3f3f3f3f,maxn=50010;struct cyc{ int x,y;}a[maxn*3];long long ans,sum;int n,A,B,C,D,E,cnt;bool cmp(cyc a,cyc b){ return a.x
            
             '9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int main(){ int T=read(); while(T--) { int n=read();sum=0,cnt=0; for(int i=1;i<=n;i++) { A=read(),B=read(),C=read(),D=read(),E=read();A*=2;B*=2; sum+=E; a[++cnt].x=A,a[cnt].y=C-E;a[++cnt].x=B+1,a[cnt].y=D-C; } sort(a+1,a+cnt+1,cmp); ans=sum; for(int i=1,now=1;i<=cnt;i++) { while(now<=cnt&&a[now].x==a[i].x){sum+=a[now].y;now++;} ans=max(ans,sum); } printf("%lld\n",ans); } return 0;}