2 条题解

  • 0
    @ 2026-2-5 3:10:47

    来源：模拟赛题解。

    算法 1

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

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

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

    算法 2

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

    算法 3

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

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

    期望得分 19pts。

    算法 4

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

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

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

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

    算法 5

    结合 算法 4 的思路，对于每种数值 vv 记一个 bitset posv_{v}，posv,w_{v,w} 为 1 表示 vv 在 awa_w 出现。

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

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

    算法 6

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

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

    然后就可以快速查询第 uu 个 Treap 第 kk 个元素的位置。

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

    因为 ∑m\sum m 较小，时间复杂度为 O((n+q+∑m)log⁡n)\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;
}
    • 0
      @ 2026-2-5 3:08:54

      两道题目的标准做法完全一致，因此请参见原题题解。

      #include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 12;
const int D = 19;
const int E = 1 << D;
const int F = (D + 1) * 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;
	stack <int> g;
	void collect(int b)
	{
		if (v[b].l > c && v[v[b].l].b == 0)
		{
			g.push(v[b].l);
			v[b].l = 0;
		}
		if (v[b].r > c && v[v[b].r].b == 0)
		{
			g.push(v[b].r);
			v[b].r = 0;
		}
	}
	int add(int l, int r, int ll, int rr, int k, int b)
	{
		if (!b)
		{
			b = g.top();
			g.pop();
			v[b] = (J) {0, 0, 0, 0};
		}
		v[b].b += (r - l + 1) * k;
		if (l == ll && r == rr)
		{
			v[b].a += k;
			collect(b);
			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);
			collect(b);
			return b;
		}
		if (l >= rmid)
		{
			v[b].r = add(l, r, rmid, rr, k, v[b].r);
			collect(b);
			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);
		collect(b);
		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("ds.in", "r", stdin);
	freopen("ds.out", "w", stdout);
	ios::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	w.c = n;
	for (int i = n + 1; i < F; i++)
		w.g.push(i);
	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;
}
      • 1

      [User Entry] 数据结构

      信息

      ID
      225
      时间
      2000ms
      内存
      1024MiB
      难度
      8
      标签
      递交数
      47
      已通过
      7
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      2. Source Code Modified by Sleeping Cup
      3. Worker 0, 49ms
      4. Powered by Hydro v5.0.7 Community