题目链接

题目大意

给出环上的一组区间，你需要构造环上的一组区间使得这些区间的交是给定的区间的并。

解题思路

集合的德摩根律告诉我们 \overline{\cup{A_i}}=\cap\overline{A_i}（区间的并的补等于区间的补的交），所以输出每一段未被给出区间覆盖的区间的补即可。

老实说还是有点一知半解。。。如果让我自己手动从头推理或许给多长时间也想不到吧:(

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
struct node{
    int l,r;
} a[N];

int cmp(node a,node b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>a[i].l>>a[i].r;
        }
        sort(a+1,a+m+1,cmp);
        cout<<m<<endl;
        for(int i=2;i<=m;i++){
            cout<<a[i].l<<" "<<a[i-1].r<<endl;
        }
        cout<<a[1].l<<" "<<a[m].r<<endl;
    }
    return 0;
}