[AtCoder Grand Contest 040][结论+贪心]B.Two Contests_综合

好久都没有写过博客了(~~准确来说是我写了很多篇都没发…~~(upd:已发))
这场AGC太迟了…于是就决定用小号做一个小时…结果B题一直WA…卡死了…

题面

题目描述

$10^9$ contestants, numbered $1$ to $10^9$ , will compete in a competition. There will be two contests in this competition.

The organizer prepared $N$ problems, numbered $1$ to $N$ , to use in these contests. When Problem $i$ is presented in a contest, it will be solved by all contestants from Contestant $L_i$ to Contestant $R_i$ (inclusive), and will not be solved by any other contestants.

The organizer will use these $N$ problems in the two contests. Each problem must be used in exactly one of the contests, and each contest must have at least one problem.

The joyfulness of each contest is the number of contestants who will solve all the problems in the contest. Find the maximum possible total joyfulness of the two contests.

数据规模

$2≤N≤10^5$
$1≤L_i≤R_i≤10^9$
All values in input are integers.

输入格式

Input is given from Standard Input in the following format:

$N$
$L_1 \ R_1$
$L_2 \ R_2$
$?$
$L_N \ R_N$

输出格式

Print the maximum possible total joyfulness of the two contests.

样例

The optimal choice is:

· Use Problem $1$ and 3 in the first contest. Contestant $5$ , $6$ , and $7$ will solve both of them, so the joyfulness of this contest is $3$ .
· Use Problem $2$ and $4$ in the second contest. Contestant $2$ , $3$ , and $4$ will solve both of them, so the joyfulness of this contest is $3$ .

The total joyfulness of these two contests is $6$ . We cannot make the total joyfulness greater than $6$ .

翻译

给你 $n$ 个区间 $L_i,R_i]$ ，请你将区间分为两组，使得两组分别求交之后的长度最大。
$2≤N≤10^5$
$1≤L_i≤R_i≤10^9$

题解

这题一旦想偏了…就真的很难做出来了…
先说题解的思路:
考虑拿出 $L$ 最大的区间 $a$ 和 $R$ 最小的区间 $b$ ，然后分两种情况：
1.若将 $a$ ， $b$ 分在同一集合，其他区间对这个区间就完全没有任何影响了，因此我们找一个长度最大的放在另一边就好。
2.若将 $a$ ， $b$ 分在不同集合，由于两集合的一个端点都已经确定，因此我们将区间按照 $l$ 排序，则可以发现最优划分一定是前缀+后缀，因此直接枚举断开点就好了。
然后是自己的辣鸡想法:
首先按照 $l$ 从小到大排序。
注意到一确定了两个区间的初始选择，由于每个区间的长度随着选入区间的增多一定递减，那我们一定会选择合并两个集合之一得到区间长度和更大的那个。
但是如何确定每个集合先选哪一个区间呢[我就是因为这个错的]…其实我们不用考虑这么多，只要多加一个将两集合合并起来的选择就好了。
具体请见代码。
时间复杂度: $O(nlog?n)O(n\log n)$

实现

/*Lower_Rating*/
/*AGC040 B*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;#define LL long long
#define MAXN 800000
#define MOD 998244353
#define Pr pair<int,int>
#define X first
#define Y second
#define INF 2000000000
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}
int add(int x,int y){
    return (x+y>=MOD)?x+y-MOD:x+y;}
int dec(int x,int y){
    return (x-y<0)?x-y+MOD:x-y;}
int mul(int x,int y){
    return 1LL*x*y%MOD;}int n,mn,id;
struct Seg{
    int l,r;
}p[MAXN+5];
bool cmp(Seg s1,Seg s2){
    if(s1.l==s2.l)return s1.r<s2.r;return  s1.l<s2.l;
}
int bin(int l1,int r1,int l2,int r2){
    return max(min(r1,r2)-max(l1,l2)+1,0);
}
int main()
{
    n=read();mn=INF;for(int i=1;i<=n;i++)p[i].l=read(),p[i].r=read();sort(p+1,p+n+1,cmp);int l1=p[1].l,r1=p[1].r,l2=p[2].l,r2=p[2].r;for(int i=2;i<=n;i++){
    int val1=max(r2-l2+1,0)+bin(l1,r1,p[i].l,p[i].r);int val2=max(r1-l1+1,0)+bin(l2,r2,p[i].l,p[i].r);int val3=max(p[i].r-p[i].l+1,0)+bin(l1,r1,l2,r2);if(val1>=val2&&val1>=val3){
    l1=max(l1,p[i].l);r1=min(r1,p[i].r);}else if(val2>=val1&&val2>=val3){
    l2=max(l2,p[i].l);r2=min(r2,p[i].r);}else{
    l1=max(l1,l2);r1=min(r1,r2);l2=p[i].l,r2=p[i].r;}}printf("%d",max(r1-l1+1,0)+max(r2-l2+1,0));
}