#### Nhận xét:
1. Do có tối đa $10^5$ giá trị phân biệt, nên ta sẽ gán cho mỗi số một giá trị $xor$ bất kì, với tỉ lệ sai là $\approx 1e-14$. Để làm vậy, bạn có thể sử dụng hàm `mt19937`. Khi đó, 2 tập giá trị được coi là tương đương nhau khi tổng $xor$ của chúng bằng nhau.
2. Một dãy con $a[l...r]$ thỏa mãn yêu cầu chỉ chứa các giá trị liên tiếp không lặp khi và chỉ khi dãy con này đắp ứng được cả 2 điều kiện sau:
- *ĐK1*. $max(a[l...r]) - min(a[l...r]) + 1 = r - l + 1$;
- *ĐK2*. $a[l] xor ... xor a[r] = min(a[l...r]) xor ... xor max(a[l...r])$.
- Để kiểm tra điều kiện 1, ta có thể sử dụng các cấu trúc dữ liệu như IT hay bảng thưa, còn để kiểm tra điều kiện 2, sau khi gán một giá trị tùy ý cho mỗi số, ta sẽ dựng mảng $xor$ tiền tố, cho mảng $a$ và dãy số $[1...n]$, và so sánh trong $O(1)$.
#### Code mẫu:
```cpp
//author: kaoruko
#include<bits/stdc++.h>
#define int long long
#define vi vector <int>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fu(i, a, b) for(int i = (a); i < (b); i++)
#define fub(i, a, b) for(int i = (a); i <= (b); i++)
#define fd(i, a, b) for(int i = (a); i > (b); i--)
#define fdb(i, a, b) for(int i = (a); i >= (b); i--)
#define pii pair<int, int>
#define PI acos(-1)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int lim = 1e18;
const int N = 2e5 + 5;
const int M = 1e9 + 7;
const int BASE = 257;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
int n, q, a[N], st[4*N], mn[4*N], xr[N], pf[N];
void init(int n){
xr[0] = 1;
fub(i, 1, n)xr[i] = rand(2, lim);
fub(i, 1, n)pf[i] = pf[i-1]^xr[i];
}
void update(int id, int l, int r, int i, int val){
if(i < l or r < i)return;
if(l == r){
st[id] = xr[val]; mn[id] = val;
return;
}
int mid = (l + r) >> 1;
update(2*id, l, mid, i, val);
update(2*id + 1, mid + 1, r, i, val);
st[id] = st[2*id]^st[2*id + 1];
mn[id] = min(mn[2*id], mn[2*id + 1]);
}
int get(int id, int l, int r, int u, int v, int ty){
if(v < l or r < u){
if(ty)return 0;
return lim;
}
if(u <= l and r <= v){
if(ty)return st[id];
return mn[id];
}
int mid = (l + r) >> 1;
int gta = get(2*id, l, mid, u, v, ty), gtb = get(2*id + 1, mid + 1, r, u, v, ty);
if(ty)return (gta^gtb);
return min(gta, gtb);
}
signed main(){
fastio;
cin >> n >> q;
init(n);
fub(i, 1, n){
cin >> a[i];
update(1, 1, n, i, a[i]);
}
while(q--){
int x, y; cin >> x >> y;
int gta = get(1, 1, n, x, y, 0), gtb = get(1, 1, n, x, y, 1);
if(gtb == (pf[y - x + gta]^pf[gta - 1]))cout << "YES\n";
else cout << "NO\n";
}
}
nihahaha
Created at
1 likes