[Luogu p3295] mengmengda (parallel search) (double)

adorable

Topic link ：luogu P3295

The main idea of the topic

Give you a big number , Then there are some restrictions if we treat this number as a string , Several pairs of substrings with the same length are the same .
Then ask how many numbers you have meet the conditions .

Ideas

It can be found that it has nothing to do with numbers , The only thing is that the first one cannot be $0$.
Then you will find that both positions are the same number , Then you consider how many numbers are irrelevant , If it is $num$, The answer is $9\ast 10^{num-1}$.

Then violence merges one by one $n^2$ Of , But the inquiry is just $n$, Let's consider whether we can neutralize .
First consider how to turn the operation into $\log n$, It's not difficult to think that it can be disassembled into $\log n$ Intervals , You can multiply it or put it on the line segment tree .
But because you have to correspond one by one , You don't look very good on the tree .

Then we consider using the method of multiplication , Then look at the inquiry .
We find that we get and search the set inside the doubled block , Each point of it can be disassembled and multiplied by two , But it can't be connected with all the points in the search set .
I found it redundant , Let's think about efficiency , Observing you and looking up sets are actually connected in the form of trees , We can connect with our father directly .
（ Take apart the two sides and connect the two sides separately ）

Then you can .

Code

#include<cstdio>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 1e5 + 100;
int n, m, fa[21][N];

ll ksm(ll x, ll y) {
    
	ll re = 1; while (y) {
    if (y & 1) re = re * x % mo; x = x * x % mo; y >>= 1;} return re;
}

int find(int now) {
    return fa[(now - 1) / n][now - (now - 1) / n * n] == now ? now : fa[(now - 1) / n][now - (now - 1) / n * n] = find(fa[(now - 1) / n][now - (now - 1) / n * n]);}
void merge(int x, int y) {
    
	int X = find(x), Y = find(y); if (X != Y) fa[(X - 1) / n][X - (X - 1) / n * n] = Y;
}

int main() {
    
	scanf("%d %d", &n, &m);
	for (int i = 0; i <= 20; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
		fa[i][j] = i * n + j;
	for (int i = 1; i <= m; i++) {
    
		int l1, r1, l2, r2; scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
		for (int j = 20; j >= 0; j--)
			if (l1 + (1 << j) - 1 <= r1) {
    
				merge(j * n + l1, j * n + l2);
				l1 = l1 + (1 << j); l2 = l2 + (1 << j);
			}
	}
	
	for (int i = 20; i > 0; i--)
		for (int j = 1; j + (1 << i) - 1 <= n; j++) {
    
			if (fa[i][j] != i * n + j) {
    
				int fi = (fa[i][j] - 1) / n, fj = fa[i][j] - fi * n;
				merge((i - 1) * n + j, (fi - 1) * n + fj);
				merge((i - 1) * n + j + (1 << (i - 1)), (fi - 1) * n + fj + (1 << (fi - 1)));
			}
		}
	
	int num = 0;
	for (int i = 1; i <= n; i++) {
    
		if (fa[0][i] == i) num++;
	}
	printf("%lld", 9ll * ksm(10, num - 1) % mo);
	
	return 0;
}