2022.7.19 模拟赛

T1 diff

  给一个乱序的模 $m$ 之后的数组（$m$ 是质数），然后问你有没有可能将这些数还原成没有进行取模操作的状态并且要求这个数组是等差数列。

  考场上是这样想的（$x$ 是首项 $d$ 是公差）：

∑ i = 1 n a i ≡ ∑ i = 1 n ( x + ( i − 1 ) d ) ( m o d m ) ≡ n ( x − d ) + n ( n + 1 ) 2 d

i=1∑n​ai​​≡i=1∑n​(x+(i−1)d)(modm)≡n(x−d)+2n(n+1)​d​

  然后就可以 $O(n^2)$ 枚举首项和第二项（因为直接枚举公差是 $O(m)$ 的而且 $m$ 很大）然后 $O(1)$ 判断这个式子，如果是成立就当他可以并输出答案。

  但是想了想这样的正确性是错误的 甚至样例里面就有天然的 hack。

  然后很显然 $20pts$ 的暴力非常好写。似乎直接全排列都能过。

  然后是正解。

  我们因为知道 $m$ 是质数。所以我们知道一个等差数列模 $m$ 后会出现循环，而且循环节长度为 $m$。所以我们考虑一下这种解法。首先我们任意找到两个数字，记他们的差为 $kd$。$d$ 就是公差， $k$ 就是一个普通的整数，然后我们发现：

1. 如果有 $2n\le m$ ，也就是说如果我们再在这个数列后面加上 $n$ 个数，这个数列也会比 $m$ 小。我们考虑把整个数列加上刚才算出来的 $kd$，这样一来得到的新数列中就会有 $k$ 个不属于原数列的数（不会重复）。这样以来我们就能 $O(n)$ 求出 $k$。于是就可以愉快的求出 $x$ 和 $d$ 了。
2. 如果 $2n>m$，就不能用上面的方法做了。因为有可能出现 $b_i+kd=b_j，j<i$ 的情况就会有重复。不过我们可以用一种很妙的方法，求出 $a$ 模 $m$ 意义下对于 $[1,m-1]$ 的补集。这样一来补集就是一个公差仍然为 $d$ 且长度小于 $\frac{m}{2}$ 的等差数列。于是就转化成了第一种情况。

  然后就做完了。

#include
using namespace std;
#define in read() 
#define MAXN 100100

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int T = 0;
int n = 0; int m = 0;
int a[MAXN] = { 0 };
int b[MAXN] = { 0 };
int x = 0; int  len = 0;

int qp(int a, int b, int p){
	int ans = 1;
	for(; b; b >>= 1){
		if(b & 1) ans = 1ll * ans * a % p;
		a = 1ll * a * a % m;
	} return ans;
}
int inv(int a, int p) { return qp(a, p - 2, p); }

void solve(int n, int *a){
	int kd = a[1] - a[0], k = 0;
	map<int, bool> vis;
	for(int i = 0; i < n; i++) vis[a[i]] = true;
	for(int i = 0; i < n; i++)
		if(!vis.count((a[i] + kd) % m)) k++;
	int d = 1ll * kd * inv(k, m) % m;
	x = -1, len = (m - d) % m;
	for(int i = 0; i < n; i++){
		if(!vis.count((a[i] + d) % m))
			if(~x) { x = -1; break; }
			else x = a[i];
	}
}

int main(){
	// freopen("diff.in", "r", stdin);
	T = in;
	while(T--){
		m = in; n = in;
		for(int i = 0; i < n; i++) a[i] = in;
		if(n == 1 or n == m) cout << a[0] << ' ' << 1 << '\n';
		else{
			sort(a, a + n);
			if(2 * n < m) solve(n, a);
			else{
				map<int , bool> vis;
				for(int i = 0; i < n; i++) vis[a[i]] = true;
				n = 0;
				for(int i = 0; i < m; i++)
					if(!vis.count(i)) b[n++] = i;
				solve(n, b);
				if(~x) x = (x + (1ll * len * n) % m) % m;
			}
			if(~x) cout << x << ' ' << len << '\n';
			else cout << "-1\n";
		}
	}
	return 0;
} 
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

