BZOJ4569 [Scoi2016]萌萌哒（并查集，倍增）

类似\(ST表\)的思想，倍增\(log(n)\)地合并

你是我家的吗？不是就来呀啦啦啦。还有要来的吗？没了！那有多少个家就映射多少答案呀

倍增原来这么好玩

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("\n-----------\n")

#define D_e(x) std::cout << (#x) << " : " <<x << "\n"

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define Pause() system("pause")

#include <ctime>

#define TIME() fprintf(stderr, "\nTIME :　%.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define FileOpen() ;

#define FilSave ;

#define Pause() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

const int N = 1e5 + 7;

const int mod = 1e9 + 7;

int fa[N][18];

inline int Find(int x, int t) {

	return x == fa[x][t] ? x : fa[x][t] = Find(fa[x][t], t);

}

inline void Merge(int x, int y, int t) {

	int p = Find(x, t), q = Find(y, t);

	if(p != q){

		fa[p][t] = q;

		if(t){

			Merge(x, y, t - 1), Merge(x + (1 << (t - 1)), y + (1 << (t - 1)), t - 1);

		}

	}

}

inline long long Pow(long long a, long long b) {

	long long s = 1;

	while(b){

		if(b & 1) s = s * a % mod;

		a = a * a % mod, b >>= 1;

	}

	return s;

}

int lg[N];

int main() {

	int n, m;

	io >> n >> m;

	if(n == 1){

		printf("10");

		return 0;

	}

	R(i,2,n) lg[i] = lg[i >> 1] + 1;

	R(i,1,n){

		R(j,0,17)

			fa[i][j] = i;

	}

	R(i,1,m){

		int l1, r1, l2, r2;

		io >> l1 >> r1 >> l2 >> r2;

		int t = lg[r1 - l1 + 1];

		Merge(l1, l2, t), Merge(r1 - (1 << t) + 1, r2 - (1 << t) + 1, t);

	}

	int ans = 0;

	R(i,1,n){

		ans += (Find(i, 0) == i);

	}

	printf("%lld\n", (9 * Pow(10, ans - 1) + mod) % mod);

	return 0;

}

BZOJ4569 [Scoi2016]萌萌哒（并查集，倍增）的相关教程结束。