信息合并类+ST表：CF1707E

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134982534

https://www.luogu.com.cn/problem/CF1707E

f([l1,r1]∪[l2,r2])=f(l1,r1)∪f(l2,r2)f([l_1,r_1]\cup [l_2,r_2])=f(l_1,r_1)\cup f(l_2,r_2)

f([l1,r1]∪[l2,r2])k=f(l1,r1)k∪f(l2,r2)kf([l_1,r_1]\cup [l_2,r_2])^k=f(l_1,r_1)^k\cup f(l_2,r_2)^k

因此我们倍增维护即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define M 20
//#define mo
#define N 100010
int n, m, i, j, k, T;
int f[M][N][M], g[M][N][M], l, r, Log2[N], L, R, q, a[N], len; 

int queF(int i, int l, int r) {
	int k = Log2[r-l+1]; 
	return min(f[i][l][k], f[i][r-(1<<k)+1][k]); 
}

int queG(int i, int l, int r) {
	int k = Log2[r-l+1]; 
	return max(g[i][l][k], g[i][r-(1<<k)+1][k]); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=1; i<=n; ++i) f[0][i][0]=g[0][i][0]=a[i]; 
	for(i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1; 
	for(i=1; i<=17; ++i) for(j=1; j+(1<<i)-1<=n; ++j) {
		f[0][j][i]=min(f[0][j][i-1], f[0][j+(1<<i-1)][i-1]); 
		g[0][j][i]=max(g[0][j][i-1], g[0][j+(1<<i-1)][i-1]); 
		debug("(%d %d) => [%d %d]\n", j, j+(1<<i)-1, f[0][j][i], g[0][j][i]); 
	}
	for(k=1; k<=17; ++k) for(i=0; i<=17; ++i)
		for(j=1; j+(1<<i)-1<=n; ++j) {
			f[k][j][i]=queF(k-1, f[k-1][j][i], g[k-1][j][i]); 
			g[k][j][i]=queG(k-1, f[k-1][j][i], g[k-1][j][i]); 
//			debug("[%d](%d %d) => [%d %d]\n", k, j, j+(1<<i)-1, f[k][j][i], g[k][j][i]); 
		}
	while(q--) {
		L=read(); R=read(); 
		if(L==1 && R==n) { printf("0\n"); continue; }
		int sum=0; 
		for(k=17; k>=0; --k) {
			len = Log2[R-L+1]; 
			l=min(f[k][L][len], f[k][R-(1<<len)+1][len]); 
			r=max(g[k][L][len], g[k][R-(1<<len)+1][len]); 
			if(l==1 && r==n) continue; 	
			L=l; R=r; sum+=(1<<k); 
			debug("> %d\n", sum); 
		}
		k=0; 
		len = Log2[R-L+1]; 
		l=min(f[k][L][len], f[k][R-(1<<len)+1][len]); 
		r=max(g[k][L][len], g[k][R-(1<<len)+1][len]); 
		debug("======%d\n", sum); 
		if(l!=1 || r!=n) printf("-1\n"); 
		else printf("%d\n", sum+1); 
	}
	return 0;
}