ACG002D - Stamp Rally

题目链接

题目分析

如果对于单个询问，显然我们可以二分答案来做。然后我们就可以整体二分了。

整体二分的思想是这样的：

首先二分一个答案，对于所有询问都判断一遍，然后按照需求分成两部分。之后对于每个部分都进行同样的操作。

对于这道题目，我们需要用并查集维护连通性。而如果是DFS顺序的话，我们就需要用到可删边的并查集。这样的时间复杂度是$O(n\log^2n)$的。然而我们可以用BFS来做，并且保持每一个深度边数递增，这样就可以直接使用普通的并查集了。时间复杂度$O(n\log n)$。

参考程序

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

const int Maxn = 100010;
int N, M, Q;
struct query {
    int x, y, z, Index;
};
query Query[ Maxn ], Temp[ Maxn ];
int X[ Maxn ], Y[ Maxn ], Ans[ Maxn ], Father[ Maxn ], Size[ Maxn ];
struct rec {
    int l, r, L, R, Deep;
};
rec Rec[ Maxn ];
int L, R;

int GetFather( int x ) {
    if( x == Father[ x ] ) return x;
    Father[ x ] = GetFather( Father[ x ] );
    return Father[ x ];
}

void Union( int x, int y ) {
    int a = GetFather( x ), b = GetFather( y );
    if( a == b ) return;
    Size[ a ] += Size[ b ];
    Father[ b ] = a;
    return;
}

int main() {
    scanf( "%d%d", &N, &M );
    for( int i = 1; i <= M; ++i ) scanf( "%d%d", &X[ i ], &Y[ i ] );
    scanf( "%d", &Q );
    for( int i = 1; i <= Q; ++i ) 
        scanf( "%d%d%d", &Query[ i ].x, &Query[ i ].y, &Query[ i ].z );
    for( int i = 1; i <= Q; ++i ) Query[ i ].Index = i;
    L = R = 0;
    R = ( R + 1 ) % Maxn;
    Rec[ R ] = ( rec ) { 0, M, 1, Q, 1 };
    int LastDeep = 0, LastEdge = 0;
    while( L != R ) {
        L = ( L + 1 ) % Maxn;
        rec Work = Rec[ L ];
        if( Work.l > Work.r || Work.L > Work.R ) continue;
        if( Work.l == Work.r ) {
            for( int i = Work.L; i <= Work.R; ++i )
                Ans[ Query[ i ].Index ] = Work.l;
            continue;
        }
        if( Work.Deep != LastDeep ) {
            for( int i = 1; i <= N; ++i ) {
                Father[ i ] = i;
                Size[ i ] = 1;
            }
            LastDeep = Work.Deep;
            LastEdge = 0;
        }
        int mid = ( Work.l + Work.r ) >> 1;
        int LL = Work.L - 1, RR = Work.R + 1;
        for( int i = LastEdge + 1; i <= mid; ++i ) Union( X[ i ], Y[ i ] );
        LastEdge = mid;
        for( int i = Work.L; i <= Work.R; ++i ) {
            int x = GetFather( Query[ i ].x ), y = GetFather( Query[ i ].y );
            int t = 0;
            if( x == y ) t = Size[ x ]; else t = Size[ x ] + Size[ y ];
            if( t < Query[ i ].z ) 
                Temp[ ++LL ] = Query[ i ];
            else
                Temp[ --RR ] = Query[ i ];
        }
        for( int i = Work.L; i <= Work.R; ++i )
            Query[ i ] = Temp[ i ];
        R = ( R + 1 ) % Maxn;
        Rec[ R ] = ( rec ) { Work.l, mid, RR, Work.R, Work.Deep + 1 };
        R = ( R + 1 ) % Maxn;
        Rec[ R ] = ( rec ) { mid + 1, Work.r, Work.L, LL, Work.Deep + 1 };
    }
    for( int i = 1; i <= Q; ++i ) printf( "%d\n", Ans[ i ] );
    return 0;
}