[bzoj 3207] 花神的嘲讽计划I

题意: 一个长度为N的序列, 一个定值K, 和M个询问, 每次询问位置[x, y]是否有某个长度为K的子串, 是则回答"No", 否则回答"Yes". (N ≤ 2*10^5, 序列中数的大小不超过N) 这是一道没有数据范围的题, 尽管 "题中所有数据不超过2*10^9" QwQ 在Po姐的博客里找到上述范围.

如果没有限制定值K, 这是区间子串查询问题, 鏼爷在WC上讲了 (虽然并没有懂), 涉及字符串中一系列很妙的理论.

如果限制了K, 哈希一下, 转换成 "区间内是否存在某个数", 建可持久化权值线段树解决.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef unsigned long long ull;
const int MAX_N = 2e5, X = 2e5 + 3, NLG_N = 18;
int top;
ull H[MAX_N + 1], h[MAX_N*2], a[MAX_N + 1], x[MAX_N];

struct Node {
	Node* lc, * rc;
	int s;
} nodes[MAX_N*(NLG_N + 1) + 1], * nil = nodes, * root[MAX_N + 1] = {nil};

struct Query {
	int x, y;
	ull s;
} Q[MAX_N];

inline void init()
{
	*nil = (Node){nil, nil, 0};
}

inline Node* new_node(const Node& v)
{
	static Node* cur = nodes + 1;
	*cur = v;
	return cur++;
}

void insert(Node* &o, Node* p, int v, int l, int r)
{
	o = new_node(*p);
	if (r-l > 1) {
		int m = (l+r)/2;
		if (v < m)
			insert(o->lc, p->lc, v, l, m);
		else
			insert(o->rc, p->rc, v, m, r);
	}
	++o->s;
}

bool query(Node* o, Node* p, int v, int l, int r)
{
	if (r-l == 1) return o->s - p->s;
	int m = (l+r)/2;
	return v < m ? query(o->lc, p->lc, v, l, m) : query(o->rc, p->rc, v, m, r);
}

inline int id(ull x)
{
	return lower_bound(h, h+top, x) - h;
}

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);

	x[0] = 1;
	For (i, 1, n-1)
		x[i] = x[i-1] * X;
	
	For (i, 1, n)
		scanf("%llu", &a[i]);
	
	Rep (i, 0, m) {
		scanf("%d%d", &Q[i].x, &Q[i].y);
		Rep (j, 0, k) {
			int b;
			scanf("%d", &b);
			Q[i].s += b * x[j];
		}
		h[top++] = Q[i].s;
	}
	
	H[n] = a[n];
	Down (i, n-1, 1)
		H[i] = H[i+1]*X + a[i];

	For (i, 1, n-k+1)
		h[top++] = a[i] = H[i] - H[i+k]*x[k];
	
	sort(h, h+top);
	top = unique(h, h+top) - h;

	init();
	For (i, 1, n-k+1)
		insert(root[i], root[i-1], id(a[i]), 0, top);

	Rep (i, 0, m) {
		if (Q[i].y-Q[i].x+1 < k)
			puts("YES");
		else // [x, y-k+1]
			puts(query(root[Q[i].y-k+1], root[Q[i].x-1], id(Q[i].s), 0, top) ? "No" : "Yes");
	}
	return 0;
}