AGC001F - Wide Swap

Description

给你一个长度为$n$的排列，每次可以交换$|i-j|\geq K$并且$|a_i-a_j|=1$的数对，问你经过若干次变换后最小字典序的排列是啥

Solution

对$a$做一个变换，令$b_{a_i}=i$，$b$数组的意思就是$i$在哪个位置

那么问题就转化成

你可以交换相邻的$|b_i-b_{i+1}|\geq K$的数对

这个时候很多人都说只要令$b$的字典序最小就可以了，但我感觉不是很对..

毕竟$b$字典序小和$a$字典序小没有什么关系啊..

再想一想上面条件的意义

如果$|b_i-b_j|<K$，那么这两个数的相对顺序是不会变的

转化到$a$上就是

对于$i$位置，$(i-K,i+K)$的数和$a_i$的相对大小是不会变的

现在我们考虑从大到小填数（从小到大也是同样的道理，没有什么区别）

那么它会有若干个位置可以填数，这些位置$i$肯定都满足 $(i-K,i+K)$中的位置已经被填了或者数比它要小

那么每$K$个位置肯定最多只有一个位置是可以填数的

我们把这$n$个位置分成每$K$个一段

每次填数之后也只会影响到 上一段、这一段、后一段 产生新的填数位置

然后这个问题就迎刃而解了..

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int Maxn = 500010;

int n, K;

int a[Maxn], ans[Maxn];

vector <int> vec[Maxn]; int no[Maxn]; bool v[Maxn];

int mx[Maxn<<2];

bool cmp(int x, int y) { return a[x] > a[y]; }

int _max(int x, int y) { return x > y ? x : y; }

int _min(int x, int y) { return x < y ? x : y; }

priority_queue <int> q;

void build_tree(int now, int L, int R) {

	if(L < R){

		int mid = L+R>>1, lc = now<<1, rc = now<<1|1;

		build_tree(lc, L, mid);

		build_tree(rc, mid+1, R);

		mx[now] = _max(mx[lc], mx[rc]);

	} else mx[now] = a[L];

}

void chg(int now, int L, int R, int x) {

	if(L == R){ mx[now] = 0; return; }

	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;

	if(x <= mid) chg(lc, L, mid, x);

	else chg(rc, mid+1, R, x);

	mx[now] = _max(mx[lc], mx[rc]);

}

int qry(int now, int L, int R, int l, int r) {

	if(L == l && R == r) return mx[now];

	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;

	if(r <= mid) return qry(lc, L, mid, l, r);

	else if(l > mid) return qry(rc, mid+1, R, l, r);

	else return _max(qry(lc, L, mid, l, mid), qry(rc, mid+1, R, mid+1, r));

}

void ins(int x) {

	if(x < 0 || x > n/K || no[x] == vec[x].size() || v[x] == true) return;

	int p = vec[x][no[x]];

	if(qry(1, 1, n, _max(1,p-K+1), _min(n,p+K-1)) == a[p]){

		no[x]++; v[x] = true;

		q.push(p);

	}

}

int main() {

	int i, j, k;

	scanf("%d%d", &n, &K);

	for(i = 1; i <= n; i++) scanf("%d", &a[i]);

	build_tree(1, 1, n);

	for(i = 1; i <= n; i++) vec[i/K].push_back(i);

	for(i = 0; i <= n/K; i++) sort(vec[i].begin(), vec[i].end(), cmp);

	for(i = 0; i <= n/K; i++) ins(i);

	for(i = n; i >= 1; i--){

		int x = q.top(); q.pop();

		ans[x] = i; chg(1, 1, n, x);

		v[x/K] = false;

		ins(x/K-1); ins(x/K); ins(x/K+1);

	}

	for(i = 1; i <= n; i++) printf("%d\n", ans[i]);

	return 0;

}

Something More

转换很妙

分段很妙

需要学的东西还有很多

巴特西

AGC001F - Wide Swap

Description

Solution

Code

Something More

最新文章

热门文章