KeyInsertion.cpp 1.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
  1. #include<stdio.h>
  2. #include<string.h>
  3. const int MaxN=265000;
  4. int f[MaxN],last[MaxN],head[MaxN],next[MaxN];
  5. int r[MaxN],p[MaxN],a[MaxN*4];
  6. bool used[MaxN];
  7. int n,m,z;
  8. void init(){
  9. //freopen("2131.in","r",stdin);
  10. //freopen("2131.out","w",stdout);
  11. scanf("%d%d",&m,&n);
  12. for(int i=0;i<m;++i)scanf("%d",&p[i]);
  13. n+=m;
  14. }
  15. inline void use(int x,int p){
  16. used[x]=true;
  17. f[x]=x;
  18. head[x]=last[p]=p;
  19. next[p]=0;
  20. }
  21. int find(int x){
  22. if(x==f[x])return x;
  23. return f[x]=find(f[x]);
  24. }
  25. void uni(int i,int j){
  26. i=find(i);
  27. j=find(j);
  28. if(i==j)return;
  29. next[last[head[j]]]=head[i];
  30. last[head[j]]=last[head[i]];
  31. f[i]=j;
  32. }
  33. void inittree(){
  34. for(z=1;z<n;z=z<<1);z<<=1;
  35. for(int i=z>>1;i<z;++i)a[i]=1;
  36. for(int i=(z>>1)-1;i;--i)a[i]=a[i+i]+a[i+i+1];
  37. }
  38. int remove(int p){
  39. int i=1;
  40. while(i<z){
  41. if(p<=a[i]){
  42. --a[i];
  43. i=i+i;
  44. }else{
  45. p-=a[i];
  46. i=i+i+1;
  47. }
  48. }
  49. return i-z+1;
  50. }
  51. void solve(){
  52. int i,j,x;
  53. for(i=1;i<=n;++i){f[i]=i-1;used[i]=false;}
  54. for(i=0;i<m;++i){
  55. if(used[p[i]]){
  56. x=find(p[i]);
  57. use(x+1,i+1);
  58. uni(x,x+1);
  59. if(used[x+2])uni(x+1,x+2);
  60. }else{
  61. use(p[i],i+1);
  62. uni(p[i],p[i]+1);
  63. if(used[p[i]-1])uni(p[i]-1,p[i]);
  64. }
  65. }
  66. inittree();
  67. memset(r,0,sizeof(r));
  68. for(i=n;i>0;--i){
  69. if(used[i]){
  70. for(j=head[find(i)];j;j=next[j])
  71. r[remove(p[j-1])]=j;
  72. while(used[i] && i)--i;
  73. }
  74. }
  75. for(i=n;i;--i)if(r[i])break;
  76. printf("%d\n",i);
  77. for(j=1;j<=i;++j){
  78. if(j>1)printf(" ");
  79. printf("%d",r[j]);
  80. }
  81. printf("\n");
  82. }
  83. int main(){
  84. init();
  85. solve();
  86. }