T2 pairs

  考场上打了 $40pts$。一个很简单的前缀和优化 $dp$，我们考虑从小到大一个一个加入数字，设 $f_{i,j}$ 表示加到 $i$ 时逆序对数为 $j$ 的方案数，那么就有：

$$f_{i,j}=\sum _{k=max(0,j-i+1)}^j{f}_{i-1,k}$$

  我们设 $sum=\sum _{k=j-i+1}^j{f}_{i,k}$，然后就可以 $O(n^2)$ 解决前 $40pts$ 了。

#include
using namespace std;
#define p 1000000007
#define MAXN 1010

int n = 0;
int f[MAXN][MAXN] = { 0 };

int main(){
//	freopen("pairs.in", "r", stdin);
//	freopen("pairs.out", "w", stdout);
    cin >> n;
    f[1][0] = 1;
    for (int i = 2; i <= n; i++){
        int sum = 0;
        for (int j = 0; j <= n; j++){
            sum = (sum + f[i - 1][j]) % p;
            f[i][j] = sum;
            if(j >= i - 1) sum = ((sum - f[i - 1][j - i + 1]) % p + p) % p;
        }
    }
    cout << f[n][n] << '\n';
    return 0;
}

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

  正解需要一点前置芝士qwq。

  1. 首先我们看这样一个问题，求 $\sum _{i=1}^n{x}_i=b$ 的非负整数解的个数。

  这个问题就非常简单啊，我们稍微把他转化一下，这个问题就等价于有 $n$ 个小朋友分 $b$ 个糖果，每个小朋友至少分到 $0$ 个糖果（好惨啊），求分完糖果的方案数。

  然后我们再转化一下问题，现在有 $b$ 个糖果排成一排，在其中放 $n-1$ 个木板（可以有多个木板在同一个格子里），这样就能把这些糖果分成 $n$ 部分，求方木板的方案数。

  这样就很显然了嘛，答案就是 $C_{n+b-1}^{n-1}$。

  2. 还有这样一个问题，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\ge l_i$ 的解数。显然我们非常不希望出现后面的约束条件，于是我们考虑这样：

$$\sum _{i=1}^n{x}_i=b-\sum _{i=1}^n{l}_i$$

  这样一来我们就把问题转化成了第一个问题一样的形式了（就相当于我们减掉了 $x_i<l_i$ 的贡献）。

  3. 最后一个问题，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\le r_i$ 的解的个数。这个问题就不像上一个那么好转换了。所以我么考虑容斥掉 $x_i\ge r_i+1$ 的贡献。

  我们令集合 $S$ 表示 $\sum _{i=1}^n(x_i\ge r_i+1)$ 的二进制集合。这样就相当于求 S = { 0 , 0 , ⋯   , 0 } S = \{ 0, 0, \cdots, 0 \} S={0,0,⋯,0} 的时候的答案。我们令 $f(S)$ 表示该二进制集合为 $S$ 时的答案。则有：

f ( S = { 0 , 0 , ⋯   , 0 } ) = t o t − ∑ S ⊂ U ( − 1 ) ∣ S ∣ + 1 f ( S ) f(S = \{0, 0, \cdots, 0\}) = tot - \sum_{S \subset U}(-1)^{|S| + 1}f(S) f(S={0,0,⋯,0})=tot−S⊂U∑​(−1)∣S∣+1f(S)

  其中 $tot$ 表示总数，也就是第一个问题的答案。 U = { 0 , 0 , ⋯   , 0 } U = \{ 0, 0, \cdots, 0 \} U={0,0,⋯,0} （$n$ 个 $0$）。上面这个式子就是容斥原理嘛。

  然后其中（等价于第二个问题）：

