为什么CE啊
查看原帖
为什么CE啊
801371
Midnight_szx楼主2023/9/5 13:10
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node{
	int ls, rs;
	int si, pri, key;
}t[200005];
int cnt, root;
void build(int x) {
	t[++cnt].si = 1;
	t[cnt].ls = t[cnt].rs = 0;
	t[cnt].key = x;
	t[cnt].pri = rand();
}
void update(int u) {
	t[u].si = t[t[u].ls].si + t[t[u].rs].si + 1;
}
void split(int u, int x, int &l, int &r) {
	if(u == 0) return;
	if(t[u].key <= x) {
		l = u;
		split(t[u].rs, x, t[u].rs, r);
	}
	else {
		r = u;
		split(t[u].ls, x, l, t[u].ls);
	}
	update(u);
}
int merge(int l, int r) {
	if(l == 0 or r == 0) 
	    return l + r;
	if(t[l].pri > t[r].pri) {
		t[l].rs = merge(t[l].rs, r);
		update(l);
		return l;
	}
	else {
		t[r].ls = merge(l, t[r].ls);
		update(r);
		return r;
	}
}
void Insert(int x) {
	int l, r;
	split(root, x, l, r);
	build(x);
	root = merge(merge(l, cnt), r);
}
int kth(int u, int k) {
	if(k == t[t[u].ls].si + 1) return u;
	if(k <= t[t[u].ls].si) return kth(t[u].ls, k);
	if(k > t[t[u].ls].si) return kth(t[u].rs, k - t[t[u].ls].si - 1);
}
int n, m, x;
int a[N], flag[N];
int main() {
	std::ios::sync_with_stdio(0);
	srand(time(NULL));
	cin>>n>>m;
	for(int i = 1; i <= n; i++) 
		cin>>a[i];
	int t;
	for(int i = 1; i <= m; i++) {
		cin>>t;
		flag[t]++;
	}
	for(int i = 1; i <= n; i++) {
		Insert(a[i]);
		while(flag[i] >= 1) {
			x++;
			cout<< t[ kth(root, x) ].key <<'\n';
			flag[i]--;
		}
	}
	return 0;
}

2023/9/5 13:10
加载中...