AT1984 Wide Swap

题意翻译

给出一个元素集合为\(\{1,2,\dots,N\}(1\leq N\leq 500,000)\)的排列\(P\)，当有\(i,j(1\leq i<j\leq N)\)满足\(j-i\geq K\)\((1\leq K\leq N-1)\)且\(|P_{i}-P{j}|=1\)时，可以交换\(P_{i}\)和\(P_{j}\)

求：可能排列中字典序最小的排列

输入格式：

\(N\) \(K\)

\(P_{1}\) \(P_{2}\) \(\dots\) \(P_{N}\)

---

这题目真是好思路啊。

首先，一个元素有两个属性，称为权值\(p\)和位置\(l\)，交换的过程可以定义为固定权值交换位置，或者固定位置交换权值。

发现原本题目中的条件不好操作，于是把权值和位置交换意义，那么问题就变成了：

让权值较小的尽可能呆在前面，当两个元素相邻并且权值之差不小于\(k\)时，可以交换这两个权值的位置。

我们把权值当成固有属性，拿位置去交换，那么如果两个元素的权值之差小于\(k\)，那么它们的相对位置是不会改变的，我们对这一对按原有位置连一条有向边。

对整个图都这么连，然后以\(\tt{topo}\)序为第一关键字，权值为第二关键字跑优先队列\(\tt{topo}\)排序，就可以找到转换以后的字典序了。

但是发现这样连边是\(O(n^2)\)的，过不了这个题，得想办法优化一下连边。

考虑一个点\(i\)会向之后的哪些点连边，\(\tt{Ta}\)会连接权值在\([p_i-k+1,p_i+k-1]\)内的所有边，而\(k\)是不变的。所以我们只需要连接\(\tt{Ta}\)位置上第一个大于\(\tt{Ta}\)和第一个小于\(\tt{Ta}\)的边就可以了，其余的这两个点会连上。

发现可以用线段树维护，倒序加点，对权值建树，区间查询最小位置。

复杂度：\(O(nlogn)\)

---

Code:

#include 
    
     #include 
     
      #include 
      
       #define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define lb(a) lower_bound(a)#define is(a) insert(a)#define ps(a) push(a)const int N=5e5+10;const int inf=0x3f3f3f3f;int in[N],loc[N],p[N],ans[N],tot,n,k;std::priority_queue 
       
        
         ,std::greater
         
           > q;int head[N],to[N<<1],Next[N<<1],cnt;void add(int u,int v){ to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;}#define ls id<<1#define rs id<<1|1int min(int x,int y){return x
          
           y?x:y;}int mi[N<<2];void change(int id,int l,int r,int p,int d){ if(l==r) {mi[id]=d;return;} int mid=l+r>>1; if(p<=mid) change(ls,l,mid,p,d); else change(rs,mid+1,r,p,d); mi[id]=min(mi[ls],mi[rs]);}int query(int id,int L,int R,int l,int r){ if(mi[id]==inf) return inf; if(l==L&&r==R) return mi[id]; int Mid=L+R>>1; if(r<=Mid) return query(ls,L,Mid,l,r); else if(l>Mid) return query(rs,Mid+1,R,l,r); else return min(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));}int main(){ scanf("%d%d",&n,&k); rep(i,1,n) scanf("%d",p),p[p[0]]=i; memset(mi,0x3f,sizeof(mi)); dep(i,n,1) { int loc=query(1,1,n,p[i],min(n,p[i]+k-1)); if(loc!=inf) add(p[i],p[loc]),++in[p[loc]]; loc=query(1,1,n,max(1,p[i]-k+1),p[i]); if(loc!=inf) add(p[i],p[loc]),++in[p[loc]]; change(1,1,n,p[i],i); } rep(i,1,n) if(!in[i]) q.ps(i); while(!q.empty()) { int now=q.top(); ans[now]=++tot; q.pop(); for(int i=head[now];i;i=Next[i]) { int v=to[i]; --in[v]; if(!in[v]) q.ps(v); } } rep(i,1,n) printf("%d\n",ans[i]); return 0;}
          
         
        
       
      
     
    

---

2018.10.26