f ( S ) = ( n + b − 1 − ∑ i ∈ S ( r i + 1 ) n − 1 ) f(S) =

f(S)=(n+b−1−i∈S∑​(ri​+1)n−1​)

  于是：

a n s = ( n + b − 1 n − 1 ) − ∑ S ⊂ U ( − 1 ) ∣ S ∣ + 1 f ( S ) = ( n + b − 1 n − 1 ) + ∑ S ⊂ U ( − 1 ) ∣ S ∣ ( n + b − 1 − ∑ i ∈ S ( r i + 1 ) n − 1 ) = ∑ S ⊆ U ( − 1 ) ∣ S ∣ f ( S )

ans​=(n+b−1n−1​)−S⊂U∑​(−1)∣S∣+1f(S)=(n+b−1n−1​)+S⊂U∑​(−1)∣S∣(n+b−1−i∈S∑​(ri​+1)n−1​)=S⊆U∑​(−1)∣S∣f(S)​

  前置芝士讲完了，但是和这道题有什么关系吗？我们来回顾一下我们上面的 $dp$。我们从小到大加入每一个数，加到第 $i$ 个数的时候，可能产生的贡献是不是显然是属于 $[1,i-1]$ 这个区间的，所以我们要求的排列数也就等价于这个方程：

$$\sum _{i=1}^n{a}_i=n\wedge a_i<i$$

  的解的个数。

  这样，问题就转化成了上面我们写到的第 $3$ 个问题。根据我们上面的推到，我们可以得到这样的式子：

a n s = ∑ S ⊆ U ( − 1 ) ∣ S ∣ ( 2 n − ∑ i ∈ S i − 1 n − 1 ) ans = \sum_{S \subseteq U} (-1)^{|S|}

ans=S⊆U∑​(−1)∣S∣(2n−i∈S∑​i−1n−1​)

  其中我们令 U = { 1 , 2 , 3 , ⋯   , n } U = {\{1, 2, 3, \cdots, n\} } U={1,2,3,⋯,n}。

  然后我们考虑如何计算这个式子，我们显然不能直接枚举所有的 $S$ 集合，然后我们注意到式子的贡献只和 $|S|$ 和 $S$ 的和有关，所以我们继续考虑 $dp$。设 $d{p}_{i,j}$ 表示 $i$ 个数字和为 $j$ 的方案数，但是我们还是不知道怎样快速计算 $d{p}_{i,j}$，于是我们规定每次将所有数字加 $1$ 然后再在集合中加入数字 $1$。这样一来只需要 $O(\sqrt{n})$ 次就能使得所有数字之和达到 $n$。因此我们就能 $O(n\sqrt{n})$ 处理这个 $dp$ 了。

  每次 $dp$ 就是这样：

