[atAGC001F]Wide Swap

结论：排列$p'_{i}$可以通过排列$p_{i}$得到当且仅当$\forall 1\le i<j<i+k,(p_{i}-p_{j})(p'_{i}-p'_{j})>0$

证明：构造$b_{p_{i}}=i$，交换即令$b_{i}$与$b_{i+1}$交换，条件为$|b_{i}-b_{i+1}|\ge k$，那么对于$x<y$的$|b_{x}-b_{y}|<k$，相对位置不会发生改变，同时其他位置可以任意交换，反映在$p'_{i}$上即$p'_{b_{x}}$和$p'_{b_{y}}$的相对大小不会改变，即得证

考虑从$n$到$1$依次填数，统计每一个位置上$cnt_{i}=\sum_{j=\max(i-k+1,1)}^{\min(i+k-1,n)}[p_{i}<p_{j}]$，然后不断找到最后一个$cnt_{i}$为0且未被填过的位置填$i$，并将其左右长度为$2k-1$的区间的$cnt_{i}$减1

先考虑贪心填$n$的正确性，由于这些位置之间的距离必然大于$k$（否则不可能同时$cnt_{i}=0$），那么当$n$填在了不是最后一个的位置，两者交换必然更优

之后的问题相当于当前问题的子问题，已经填过的位置可以看作最小的（因为已经对之前的-1），那么新的最大值$n-1,n-2,...$的填法与$n$相同

那么用线段树来维护，相当于支持：1.区间-1；2.查询最后一个0，为了方便查询，可以将填写后的$cnt_{i}$置为$\infty

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 500005

 4 #define L (k<<1)

 5 #define R (L+1)

 6 #define mid (l+r>>1)

 7 int n,k,x,a[N],cnt[N],ans[N],f[N<<3],tag[N<<3];

 8 void upd(int k,int x){

 9     tag[k]+=x;

10     f[k]+=x;

11 }

12 void down(int k){

13     upd(L,tag[k]);

14     upd(R,tag[k]);

15     tag[k]=0;

16 }

17 void update(int k,int l,int r,int x){

18     if (l==r){

19         f[k]=1;

20         return;

21     }

22     if (x<=mid)update(L,l,mid,x);

23     else update(R,mid+1,r,x);

24     f[k]=f[L]+f[R];

25 }

26 int query(int k,int l,int r,int x,int y){

27     if ((l>y)||(x>r))return 0;

28     if ((x<=l)&&(r<=y))return f[k];

29     return query(L,l,mid,x,y)+query(R,mid+1,r,x,y);

30 }

31 void update(int k,int l,int r,int x,int y,int z){

32     if ((l>y)||(x>r))return;

33     if ((x<=l)&&(r<=y)){

34         upd(k,z);

35         return;

36     }

37     down(k);

38     update(L,l,mid,x,y,z);

39     update(R,mid+1,r,x,y,z);

40     f[k]=min(f[L],f[R]);

41 }

42 int find(int k,int l,int r){

43     if (l==r)return l;

44     down(k);

45     if (!f[R])return find(R,mid+1,r);

46     return find(L,l,mid);

47 }

48 int main(){

49     scanf("%d%d",&n,&k);

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

51         scanf("%d",&x);

52         a[x]=i;

53     }

54     for(int i=n;i;i--){

55         cnt[i]=query(1,1,n,max(a[i]-k+1,1),min(a[i]+k-1,n));

56         update(1,1,n,a[i]);

57     }

58     memset(f,0,sizeof(f));

59     for(int i=1;i<=n;i++)update(1,1,n,a[i],a[i],cnt[i]);

60     for(int i=n;i;i--){

61         int l=find(1,1,n);

62         ans[l]=i;

63         update(1,1,n,l,l,0x3f3f3f3f);

64         update(1,1,n,max(l-k+1,1),min(l+k-1,n),-1);

65     }

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

67 }

巴特西

[atAGC001F]Wide Swap

最新文章

热门文章