P12485 [Kiểm tra tập trung đội 2024] Bậc thầy PM - Giải pháp

tip

date:2025/7/17, NGÀY 11

Đây là bài T4 trong kỳ thi mô phỏng, Clonoth cũng đã đưa bài từ đội tuyển tập trung của mình vào, nhưng kỳ lạ là chỉ có một bài giải và số lượng bài nộp lên tới \(10\) bài.

Mình buộc phải chỉnh sửa bài giải pháp chính thức và đưa lên. Ý tưởng không phải của mình, hy vọng Clonoth sẽ không phát hiện.

Thực tế, bài này khó ở quá trình suy nghĩ, nếu thực sự hiểu thì code không quá khó, cây BIT và cây đoạn đều khá chuẩn (chỉ là đen), nhưng thật sự rất khó hiểu aaa. Lưu giữ bộ não, bắt đầu thôi.

Giả sử \(n,q\) cùng cấp.

Phương án 1

Xây dựng \(b\) từ \(a\) với độ phức tạp \(O(n)\).

Duyệt mảng \(a\) theo thứ tự \(i=1,2,\ldots,n\), đồng thời duy trì \(vis_i\) cho biết \(i\) đã xuất hiện trong \(b\) hay chưa. Khi \(a_i\ne 0\), đặt \(vis_i = \text{true}\); khi \(a_i=0\), khởi tạo \(b_i\) bằng giá trị \(b_p\) của vị trí \(a_p=0\) gần nhất trước đó, sau đó tăng \(b_i \gets b_i + 1\) cho đến khi \(vis_{b_i} = \text{false}\.

Độ phức tạp thời gian \(O(n^2)\), có thể giải quyết được bài con 1.

code

Mã của người yếu kém trong phòng thi.

while(q--){
	cin>>x>>k>>y; 
	a[x]=k;
	if(a[y]!=0){
		cout<<a[y]<<'\n';
		continue;
	}
	for(int j=1;j<=n;j++)
		fa[j]=j;
	for(int j=1;j<=n;j++){
		if(a[j]==-1)	continue;
		if(a[j]==0){
			int b=find(1);
			if(j==y){
				cout<<b<<'\n';
				break;
			}
			fa[find(b)]=find(b+1);
			continue;
		}
		fa[find(a[j])]=find(a[j]+1);
	}
}

Cấu trúc tập hợp rời có vai trò như vis, hợp nhất các phần tử đã xuất hiện với \(1\), đẹp hơn một chút so với \(O(n^2)\) buồn.

Phương án 2

Giải quyết bài con 2.

Lưu ý rằng tồn tại tập hợp \(S\subseteq \{1,2,…,n\}\) sao cho với mỗi \(a_x=0\) thứ \(i\) trong \(a\), \(b_x\) bằng số thứ \(i\) nhỏ nhất trong \(S\).

Khi đó \(x \in S\) tương đương với không tồn tại \(a_i=x\).

Sử dụng cấu trúc dữ liệu như cây BIT hoặc cây cân bằng để duy trì các thao tác chèn, xóa, tìm số thứ \(k\) nhỏ. Độ phức tạp \(O(n \log n)\), có thể giải quyết được bài con 2.

code

Mã từ HZ巨佬 orz:

void add(int x,int k){
	for(int i=x;i<=n;i+=i&-i)
		tr[i]+=k;
	return;
}
int qry(int x) {
	int res=0;
	while(x){
		res+=tr[x];
		x-=x&-x;
	}
	return res;
}
int K=n+1;
for(int i=1;i<=n;i++)
	if(a[i]==0){
		K=i;
		break;
	}
for(int i=1;i<=q;i++){
	if(a[x[i]]!=-1){
		cnt[a[x[i]]]--;
		if(!cnt[a[x[i]]])
			add(a[x[i]],-1);
	}
	if(k[i]!=-1){
		if(!cnt[k[i]])
			add(k[i],1);
		cnt[k[i]]++;
	}
	a[x[i]]=k[i];
	if(y[i]<K)	cout<<a[y[i]]<<'\n';
	else{
		int l=1,r=n;
		while(l<r){
			int mid=(l+r)>>1;
			if (mid-qry(mid)<y[i]-K+1)	l=mid+1;
			else	r=mid;
		}
		cout<<l<<'\n';
	}
}

Phương án 3

Giải quyết bài con 5. Ban đầu, bài toán tương đương với việc chèn các số dương vào dãy \(a\) ban đầu toàn số 0.

Dễ thấy rằng tập hợp \(S\) có tính chất như trong phương án 2 vẫn tồn tại trong trường hợp tổng quát, điều này gợi ý chúng ta nên duy trì \(S\) một cách động thay vì mảng \(b\).

Giả sử các số dương trong \(a\) là khác nhau, nếu có trùng thì chỉ giữ lại cái đầu tiên (ý nghĩa của thao tác update trong heap của mã mẫu). Định nghĩa \(pos_i\) là vị xuất hiện của \(i\).

Tại mọi thời điểm, với \(a_i\), \(a_i \notin S\) tương đương với \(b_p