大家好啊，我用分块水过了这道题，代码跑的甚至比 std 还快。

#include <bits/stdc++.h>
using namespace std;
const int B1 = 320, B2 = 320, C1 = B1 + 12, C2 = B2 + 12, N = 1e5 + 12;
int a[N], b[C2][N], t[C2];
void push(int c)
{
	if (!t[c]) return;
	for (int i = 0; i < B1; i++)
	{
		b[c][a[c * B1 + i]] = 0;
		a[c * B1 + i] = t[c];
	}
	b[c][t[c]] = B1;
	t[c] = 0;
}
int get(int c, int v)
{
	if (t[c] == v) return B1;
	if (t[c] && t[c] != v) return 0;
	return b[c][v];
}
void update(int x, int v)
{
	b[x / B1][a[x]]--;
	a[x] = v;
	b[x / B1][v]++;
}
int main()
{
	freopen("array.in", "r", stdin);
	freopen("array.out", "w", stdout);
	ios::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		b[i / B1][a[i]]++;
	}
	while (q--)
	{
		int z, m, x, y, l, r, v, f = 0;
		cin >> z;
		if (z == 1)
		{
			cin >> l >> r >> v;
			if (l / B1 == r / B1)
			{
				push(l / B1);
				for (int i = l; i <= r; i++)
					update(i, v);
				continue;
			}
			push(l / B1);
			for (int i = l; i < B1 * (l / B1 + 1); i++)
				update(i, v);
			for (int i = l / B1 + 1; i < r / B1; i++)
				t[i] = v;
			push(r / B1);
			for (int i = r / B1 * B1; i <= r; i++)
				update(i, v);
		}
		if (z == 2)
		{
			cin >> m;
			while (m--)
			{
				cin >> x >> y;
				if (f > n + 1) continue;
				while (f % B1)
				{
					if (a[f] == x) y--;
					f++;
					if (!y) break;
					if (f > n + 1) break;
				}
				if (!y) continue;
				while (f <= n + 1 && y > get(f / B1, x))
				{
					y -= get(f / B1, x);
					f += B1;
				}
				if (f > n + 1) continue;
				push(f / B1);
				while (y)
				{
					if (a[f] == x) y--;
					f++;
				}
			}
			if (f <= n + 1) puts("Yes");
			if (f > n + 1) puts("No");
		}
	}
	return 0;
}

考虑使用颜色段均摊技巧维护序列，然后对每个权值利用一棵动态开点权值线段树维护该权值在序列中的出现位置。对于查询操作，贪心地尽量靠左匹配原序列，维护当前匹配到的位置，对给定的每个段在对应的动态开点权值线段树上二分得到匹配完成时的位置即可。

最终的时间复杂度为 $O(n \log n + m \log n + q \log n)$，空间复杂度为 $O(n \log n + q \log n)$。

（用平衡树存储每个权值对应的颜色段来代替动态开点权值线段树，可以将空间复杂度优化到 $O(n + q)$，但可能会影响程序运行性能并增加代码编写难度。）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 12;
const int D = 17;
const int E = 1 << D;
const int F = 5 * D * N;
struct I
{
	int l;
	int r;
};
bool operator<(I x, I y)
{
	if (x.l != y.l) return x.l < y.l;
	return x.r < y.r;
}
map <I, int> segs;
struct J
{
	int a;
	int b;
	int l;
	int r;
};
struct K
{
	J v[F];
	int c;
	int add(int l, int r, int ll, int rr, int k, int b)
	{
		if (!b)
		{
			c++;
			b = c;
		}
		v[b].b += (r - l + 1) * k;
		if (l == ll && r == rr)
		{
			v[b].a += k;
			return b;
		}
		int lmid = (ll + rr) >> 1, rmid = lmid + 1;
		if (r <= lmid)
		{
			v[b].l = add(l, r, ll, lmid, k, v[b].l);
			return b;
		}
		if (l >= rmid)
		{
			v[b].r = add(l, r, rmid, rr, k, v[b].r);
			return b;
		}
		v[b].l = add(l, lmid, ll, lmid, k, v[b].l);
		v[b].r = add(rmid, r, rmid, rr, k, v[b].r);
		return b;
	}
	int get(int r, int acc, int ll, int rr, int b)
	{
		if (!r) return 0;
		if (!b) return (r - ll + 1) * acc;
		if (r == rr) return v[b].b + (rr - ll + 1) * acc;
		int lmid = (ll + rr) >> 1, rmid = lmid + 1;
		if (r <= lmid) return get(r, acc + v[b].a, ll, lmid, v[b].l);
		return get(lmid, acc + v[b].a, ll, lmid, v[b].l) + get(r, acc + v[b].a, rmid, rr, v[b].r);
	}
	int search(int k, int acc, int ll, int rr, int b)
	{
		int cur = get(rr, acc, ll, rr, b);
		if (cur < k) return cur - k;
		if (ll == rr) return rr;
		int lmid = (ll + rr) >> 1, rmid = lmid + 1, ans = search(k, acc + v[b].a, ll, lmid, v[b].l);
		if (ans < 0) ans = search(-ans, acc + v[b].a, rmid, rr, v[b].r);
		return ans;
	}
};
K w;
int main()
{
	freopen("array.in", "r", stdin);
	freopen("array.out", "w", stdout);
	ios::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	w.c = n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		w.add(i, i, 1, E, 1, x);
		segs[(I) {i, i}] = x;
	}
	while (q--)
	{
		int z, l, r, v, m, x, y;
		cin >> z;
		if (z == 1)
		{
			map <I, int> temp;
			cin >> l >> r >> v;
			map<I, int>:: iterator seg = segs.lower_bound((I) {l, 0});
			if (seg == segs.end()) seg--;
			if ((*seg).first.l > l) seg--;
			temp[(*seg).first] = (*seg).second;
			w.add((*seg).first.l, (*seg).first.r, 1, E, -1, (*seg).second);
			segs.erase(seg);
			while (1)
			{
				if (segs.empty()) break;
				map<I, int>:: iterator seg = segs.lower_bound((I) {l, 0});
				if (seg == segs.end()) break;
				if ((*seg).first.l > r) break;
				temp[(*seg).first] = (*seg).second;
				w.add((*seg).first.l, (*seg).first.r, 1, E, -1, (*seg).second);
				segs.erase(seg);
			}
			pair<I, int> t1 = (*(temp.begin()));
			if (t1.first.l < l)
			{
				segs[(I) {t1.first.l, l - 1}] = t1.second;
				w.add(t1.first.l, l - 1, 1, E, 1, t1.second);
			}
			pair<I, int> t2 = (*(temp.rbegin()));
			if (t2.first.r > r)
			{
				segs[(I) {r + 1, t2.first.r}] = t2.second;
				w.add(r + 1, t2.first.r, 1, E, 1, t2.second);
			}
			segs[(I) {l, r}] = v;
			w.add(l, r, 1, E, 1, v);
		}
		if (z == 2)
		{
			cin >> m;
			int cur = 1;
			for (int i = 1; i <= m; i++)
			{
				cin >> x >> y;
				if (cur == n + 2) continue;
				cur = w.search(w.get(cur - 1, 0, 1, E, x) + y, 0, 1, E, x) + 1;
				if (cur <= 0) cur = n + 2;
			}
			if (cur == n + 2)
			{
				puts("No");
				continue;
			}
			puts("Yes");
		}
	}
	return 0;
}