贪心、线段树、哈希

Solution 1：思索许久，发现使得整个环连通至多需要激活 $n-1$ 条道路，所以必定存在一条道路没有被激活。同时由于该道路没有激活，所有给定点对都不能通过这条道路，于是连接所有点对的方案都可以确定。

枚举没有被激活的道路编号，强制所有点对连通都不能通过这条道路，初始这个道路的编号为 $n$。然后进行道路覆盖，朴素实现的时间复杂度为 $O(n^2)$，对于边 $i$ 记录有当前多少个点对 $(l,r) (l<r)$ 第一个覆盖的节点为 $i$，枚举到 $i$ 时把这些点对的道路覆盖反转，然后更新反转后第一个被覆盖节点的信息，这样每个点对的道路至多被反转两次，使用线段树维护。

注意对线段树叶子节点的处理，如果叶子结点没被打标记那么被覆盖长度应该置为 $0$ 而不是从左右儿子继承，这些节点没有左右儿子。

由于 $n,m$ 同阶，时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r,w,m;}s[800'005];
vector<int> v[200'005],w[200'005];
int n,m;
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r,s[u].w=0,s[u].m=0;
    if(l==r) return;
    build(u*2,l,(l+r)/2),build(u*2+1,(l+r)/2+1,r);
}
void update(int u,int l,int r,int k){
    if(s[u].l>r||s[u].r<l) return;
    if(s[u].l>=l&&s[u].r<=r) s[u].m+=k;
    else update(u*2,l,r,k),update(u*2+1,l,r,k);
    if(s[u].m) s[u].w=s[u].r-s[u].l+1;
    else if(s[u].l==s[u].r) s[u].w=0;
    else s[u].w=s[u*2].w+s[u*2+1].w;
}
void solution(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) v[i].clear(),w[i].clear();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        v[x].push_back(y);
        update(1,x,y-1,1);
    }
    int ans=s[1].w;
    for(int i=1;i<=n-1;i++){
        for(int j:v[i]){
            update(1,i,j-1,-1);
            update(1,1,i-1,1),update(1,j,n,1);
            w[j].push_back(i);
        }
        for(int j:w[i]){
            update(1,1,j-1,-1),update(1,i,n,-1);
            update(1,j,i-1,1);
        }
        ans=min(ans,s[1].w);
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}

Solution 2：看题解来的，很强大的维护手法。

考虑反转道路的维护，线段树配合 vector 的手法有些麻烦。而给每个点对随机一个权值，随便覆盖一个方向（区间异或随机权值）之后全局异或这个点对的随机权值就可以实现反转道路的操作。

同时，任何一个位置的权值都是由若干个点对的覆盖操作得到的，所以可以全局异或任意一个位置的权值，这代表反转所有经过这个位置的点对的覆盖。

最小化没有被覆盖的道路数量即最大化异或权值为 $0$ 的位置个数，显然应该异或全局出现次数最多的数来最大化 $0$ 的数量，所以答案为 $n$ 减出现最多的数的数出现次数。因为权值是随机的，可以使用 unordered_map 维护权值出现次数。

由于 $n,m$ 同阶，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
mt19937_64 sky(chrono::steady_clock::now().time_since_epoch().count());
unsigned long long sum[200'005];
int n,m,ans;
void solution(){
    cin>>n>>m,ans=0;
    for(int i=1;i<=n;i++) sum[i]=0ull;
    for(int i=1;i<=m;i++){
        static unsigned long long x;
        static int l,r;
        cin>>l>>r,x=sky();
        sum[l]^=x,sum[r]^=x;
    }
    for(int i=1;i<=n;i++) sum[i]^=sum[i-1];
    unordered_map<unsigned long long,int> w;
    for(int i=1;i<=n;i++) ans=max(ans,++w[sum[i]]);
    cout<<n-ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}