[SCOI2016]萌萌哒

题目描述

题面

一个长度为 \(n\) 的大数，用 \(S_1S_2S_3 \cdots S_n\)表示，其中 \(S_i\) 表示数的第 \(i\) 位, \(S_1\) 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，\(l_1,r_1,l_2,r_2\)，即两个长度相同的区间，表示子串 \(S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}\)与 \(S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}\)完全相同。

比如 \(n=6\) 时，某限制条件 \(l_1=1,r_1=3,l_2=4,r_2=6\) ，那么 \(123123\)，\(351351\) 均满足条件，但是 \(12012\)，\(131141\) 不满足条件，前者数的长度不为 \(6\) ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

数据范围

\(1\le n\le 10^5\)，\(1\le m\le 10^5\) ，$ 1\le li1,ri1,li2,ri2 \le n $ ；并且保证 $ r1_{i}-l1_{i}=r2_{i}-l2_{i} $ 。

solution

这题难想在用 ST 表优化并查集的合并过程（还是第一次见呢），感觉很好的例题，所以就跑来写题解了 /cy

\(f_{i, j}\) 表示以 \(i\) 为左端点，区间 \([i, j]\) 其中 \(i\) 已经完成合并的 \(i\) 的祖先（还是具体看代码理解吧 /kk）

合并就类似 ST 表预处理的方式正常合并就好了。

复杂度：\(O(nlog^2n)\)

code

/*Work by:Ariel_*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int mod = 1e9 + 7;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int N, M, f[MAXN][25];
int find(int x, int y) {return f[x][y] == x ? f[x][y] : f[x][y] = find(f[x][y], y);}
void merge(int x, int y, int len) {
  int fx = find(f[x][len], len), fy = find(f[y][len], len);
  f[f[fx][len]][len] = fy;
}
int main(){
  N = read(), M = read();
  for (int i = 1; i <= N; i++) 
    for (int j = 0; j <= 21; j++) f[i][j] = i;
  for (int i = 1; i <= M; i++) {
  	int l1 = read(), r1 = read(), l2 = read(), r2 = read();
  	int len = log2(r1 - l1 + 1);
	merge(l1, l2, len);
	l1 = r1 - (1 << len) + 1, l2 = r2 - (1 << len) + 1;
	merge(l1, l2, len); 
  }
  for (int len = 21; len >= 1; len--) {
  	 for (int i = 1; i + (1 << len) - 1 <= N; i++) {
  	     int fa = find(i, len);
		 if(fa == i) continue;
		 merge(i, fa, len - 1);
		 merge(i + (1 << (len - 1)), fa + (1 << (len - 1)), len - 1); 	
	  }
  }
  long long Ans = 0;
  for (int i = 1; i <= N; i++) {
  	 if(f[i][0] == i) {
  	   if(Ans == 0) Ans = 9;
	   else Ans = Ans * 10 % mod;	
	 } 
  }
  cout<<Ans;
  puts("");
  return 0;
}

原文地址：http://www.cnblogs.com/Dita/p/16914939.html