[st表][贪心]Loop 2022杭电多校第6场 1012

Problem Description

You are given an array aa of length nn. You must perform exactly kk times operations.

For each operation,

\bullet∙ First, you select two integers l,rl,r ((1\leq l\leq r \leq n1≤l≤r≤n)),

\bullet∙ Second, change aa to bb, satisfy :

\ \ \ \ \circ    ∘ For each ii ((1\le i< l1≤i

\ \ \ \ \circ    ∘ For each ii ((l\le i< rl≤i

\ \ \ \ \circ    ∘ b_r=a_lbr​=al​

\ \ \ \ \circ    ∘ For each ii ((r< i\le nr

Find the lexicographically largest possible array after kk times operations.

Array xx is lexicographically greater than array yy if there exists an index ii (( 1\leq i\leq n1≤i≤n )) such that x_ixi​ >> y_iyi​ and for every j (1\leq j \lt i) ,j(1≤j

Input

The first line of the input contains one integer TT ((1\leq T\leq 1001≤T≤100 )) --- the number of test cases. Then TT test cases follow.

The first line of the test case contains two integers n,kn,k ((1\le n,k\le 3000001≤n,k≤300000))

The second line of the test case contains nn integers a_1,a_2,...,a_na1​,a2​,...,an​((1\le a_i\le 3000001≤ai​≤300000))

The sum of nn over all testcases doesn't exceed 10^{6}106.

The sum of kk over all testcases doesn't exceed 10^{6}106.

Output

For each testcase,one line contains nn integers ,a_1,a_2,...,a_na1​,a2​,...,an​ --- the lexicographically largest possible array after kk times operations.

Don‘t have spaces at the end of the line

Sample Input

2

7 3

1 4 2 1 4 2 4

5 2

4 3 5 4 5

Sample Output

4 4 2 4 2 1 1

5 4 5 4 3

题意： 给出长度为n的数组以及k次操作机会，每次操作可以选择一个区间[l, r]使区间内的点循环左移1位，问最终字典序最大的序列是什么。

分析： 选择区间[l, r]内的循环左移实际上等价于选择一个值a[i]将其拿出并放在后面任意一个位置上，贪心地想，要想字典序最大那么从前往后看每个位置都要尽可能大，所以遍历一遍数组，第i个位置能够通过小于等于k次的操作变成a[i]到a[i+k]中的某个值，显然第i个位置应该变成其中的最大值，所以这需要我们提前维护出区间最大值，这可以通过st表O(nlogn)处理出来，过程中被弹出的值用一个数组t2存下来，取到的最大值也用一个数组t1存下来，最后可以将这些弹出的值任意插入回t1，所以对t2降序排列，字典序最大也就是一个类似归并t1和t2的过程。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int f[300005][20], a[300005], n, k, ans[300005];
 
bool cmp(int x, int y){
	return x > y;
}
 
void st()
{
    for(int i = 1; i <= n; i ++) f[i][0] = a[i]; 
    for(int j = 1; j < 20; j ++) 
        for(int i = 1; i+(1<-1 <= n; i ++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//均分为两部分 
}
 
int query(int l, int r)
{
	int len = abs(r-l+1);//询问区间长度 
    int t = log(len)/log(2);//换底公式，得到以2为底的下取整对数 
    return max(f[l][t],f[r-(1<1][t]);
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		scanf("%d%d", &n, &k);
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		st();
		vector<int> temp1, temp2;
		for(int i = 1; i <= n; i++){
			int l = i, r = i+k;
			if(r > n) r = n;
			int mx = query(l, r);
			temp1.push_back(mx);
			while(a[i] != mx){
				if(!k) break;
				k--;
				temp2.push_back(a[i]);
				i++;
			}
		}
		sort(temp2.begin(), temp2.end(), cmp);
		int cnt = 0, i = 0, j = 0;
		for(; i < temp1.size() && j < temp2.size();){
			if(temp1[i] < temp2[j]){
				ans[++cnt] = temp2[j];
				j++;
			}
			else if(temp1[i] >= temp2[j]){
				ans[++cnt] = temp1[i];
				i++;
			}
		}
		while(i < temp1.size()){
			ans[++cnt] = temp1[i];
			++i;
		}
		while(j < temp2.size()){
			ans[++cnt] = temp2[j];
			++j;
		}
		printf("%d", ans[1]);
		for(int i = 2; i <= n; i++)
			printf(" %d", ans[i]);
		puts("");
	}
    return 0;
}