题解：CF2261D2 Come Be My Friend, Don't Be So Scared (Hard Version)

· · 题解

首先注意到的性质是，如果一个位置可以被已有的区间区分开，则无论你怎么加区间，它之后一定还是可以被区分开。

所以我们用异或哈希的方法，给每个区间赋随机权值，每个位置的权值定义为所有覆盖它的区间的权值的异或和。用差分完成。然后如果一个位置的权值是唯一的，我们直接去掉它。对剩下的所有位置构成的子序列抽出来按照哈希值重新标号得到一个新序列 b，长度设为 m。

接下来发挥你的注意力。你注意到对于每个 1\leq i\leq m，如果 b_i=b_{i+1}（当 i=m 的时候这里 i+1 视作 1）都至少有一个区间的右端点在 i 或者至少有一个区间的左端点在 i+1，否则一定区分不开 i 和 i+1。所以答案下界为 L=\lceil\frac{m}{2}\rceil。

然后你发现这不就是简单版本吗。你直接把这些分界的位置拿出来，直接照搬简单版本里的构造 [1,L],[2,L+1],\cdots,[L,2L-1] 就做完了。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 800005

//首先使用 hyperregular trick 进行异或哈希
//加入一个线段不可能让原本区分开的位置区分不开
//考虑把所有区分不开的位置拼在一起

mt19937_64 rnd(20070414);

int n,m,dif[MAXN],b[MAXN],len,pnt[MAXN],id[MAXN],ori[MAXN],siz[MAXN],fir[MAXN];

vector< pair<int,int> > ans;

inline void solve(){
    scanf("%lld%lld",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ){
        int l,r; scanf("%lld%lld",&l,&r);
        int x = rnd();
        dif[l] ^= x;
        if( r < n ) dif[r + 1] ^= x;
    }
    map<int,int> M,to; int cnt = 0;
    for( int i = 1 ; i <= n ; i ++ )
        dif[i] ^= dif[i - 1],M[dif[i]] ++;
    for( int i = 1 ; i <= n ; i ++ ){
        int v = dif[i]; if( M[v] == 1 ) continue;
        if( !to.count( v ) ) to[v] = ++cnt;
        b[++len] = to[v],id[len] = ++pnt[to[v]],ori[len] = i;
        siz[to[v]] ++;
    }
    vector<int> pos; int res = 0;
    for( int i = 1 ; i <= len ; i ++ )
        if( b[i] == b[i % len + 1] ) pos.emplace_back( i ),res ++;
    for( int i = 1 ; i <= ( res + 1 ) / 2 ; i ++ )
        ans.emplace_back( make_pair( ori[pos[i - 1] + 1] , ori[pos[min( res - 1 , i + res / 2 - 1 )]] ) );
    printf("%lld\n",(int)ans.size());
    for( pair<int,int> p : ans ) printf("%lld %lld\n",p.first,p.second);
    for( int i = 1 ; i <= n ; i ++ ) dif[i] = 0;
    for( int i = 1 ; i <= len ; i ++ ) b[i] = id[i] = ori[i] = 0;
    for( int i = 1 ; i <= cnt ; i ++ ) pnt[i] = siz[i] = fir[i] = 0;
    len = 0;
    ans.clear();
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}

::::