来源：模拟赛题解。

算法 1

对于操作 2，一个经典的贪心策略是尽可能早地匹配。

假设我们当前已经匹配到了原序列的第 cur 个位置（初始为 0），下一个目标是匹配 $y$ 个数值 $x$。为了让后面的匹配更有可能成功，我们应该在 cur 之后寻找最早出现的 $y$ 个 $x$，并将 cur 更新为这第 $y$ 个 $x$ 的位置。如果找不到，则说明无法匹配。

直接按照这个写一个暴力，期望得分 13pts。

算法 2

没有修改，记录每个数字出现的下标，二分即可，期望得分 13pts。

算法 3

值域为 $2$，考虑用线段树维护区间内 1 的个数（2 的个数即为区间长度减去 1 的个数）。

要查找某位置后的第 $k$ 个 $v$，先查询该位置前的 $v$ 的数量 cnt，然后在线段树上二分查找全局第 cnt $+$ $k$ 个 $v$ 的位置。时间复杂度 $O(q \log n)$。

期望得分 19pts。

算法 4

考虑操作 1，这是典型的区间推平操作，提示我们使用 ODT 维护颜色段。

对于操作 2，我们需要处理：

• 在 ODT 进行 $\texttt{split}$ 和 $\texttt{assign}$ 时，更新颜色的分布信息。
• 给定 cur，找到数值 $x$ 在 cur 之后的第 $y$ 个出现位置。

然后这样做可以过随机数据和 $y=1$，期望得分 33pts。结合前面的算法可以拿到 78pts。

算法 5

结合 算法 4 的思路，对于每种数值 $v$ 记一个 bitset pos$_{v}$，pos$_{v,w}$ 为 1 表示 $v$ 在 $a_w$ 出现。

考虑查询，找下一个位置可以用 $\texttt{\_Find\_next}$。

考虑修改，再上一个 ODT，ODT 上加删区间对应 bitset 上的操作，只需要实现区间设为 0/1 即可，可以用位运算轻松完成，期望得分 24pts。结合前面的做法可以拿到 89pts。

算法 6

结合 算法 4 的思路，上一个 ODT 并给每种数值 $v$ 维护一棵 Treap。

• Treap 的节点存储该数值的一个连续区间 $[l, r]$。
• Treap 以区间的左端点 $l$ 为关键字进行排序。
• Treap 的每个节点维护 $\texttt{sz}$，表示该子树中所有区间包含的元素总数（即 $\sum (r - l + 1)$）。

然后就可以快速查询第 $u$ 个 Treap 第 $k$ 个元素的位置。

考虑修改，跟 算法 5 的思路相同，ODT 区间发生变动时对应 Treap 上的操作。

因为 $\sum m$ 较小，时间复杂度为 $\mathcal O((n+q+\sum m) \log n)$，可以通过本题。

你也可以写动态开点线段树，应该不会被卡。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005,M=4000005;
char B[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=B)+fread(B,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int rd(){
	int x=0;char c=GC;
	while(c<'0'||c>'9')c=GC;
	while(c>='0'&&c<='9')x=x*10+c-'0',c=GC;
	return x;
}
int ls[M],rs[M],L[M],R[M],sz[M],pr[M],tr[M],tp,tot,rt[N];
inline int nd(int l,int r){
	int u=tp?tr[tp--]:++tot;
	ls[u]=rs[u]=0;L[u]=l;R[u]=r;sz[u]=r-l+1;pr[u]=rand();
	return u;
}
inline void up(int u){sz[u]=(R[u]-L[u]+1)+sz[ls[u]]+sz[rs[u]];}
void sp(int u,int k,int&x,int&y){
	if(!u){x=y=0;return;}
	if(L[u]<k)x=u,sp(rs[u],k,rs[u],y);
	else y=u,sp(ls[u],k,x,ls[u]);
	up(u);
}
int mg(int x,int y){
	if(!x||!y)return x|y;
	if(pr[x]<pr[y]){rs[x]=mg(rs[x],y);up(x);return x;}
	else{ls[y]=mg(x,ls[y]);up(y);return y;}
}
inline void ins(int v,int l,int r){
	int x,y;sp(rt[v],l,x,y);
	rt[v]=mg(mg(x,nd(l,r)),y);
}
inline void del(int v,int l){
	int x,y,z;sp(rt[v],l,x,z);sp(z,l+1,y,z);
	if(y)tr[++tp]=y;rt[v]=mg(x,z);
}
int rk(int u,int k){
	if(!u)return 0;
	if(k<=L[u])return rk(ls[u],k);
	if(k>R[u])return sz[ls[u]]+(R[u]-L[u]+1)+rk(rs[u],k);
	return sz[ls[u]]+(k-L[u]);
}
int kth(int u,int k){
	if(!u)return-1;
	if(k<=sz[ls[u]])return kth(ls[u],k);
	k-=sz[ls[u]];
	int len=R[u]-L[u]+1;
	if(k<=len)return L[u]+k-1;
	return kth(rs[u],k-len);
}
struct Node{
	int l,r;mutable int v;
	Node(int L,int R=0,int V=0):l(L),r(R),v(V){}
	bool operator<(const Node&o)const{return l<o.l;}
};
set<Node>s;typedef set<Node>::iterator IT;
IT split(int p){
	IT it=s.lower_bound(Node(p));
	if(it!=s.end()&&it->l==p)return it;
	--it;int l=it->l,r=it->r,v=it->v;
	del(v,l);ins(v,l,p-1);ins(v,p,r);
	s.erase(it);s.insert(Node(l,p-1,v));
	return s.insert(Node(p,r,v)).first;
}
void assign(int l,int r,int v){
	IT itr=split(r+1),itl=split(l);
	for(IT it=itl;it!=itr;){del(it->v,it->l);s.erase(it++);}
	s.insert(Node(l,r,v));ins(v,l,r);
}
int qx[N];ll qy[N];
int main(){
	freopen("ds.in","r",stdin);
	freopen("ds.out","w",stdout);
	srand(19260817);
	int n=rd(),q=rd(),st=1,v=rd();
	for(int i=2,c;i<=n;++i){
		c=rd();
		if(c!=v){s.insert(Node(st,i-1,v));ins(v,st,i-1);st=i;v=c;}
	}
	s.insert(Node(st,n,v));ins(v,st,n);
	while(q--){
		int op=rd();
		if(op==1){
			int l=rd(),r=rd(),x=rd();
			assign(l,r,x);
		}else{
			int m=rd(),c=0;ll tot=0;
			for(int i=0,x,y;i<m;++i){
				x=rd();y=rd();tot+=y;
				if(c&&qx[c-1]==x)qy[c-1]+=y;
				else qx[c]=x,qy[c++]=y;
			}
			if(tot>n){puts("No");continue;}
			bool ok=1;int cur=1;
			for(int i=0;i<c;++i){
				if(qy[i]<=0)continue;
				if(!rt[qx[i]]){ok=0;break;}
				int r=rk(rt[qx[i]],cur);
				if(r+qy[i]>sz[rt[qx[i]]]){ok=0;break;}
				cur=kth(rt[qx[i]],r+qy[i])+1;
				if(cur>n+1)cur=n+1;
			}
			puts(ok?"Yes":"No");
		}
	}
	return 0;
}