https://www.luogu.com.cn/article/i7ajvm8e
哈希好题。
题意
给定一个序列,每次询问给定两个长度相等的区间,问这两个区间是否只有一个数不一样。
思路
发现我们要求的信息只与数的出现次数有关,自然想到桶。那么如果有两个区间合法,那这两个区间的桶只有两个位置不同且桶内的值均相差 \(1\)。
维护每个区间的桶不太能直接做,且信息明显可差分,直接套一个主席树。
在树上二分找不同的位置进行判断即可。
如果当前区间完全相等那么不满足条件,左右都不相等的情况只能出现一次不然不合法,左右只有一个不相等递归那边不相等的即可。
代码
我的实现需要注意的细节还是挺多的。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
using ubt = unsigned long long;
const int maxN = 1e5 + 7;
int n, m, Q;
int sor[maxN];
int a[maxN], T[maxN];
const ubt Base = 13331;
ubt B[maxN];
int top[maxN], tot;
struct dat {
int l, r;
int len;
ubt H;
} t[maxN * 20];
void upd(int p) {
t[p].H = B[t[t[p].l].len] * t[t[p].r].H + t[t[p].l].H;
}
void build(int l, int r, int &p) {
p = ++tot;
t[p].len = r - l + 1;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, t[p].l);
build(mid + 1, r, t[p].r);
upd(p);
}
void insert(int &p, int w, int K, int l, int r) {
p = ++tot;
t[p] = t[w];
if (l == r) {
t[p].H = T[K];
return;
}
int mid = (l + r) >> 1;
if (K <= mid) insert(t[p].l, t[w].l, K, l, mid);
else insert(t[p].r, t[w].r, K, mid + 1, r);
upd(p);
}
ubt get(int l, int r) {
return t[r].H - t[l].H;
}
bool Flag;
bool check(int x0, int y0, int x1, int y1, int l, int r) {
auto t0 = get(x0, y0), t1 = get(x1, y1);
if (t0 == t1) return false;
if (l == r) {
auto res = abs((int)t0 - (int)t1) == 1;
return res;
}
auto L = get(t[x0].l, t[y0].l) != get(t[x1].l, t[y1].l);
auto R = get(t[x0].r, t[y0].r) != get(t[x1].r, t[y1].r);
int mid = (l + r) >> 1;
if (L && R) {
if (Flag) return false;
Flag = true;
return check(t[x0].r, t[y0].r, t[x1].r, t[y1].r, mid + 1, r)
&& check(t[x0].l, t[y0].l, t[x1].l, t[y1].l, l, mid);
}
return R ? check(t[x0].r, t[y0].r, t[x1].r, t[y1].r, mid + 1, r)
: check(t[x0].l, t[y0].l, t[x1].l, t[y1].l, l, mid);
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> Q;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
sor[i] = a[i];
sort(sor + 1, sor + n + 1);
m = unique(sor + 1, sor + n + 1) - sor - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(sor + 1, sor + m + 1, a[i]) - sor;
B[0] = 1;
for (int i = 1; i <= m; i++)
B[i] = B[i - 1] * Base;
build(1, m, top[0]);
for (int i = 1; i <= n; i++) {
T[a[i]]++;
insert(top[i], top[i - 1], a[i], 1, m);
}
while (Q--) {
int l, r, a, b;
cin >> l >> r >> a >> b;
Flag = false;
bool res = check(top[l - 1], top[r], top[a - 1], top[b], 1, m);
puts(res ? "DA" : "NE");
}
}
标签:return,Zapatak,int,题解,top,mid,题日,maxN,check
From: https://www.cnblogs.com/ccxswl/p/18540575