[BZOJ3207][花神的嘲讽计划Ⅰ][主席树+Hash]

题目大意：

给定一个 N<=100000 个数的序列和 M<=100000 个询问和 k ，每个询问包含k 2个数字： l,r,b[1],b[2]...b[k] ，要求输出 b[1] b[k] 在 [l,r] 中是否出现。

思路：

因为 b[1],b[2]...b[k] 是一段连续的数字，所以可以把它 Hash 成一个数然后用这个数来判断是否出现，这个数可以对 [1,INF] ( INF 实际值是unsigned long long的最大值)这个区间在 [1,N] 都开一棵可持久化线段树记录之前的版本。然后查询 Hash 值有没有出现就好了

代码：

#include <bits/stdc++.h> using namespace std; namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; bool f = 0; for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (f) x = -x; } inline void write(int x) { if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('\n'); } }; const int Maxn = 100005; typedef unsigned long long ll; int ls[Maxn * 80], rs[Maxn * 80], sum[Maxn * 80], rt[Maxn], sz; inline void insert(int x, int &y, ll l, ll r, ll pos) { y = ++sz; sum[y] = sum[x] + 1; ls[y] = ls[x], rs[y] = rs[x]; if (l == r) return ; ll mid = (l >> 1) + (r >> 1) + (l & r & 1); if (pos <= mid) insert(ls[x], ls[y], l, mid, pos); else insert(rs[x], rs[y], mid + 1, r, pos); } inline int query(int x, int y, ll l, ll r, ll pos) { if (sum[y] - sum[x] == 0) return 0; if (l == r) return 1; ll mid = (l >> 1) + (r >> 1) + (l & r & 1); if (pos <= mid) return query(ls[x], ls[y], l, mid, pos); else return query(rs[x], rs[y], mid + 1, r, pos); } int n, m, k, a[Maxn]; ll hash[Maxn], w; int main(void) { //freopen("in.txt", "r", stdin); IO::read(n), IO::read(m), IO::read(k); for (int i = 1; i <= n; i++) IO::read(a[i]); for (int i = 1; i <= n; i++) hash[i] = hash[i - 1] * 99997 + a[i]; w = 1; for (int i = 1; i <= k; i++) w *= 99997; for (int i = k; i <= n; i++) insert(rt[i - 1], rt[i], 1, ULLONG_MAX, hash[i] - hash[i - k] * w); for (int i = 1, x, y, s; i <= m; i++) { IO::read(x), IO::read(y); ll h = 0; for (int j = 1; j <= k; j++) IO::read(s), h = h * 99997 + s; if (y - x + 1 >= k && query(rt[x + k - 2], rt[y], 1, ULLONG_MAX, h)) puts("No"); else puts("Yes"); } return 0; }

完。

By g1n0st