[ICPC2022济南站] H.Set of Intervals 【分类讨论】

分析：

只有一个区间的时候输出1

只有两个区间的时候，只有三种情况：包含，相离，相交。可以推出一个数学式子计算相交和相离的情况下的答案，我们用$getans(l_1,r_1,l_2,r_2)$表示。那么包含的情况的答案则可以通过容斥原理，假设$[l_1,r_1]$是小的区间，则$getans(l_1,r_1,l_2,r_2)+getans(l_2,r_2,l_1,r_1)-getans(l1,r1,l1,r1)$得到。

接下来我们考虑其他情况：

假设现在对于所有区间，其最小的左端点位置为$minl$，由第一个区间提供，最大的右端点位置为$maxr$，也由第一个区间提供，那么对于剩下的其他$n-1$个区间，可以计算他们的最小值$secl$和他们的最大值$secr$，答案就是上面两个区间包含的情况的答案。

如果$minl$和$maxr$由不同的区间提供，也就是分别由第一个和第二个区间提供。那么还是同样求出其他$n-2$个区间的$secl$和$secr$。

接下来，分几种情况讨论：

1.两个端点一个在$[minl,maxr]$之中，另一个在$[secl,secr]$之中，这种情况完全可以取到，利用计算包含的函数计算。

2.两个端点都在$[minl,secl-1]$之中，这个情况可以发现，左端点一定是由第一个区间和其他某个区间的并构成，因此能取到$[minl,secl-1]$的全集。而右端点只能由第二个区间获得，因为其他区间染指不到$secl-1$以及之前。所以可以利用相交或者包含的那个函数计算

3.两个端点都在$[secr+1,maxr]$之中，这个情况和情况2对称

4.左端点在$[minl,sec-1]$，右端点在$[secr+1,maxr]$。这时候，如果有$n\ge 4$，那么总是可以把第一个区间和其他区间合并，第二个区间和其他区间合并，于是左右端点能取到所有情况，利用相离的计算即可。否则$n=3$，此时可以选择将左端点和其他区间合并，再将右端点和其他区间合并，分别计算结果，然后再减去算重的部分。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 105000;
 5 
 6 struct node{
 7     int l,r;
 8 }p[maxn];
 9 
10 long long calc(int l1,int r1,int l2,int r2){
11     if(l1 > r1) return 0;
12     if(l2 > r2) return 0;
13     if(r1 < l2){
14     return 1ll*(r1-l1+1)*(r2-l2+1);
15     }else{
16     r1 = min(r1,r2);
17     l2 = max(l2,l1);
18     if(l1 > r1) return 0;
19     if(l2 > r2) return 0;
20     return 1ll*(l2-l1)*(r2-l2+1)+1ll*(r1-l2+1)*(r2-l2+r2-r1)/2;
21     }
22 }
23 
24 int main(){
25     ios::sync_with_stdio(false);
26     int t; cin >> t;
27     while(t--){
28     int n;
29     cin >> n;
30     for(int i=1;i<=n;i++) cin >> p[i].l >> p[i].r;
31     if(n == 1){cout<<1<<endl;continue;}
32     int samepos = 0;
33     int minnl = 1e9,ps1 = 0,maxxr = -1e9,ps2 = 0;
34     for(int i=1;i<=n;i++){
35         if(p[i].l < minnl && p[i].r > maxxr){
36         ps1 = i,minnl = p[i].l;
37         ps2 = i,maxxr = p[i].r;
38         }else{
39         if(p[i].l < minnl){
40             ps1 = i;
41             minnl = p[i].l;
42         }else if(p[i].r > maxxr){
43             ps2 = i;
44             maxxr = p[i].r;
45         }
46         }
47     }
48     if(ps1 == ps2){
49         samepos = 1;
50         swap(p[1],p[ps1]);
51     }else{
52         if(ps2 == 1 && ps1 == 2){
53         swap(p[1],p[2]);
54         }else if(ps2 == 1){
55         swap(p[1],p[2]);
56         swap(p[ps1],p[1]);
57         }else{
58         swap(p[1],p[ps1]);
59         swap(p[2],p[ps2]);
60         }
61     }
62     if(n == 2 && !samepos){
63         cout<<calc(p[1].l,p[1].r,p[2].l,p[2].r)<<endl;
64         continue;
65     }
66     int secl = 1e9,secr = -1e9;
67     int st = (samepos == 1?2:3);
68     for(int i=st;i<=n;i++){
69         secl = min(secl,p[i].l);
70         secr = max(secr,p[i].r);
71     }
72     long long p1 = calc(minnl,maxxr,secl,secr)+calc(secl,secr,minnl,maxxr)-calc(secl,secr,secl,secr);
73     if(samepos == 1){
74         cout<<p1<<endl;
75     }else{
76         //both l,secl-1
77         p1 += calc(minnl,secl-1,p[2].l,secl-1);
78         //both r,secr-1
79         p1 += calc(secr+1,p[1].r,secr+1,maxxr);
80         //l,secl-1;r,secr-1;
81         if(n >= 4){
82         p1 += calc(minnl,secl-1,secr+1,maxxr);
83         }else{
84         if(p[1].r >= secl-1 || p[2].l <= secr+1){
85 
86             p1 += calc(minnl,secl-1,secr+1,maxxr);
87         }else{
88             p1 += calc(minnl,secl-1,p[2].l,maxxr)+calc(minnl,p[1].r,secr+1,maxxr)-calc(minnl,p[1].r,p[2].l,maxxr);
89         }
90         }
91         cout<<p1<<endl;
92     }
93     }
94 }