AtCoder AGC001F Wide Swap (线段树、拓扑排序)

题目链接: https://atcoder.jp/contests/agc001/tasks/agc001_f

题解: 先变成排列的逆，要求\(1\)的位置最小，其次\(2\)的位置最小，依次排下去(称之为逆字典序)。有一些条件，如果两数\(x,y\)的差小于\(K\), 那么它们的相对位置不可变。

所以如果从必须在前面的往必须在后面的连边，得到的图将是一个DAG，现在需要求它的一个拓扑序满足上面的最优化条件。

先排除几个错误结论: 翻转后字典序越大，字典序越小，错误。逆字典序越大，字典序越大/越小，错误。

有这样一个正确结论: 逆字典序最小的拓扑序即为翻转后字典序最大的拓扑序。注意必须是在一个图的拓扑序的集合中，不可拓展到任意排列的集合中，而且是“最大”“最小”，不可拓展为“越大”“越小”。

对于这个结论，网上好多感性理解/证明都是明显有问题的。我给出一个我自己的证明: (可能有错，有错请指出) 考虑归纳，假设往图里添加一个新的点\(n\), 假设在翻转后字典序最大的拓扑序里\(n\)的位置为\(k\), 那么\(n\)一定要向位置\((k+1)\)上的数连边(否则交换它们会使得翻转后字典序更大)，即\(n\)现在所处的位置是合法情况下其所处的最靠后的位置。又因为在没加\(n\)之前该排列是逆字典序最小的，因此加了\(n\)之后会使得后面最小个数的小于\(n\)的数位置后移\(1\), 因此加了之后依然是最小。

所以我们只需要建出图来求翻转后字典序最小的拓扑序，然而边数是\(O(n^2)\)的，但是发现连边时只需要考虑区间内最小的和最大的即可。线段树优化。

时间复杂度\(O(n\log n)\)

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<utility>

#include<algorithm>

#include<queue>

#define llong long long

using namespace std;

const int N = 5e5;

struct SegmentTree

{

	struct SgTNode

	{

		int val;

	} sgt[(N<<2)+2];

	void pushup(int pos) {sgt[pos].val = max(sgt[pos<<1].val,sgt[pos<<1|1].val);}

	void modify(int pos,int le,int ri,int lrb,int val)

	{

		if(le==lrb && ri==lrb) {sgt[pos].val = val; return;}

		int mid = (le+ri)>>1;

		if(lrb<=mid) {modify(pos<<1,le,mid,lrb,val);}

		else if(lrb>mid) {modify(pos<<1|1,mid+1,ri,lrb,val);}

		pushup(pos);

	}

	int querymax(int pos,int le,int ri,int lb,int rb)

	{

		if(lb<=le && rb>=ri) {return sgt[pos].val;}

		int mid = (le+ri)>>1;

		int ret = 0;

		if(rb>mid) {ret = max(ret,querymax(pos<<1|1,mid+1,ri,lb,rb));}

		if(lb<=mid) {ret = max(ret,querymax(pos<<1,le,mid,lb,rb));}

		return ret;

	}

} smt;

struct Edge

{

	int v,nxt;

} e[(N<<1)+2];

int a[N+3];

int b[N+3];

int ind[N+3];

int fe[N+3];

priority_queue<pair<int,int> > pq;

pair<int,int> ans[N+3];

int fans[N+3];

int n,m,en;

void addedge(int u,int v)

{

//	printf("addedge%d %d\n",u,v);

	en++; e[en].v = v; ind[v]++;

	e[en].nxt = fe[u]; fe[u] = en;

}

int main()

{

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

	for(int i=1; i<=n; i++) {int x; scanf("%d",&b[i]); a[b[i]] = i;}

	for(int i=1; i<=n; i++)

	{

		ans[i].second = a[i];

		int x = smt.querymax(1,0,n,max(a[i]-m+1,0),a[i]);

		int y = smt.querymax(1,0,n,a[i],min(a[i]+m-1,n));

		if(x) {addedge(i,x);}

		if(y) {addedge(i,y);}

//		printf("iquery %d %d %d\n",i,max(0,a[i]-m+1),min(n,a[i]+m-1));

//		printf("imodify %d %d %d\n",i,ans[i].second,ans[i].first);

		smt.modify(1,0,n,ans[i].second,i);

//		printf("ans%d %d %d\n",i,ans[i].first,ans[i].second);

	}

	for(int i=1; i<=n; i++) if(ind[i]==0) {pq.push(make_pair(a[i],i));}

	int j = 0;

	while(!pq.empty())

	{

		pair<int,int> tmp = pq.top(); pq.pop();

		j++; b[j] = tmp.first; int u = tmp.second;

		for(int i=fe[u]; i; i=e[i].nxt)

		{

			ind[e[i].v]--;

			if(ind[e[i].v]==0)

			{

				pq.push(make_pair(a[e[i].v],e[i].v));

			}

		}

	}

	for(int i=1; i<n+1-i; i++) swap(b[i],b[n+1-i]);

	for(int i=1; i<=n; i++) fans[b[i]] = i;

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

	return 0;

}

巴特西

AtCoder AGC001F Wide Swap (线段树、拓扑排序)

代码

最新文章

热门文章