QwQ有点有趣

明显，平衡树可以秒这道题

但是总是感觉太烦了。

有没有好一点的方法呢？

如果我们考虑每一个数，如果没有向后送，向前移的位置数等于前面比它大的数，显然这可以用树状数组搞。

而剩下的数相对顺序一定排好了

所以把剩下的数sort一下填进去就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

#define MN 200005
#define lb(x) ((x)&(-x))
#define ft first
#define sd second
#define pii pair<int,int>

int c[MN],res[MN],b[MN],n,k;
pii a[MN];

int add(int x,int y){
	for(;x<=n;x+=lb(x))c[x]+=y;
}

bool C(pii A,pii B){
	return A.sd<B.sd;
}

int qry(int x){
	int res=0;
	for(;x;x-=lb(x))res+=c[x];
	return res;
}

priority_queue<int> pQ;

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].ft);
		a[i].sd=i;
	}
	sort(a+1,a+n+1);
	for(int i=n;i;--i){
		b[a[i].sd]=qry(a[i].sd);
		add(a[i].sd,1);
		if(b[a[i].sd]>k)res[a[i].sd-k]=a[i].ft;
		else pQ.push(a[i].ft);
	}
	for(int i=n;i;--i){
		if(!res[i])res[i]=pQ.top(),pQ.pop();
	}
	for(int i=1;i<=n;++i)printf("%d\n",res[i]);
	return 0;
}

最后更新： 2019年01月14日 18:47

原始链接： http://tenecnt.github.io/2018/07/24/bzoj5170/