{ d p i , j + i + = d p i , j j + i ≤ n d p i + 1 , j + i + 1 + = d p i , j j + i + 1 ≤ n

{dpi,j+i​+=dpi,j​j+i≤ndpi+1,j+i+1​+=dpi,j​j+i+1≤n​

#include
using namespace std;
#define MAXN 100100
#define MAXM MAXN << 1
#define MOD 1000000007

int n = 0; int m = 0;
int fac[MAXM] = { 0 };           // i!
int inv[MAXM] = { 0 };
int inc[MAXM] = { 0 };           // 1 / i!
int f[505][MAXN] = { 0 };
int c[MAXN] = { 0 };

int C(int x, int y) { return 1ll * fac[x] * inc[y] % MOD * inc[x - y] % MOD; }
inline void upd(int &x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
} 

int main(){
    cin >> n;
    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    inc[0] = inc[1] = 1;
    for(int i = 2; i <= 2 * n; i++){
        fac[i] = 1ll * fac[i - 1] * i % MOD;
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
        inc[i] = 1ll * inc[i - 1] * inv[i] % MOD;
    }
    for(int i = 0; i <= n; i++) c[i] = C(i + n - 1, n - 1);
    for(m = 1; m * (m + 1) / 2 <= n; m++);
    int ans = c[n]; f[1][1] = 1;
    for(int i = 1; i < m; i++)
        for(int j = 1; j <= n; j++)
            if(f[i][j]){
                if(i & 1) upd(ans, (MOD - 1ll * f[i][j] * c[n - j] % MOD));
                else upd(ans, 1ll * f[i][j] * c[n - j] % MOD);
                if(j + i <= n) upd(f[i][j + i], f[i][j]);
                if(j + i + 1 <= n) upd(f[i + 1][j + i + 1], f[i][j]);
            }
    cout << ans << '\n';
    return 0;
}
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

T3 unicom

  前 $30pts$ 暴力建图就行了。因为题目的要求，所以边的大小是 $O(nk)$ 的，所以直接暴力 $dfs$ 就是 $O(n^{2}k)$ 就能拿 $30pts$ 了。

#include
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM MAXN << 3

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int m = 0; int k = 0;
int tot = 0;
int first[MAXN] = { 0 };
int   nxt[MAXM] = { 0 };
int    to[MAXM] = { 0 };
inline void add(int x, int y){
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int vis[MAXN] = { 0 };
void dfs(int x, int fa, int l, int r){
	vis[x] = 1;
	for(int e = first[x]; e; e = nxt[e]){
		int y = to[e];
		if(vis[y] or y < l or y > r or y == fa) continue;
		dfs(y, x, l, r);
	}
}

int main(){
	n = in; k = in; m = in;
	for(int i = 1; i <= m; i++){
		int x = in, y = in;
		add(x, y); add(y, x);
	} int q = in;
	if(k == 1)
		while(q--){
			int l = in, r = in, cnt = 0;
		}
	else if(n <= 1000){
		while(q--){
			memset(vis, 0, sizeof(vis));
			int l = in, r = in, cnt = 0;
			for(int i = l; i <= r; i++) if(!vis[i]) cnt++, dfs(i, 0, l, r);
			cout << cnt << '\n';
		}
	}
	else
		while(q--){
			int l = in, r = in;	
		}
	return 0;
}
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

  还有 $30pts$ 是 $k=1$，也就是很多链的情况。对于这一部分，我们可以预处理出每一个连通块包含哪些连续的区间，然后弄一个并查集就能比较容易的找到答案了。$60pts$ gained。

#include
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM MAXN << 3

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int m = 0; int k = 0;
int tot = 0;
int first[MAXN] = { 0 };
int   nxt[MAXM] = { 0 };
int    to[MAXM] = { 0 };
inline void add(int x, int y){
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int vis[MAXN] = { 0 };
void dfs(int x, int fa, int l, int r){
	vis[x] = 1;
	for(int e = first[x]; e; e = nxt[e]){
		int y = to[e];
		if(vis[y] or y < l or y > r or y == fa) continue;
		dfs(y, x, l, r);
	}
}

int fa[MAXN] = { 0 };
int find(int x){
	if(x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}
struct Tunion{
	int l, r;
	int idx;
}u[MAXN];

int main(){
	n = in; k = in; m = in;
	if(k == 1){
		for(int i = 1; i <= n; i++) fa[i] = i;
		for(int i = 1; i <= m; i++){
			int x = in, y = in;
			int fax = find(x), fay = find(y);
			fa[fax] = fay;
		} int q = in; int pre = 0, cnt = 1, fa1 = find(1);
//		for(int i = 1; i <= n; i++) cout << find(i) << ' '; puts("");
		u[fa1].l = 1; pre = fa1; u[fa1].idx = 1;
		for(int i = 2; i <= n; i++){
			int fai = find(i); 
//			printf("i = %d pre = %d fai = %d\n", i, pre, fai);
			if(fai != pre){
//				printf("    i = %d\n", i); 
				u[pre].idx = cnt++, u[pre].r = i - 1, u[fai].l = i, pre = fai;
			}
			else ;
		} u[pre].idx = cnt;
//		for(int i = 1; i <= n; i++) cout << u[i].idx << ' '; puts("");
		while(q--){
			int l = in, r = in, cnt = 0;
			int fal = find(l), far = find(r);
			int a = u[fal].idx, b = u[far].idx;
//			printf("l = %d r = %d \nfal = %d far = %d \na = %d b = %d \n", l, r, fal, far, a, b);
			cout << b - a + 1 << '\n';
		}
	}
	else if(n <= 1000){
		for(int i = 1; i <= m; i++){
			int x = in, y = in;
			add(x, y); add(y, x);
		} int q = in;
		while(q--){
			memset(vis, 0, sizeof(vis));
			int l = in, r = in, cnt = 0;
			for(int i = l; i <= r; i++) if(!vis[i]) cnt++, dfs(i, 0, l, r);
			cout << cnt << '\n';
		}
	}
	else{
		for(int i = 1; i <= m; i++){
			int x = in, y = in;
			add(x, y); add(y, x);
		} int q = in;
		while(q--){
			int l = in, r = in;	
		}
	}
	return 0;
}
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

  正解没看懂 qwq。

T4 similar

  很显然的 $30pts$。直接 $O(n^2\log n)$ 暴力搞。

#include
using namespace std;
#define in read()
#define MAXN 100100

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int q = 0;
int a1[MAXN] = { 0 };
int a2[MAXN] = { 0 };
int arr[MAXN] = { 0 };

int main(){
	n = in; q = in;
	for(int i = 1; i <= n; i++) arr[i] = in;
	while(q--){
		int a = in, b = in, c = in, d = in;
		for(int i = a; i <= b; i++) a1[i - a + 1] = arr[i];
		for(int i = c; i <= d; i++) a2[i - c + 1] = arr[i];
		int cnt = 0, len = b - a + 1; 
		sort(a1 + 1, a1 + len + 1); sort(a2 + 1, a2 + len + 1);
		for(int i = 1; i <= len; i++) if(a1[i] != a2[i]) cnt++;
		cnt <= 1 ? cout << "YES\n" : cout << "NO\n"; 
	}
	return 0;
} 
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

  还有 $30pts$ 是 $a_i<100$ 的时候。这个时候我们可以考虑转化问题，我们可以想到因为 $a_i$ 比较小，所以如果我们把数组变成一个桶就能大大减少比较时间。但是我们如何快速得到一个区间内的痛呢。我们可以对于每一个位置的 $a_i$ 我们在这个位置上存一个前缀的桶，这样我们只需要把右端点的痛减去左端点减一的桶就能得到区间内的桶了（和前缀和差不多 前缀桶）。

  现在我们考虑怎样才算是两个桶相似。显然相似就要满足桶内所有数字相等或者只有两个数字不同且这两个数字之间的数都没有出现在桶里面。这样每次比较的时间就是桶的大小，时间复杂度是 $O(100n)$。

#include
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM 101 

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int q = 0;
int a1[MAXN] = { 0 };
int a2[MAXN] = { 0 };
int arr[MAXN] = { 0 };
int tong1[MAXM] = { 0 };
int tong2[MAXN] = { 0 };
struct Tong{
	int t[MAXM];
}T[MAXN];

int main(){
	n = in; q = in; int f = 1, m = 100;
	for(int i = 1; i <= n; i++){
		arr[i] = in;
		if(arr[i] > 100) f = 0;
	}
	if(!f)
		while(q--){
			int a = in, b = in, c = in, d = in;
			for(int i = a; i <= b; i++) a1[i - a + 1] = arr[i];
			for(int i = c; i <= d; i++) a2[i - c + 1] = arr[i];
			int cnt = 0, len = b - a + 1; 
			sort(a1 + 1, a1 + len + 1); sort(a2 + 1, a2 + len + 1);
			for(int i = 1; i <= len; i++) if(a1[i] != a2[i]) cnt++;
			cnt <= 1 ? cout << "YES\n" : cout << "NO\n"; 
		}
	else{
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++) T[i].t[j] = T[i - 1].t[j];
			T[i].t[arr[i]]++;
		}
		while(q--){
			int a = in, b = in, c = in, d = in;
//			printf("a = %d b = %d c = %d d = %d\n", a, b, c, d);
			for(int i = 1; i <= m; i++) tong1[i] = T[b].t[i] - T[a - 1].t[i];
			for(int i = 1; i <= m; i++) tong2[i] = T[d].t[i] - T[c - 1].t[i];
//			cout << "tong1 : "; for(int i = 1; i <= 5; i++) cout << tong1[i] << ' '; puts("");
//			cout << "tong2 : "; for(int i = 1; i <= 5; i++) cout << tong2[i] << ' '; puts("");
			int f1 = 1, f2 = 1, temp = 0, s = 0, e = 0;
			for(int i = 1; i <= m; i++)
				if(tong1[i] != tong2[i]){
					f1 = 0;
					if(temp == 0) s = i, temp++;
					else if(temp == 1) e = i, temp++;
					else if(temp >= 2) f2 = 0;
				}
			for(int i = s + 1; i <= e - 1; i++) if(tong1[i] or tong2[i]) f2 = 0;
			f1 or f2 ? cout << "YES\n" : cout << "NO\n";
		}
	}
	return 0;
} 
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

  现在来看看正解。受60分的做法启发，我们希望可以找到两个区间对应的桶以及对应的数字数目不同的位置。我们可以对值域线段树做可持久化来得到我们所需要的桶。对于找到数目不同的数字。我们可以使用哈希进行判断。

  做法就是对于每一个数字 $a_i$ ，我们赋予它一个哈希值 $v_i$ 。按编号从小到大对于 $a_i$ 建立可持久化值域线段
树，线段树上的每一个节点维护对应值域区间的桶的哈希值。通过可持久化线段树上的二分来找到第一个和最后一个不同的位置，随后判断中间值域的桶哈希值是否相同即可。时间复杂度为 $O(n\log n)$。

//std
#include 
#define ll long long
#define INF 1000000000
#define INF2 2000000000000000000
 
using namespace std;

const int N = 1e5 + 5;
const int LOGN = 30;
const int P = 1e5 + 7;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 21;

int A[N], root[N], L[N * LOGN], R[N * LOGN];
int pw1[N], pw2[N];
int tree1[N * LOGN], tree2[N * LOGN];
int id = 0;
int n, q;

inline void copyNode(const int &dest, const int &src) {
    tree1[dest] = tree1[src];
    tree2[dest] = tree2[src];
    L[dest] = L[src];
    R[dest] = R[src];
}

int power(int x, int y, int mod) {
    if(y == 0)
        return 1;
    int a = power(x, y/2, mod);
    a = (1LL * a * a)%mod;
    if(y%2)
        a = (1LL * a * x)%mod;
    return a;
}

int create(int start, int end) {
    int node = ++id;
    if(start == end)
        tree1[node] = tree2[node] = L[node] = R[node] = 0;
    else {
        int mid = (start + end)/2;
        L[node] = create(start, mid);
        R[node] = create(mid + 1, end);
        tree1[node] = tree2[node] = 0;
    }
    return node;
}

int update(int node, int start, int end, int idx, int val) {
    int newNode = ++id;
    copyNode(newNode, node);
    node = newNode;
    if(start == end) {
        tree1[node] += val;
        tree2[node] += val;
        return node;
    }
    int mid = (start + end)/2;
    if(start <= idx && idx <= mid)
        L[node] = update(L[node], start, mid, idx, val);
    else
        R[node] = update(R[node], mid + 1, end, idx, val);
    tree1[node] = (1LL * tree1[L[node]] + 1LL * pw1[mid - start + 1] * tree1[R[node]])%MOD1;
    tree2[node] = (1LL * tree2[L[node]] + 1LL * pw2[mid - start + 1] * tree2[R[node]])%MOD2;
    return node;
}

bool check(int node1L, int node1R, int node2L, int node2R) {
    if(node1L == 0)
        return true;
    int val1 = tree1[node1R] - tree1[node1L];
    if(val1 < 0)
        val1 += MOD1;
    int val2 = tree1[node2R] - tree1[node2L];
    if(val2 < 0)
        val2 += MOD1;
    int val3 = tree2[node1R] - tree2[node1L];
    if(val3 < 0)
        val3 += MOD2;
    int val4 = tree2[node2R] - tree2[node2L];
    if(val4 < 0)
        val4 += MOD2;
    return (val1 == val2 && val3 == val4);
}

int query2(int node1L, int node1R, int node2L, int node2R, const int &dir) {
    if(!L[node1L] && !R[node1L]) {
        int val1 = tree1[node1R] - tree1[node1L];
        if(val1 < 0)
            val1 += MOD1;

        int val2 = tree1[node2R] - tree1[node2L];
        if(val2 < 0)
            val2 += MOD1;
        return (val1 - val2);
    }
    bool lVal = check(L[node1L], L[node1R], L[node2L], L[node2R]);
    bool rVal = check(R[node1L], R[node1R], R[node2L], R[node2R]);
    if(!lVal && !rVal)
        return INF;
    if(!lVal && dir && (((tree1[R[node1R]] - tree1[R[node1L]] + MOD1)%MOD1) || ((tree2[R[node1R]] - tree2[R[node1L]] + MOD2)%MOD2)))
        return INF;
    if(!rVal && !dir && (((tree1[L[node1R]] - tree1[L[node1L]] + MOD1)%MOD1) || ((tree2[L[node1R]] - tree2[L[node1L]] + MOD2)%MOD2)))
        return INF;
    if(!lVal)
        return query2(L[node1L], L[node1R], L[node2L], L[node2R], dir);
    else if(!rVal)
        return query2(R[node1L], R[node1R], R[node2L], R[node2R], dir);
    return 0;
}

bool query(int node1L, int node1R, int node2L, int node2R, int start, int end) {
    bool lVal = check(L[node1L], L[node1R], L[node2L], L[node2R]);
    bool rVal = check(R[node1L], R[node1R], R[node2L], R[node2R]);
    int mid = (start + end)/2;
    if(!lVal && !rVal) {
        int a = query2(L[node1L], L[node1R], L[node2L], L[node2R], 1);
        int b = query2(R[node1L], R[node1R], R[node2L], R[node2R], 0);
        return (abs(a) == 1 && a + b == 0);
    }
    else if(!lVal) {
        return query(L[node1L], L[node1R], L[node2L], L[node2R], start, mid);
    }
    else if(!rVal) {
        return query(R[node1L], R[node1R], R[node2L], R[node2R], mid + 1, end);
    }
    return true;
}



int main() {
    int t;
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i <= 100000; i++) {
        pw1[i] = (1LL * pw1[i - 1] * P)%MOD1;
        pw2[i] = (1LL * pw2[i - 1] * P)%MOD2;
    }
    cin >> n >> q;
    id = 0;
    for(int i = 1; i <= n; i++)
        cin >> A[i];
    root[0] = create(1, N);
    for(int i = 1; i <= n; i++)
        root[i] = update(root[i - 1], 1, N, A[i], 1);
    while(q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(query(root[l1 - 1], root[r1], root[l2 - 1], root[r2], 1, N))
            cout << "YES\n";
    	else cout << "NO\n";
    }
    return 0; 
}   
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156