这道题提醒了我：

1、交之前要删文件

2、v不要打成mn

3、maintain的位置

4、pushdown pushdown pushdown

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define rep(i,l,r) for(int i=l;i
            
             s; 29 if(k==1) return -1; 30 return k<=0?0:1; 31 } 32 inline void maintain(){ 33 s=ch[0]->s+ch[1]->s+1; 34 mn=min(v,min(ch[0]->mn,ch[1]->mn)); 35 } 36 inline void pushdown(){ 37 if(rev){ 38 rev=0; 39 ch[0]->rev^=1; 40 ch[1]->rev^=1; 41 swap(ch[0],ch[1]); 42 } 43 } 44 }; 45 void rotate(node*&o,int d) 46 { 47 node*k=o->ch[d^1]; 48 o->ch[d^1]=k->ch[d]; 49 k->ch[d]=o; 50 o->maintain();k->maintain(); 51 o=k; 52 } 53 void splay(node*&o,int k) 54 { 55 o->pushdown(); 56 int d=o->cmp(k); 57 if(d==-1) return; 58 if(d==1) k-=o->ch[0]->s+1; 59 node*p=o->ch[d]; 60 p->pushdown(); 61 int d2=p->cmp(k); 62 int k2=(d2?k-p->ch[0]->s-1:k); 63 if(d2!=-1){ 64 splay(p->ch[d2],k2); 65 d==d2?rotate(o,d^1):rotate(o->ch[d],d); 66 } 67 rotate(o,d^1); 68 } 69 struct num{ 70 int v,r; 71 inline bool operator <(const num&an)const{ 72 return (v
             
              
               ch[0]=null; 78 pt->ch[1]=null; 79 pt->v=pt->mn=k; 80 pt->rev=0; 81 pt->s=1; 82 return pt++; 83 } 84 num a[maxn]; 85 int b[maxn]; 86 node*build(int l,int r) 87 { 88 if(l>=r) return null; 89 int mid=(l+r)>>1; 90 node*o=newnode(b[mid]); 91 if(l
               
                ch[0]=build(l,mid); 92 if(mid+1
                
                 ch[1]=build(mid+1,r); 93 o->maintain(); 94 return o; 95 } 96 int cnt=0; 97 void dfs(node*o) 98 { 99 if(o==null) return;100 o->pushdown();101 dfs(o->ch[0]);102 printf("%d ",o->v);103 dfs(o->ch[1]);104 }105 int find(node*o,int k)106 { 107 o->pushdown(); 108 if(o->v==k) return o->ch[0]->s+1;109 if(o->ch[0]->mn==k) return find(o->ch[0],k);110 return find(o->ch[1],k)+o->ch[0]->s+1; 111 }112 int n,ans[maxn];113 node x[maxn],*root;114 void init()115 {116 pt=x;117 null=newnode(inf);118 null->s=0;119 root=build(0,n+2);120 }121 int main()122 { 123 n=read();124 rep(i,0,n){125 a[i].v=read();126 a[i].r=i;127 }128 sort(a,a+n);129 rep(i,0,n) b[a[i].r+1]=i+1;130 b[n+1]=inf;131 b[0]=inf;132 init();133 rep(i,1,n+1){134 splay(root,i);135 ans[i]=find(root,i);136 printf("%d",ans[i]-1);137 if(i!=n) printf(" ");138 splay(root->ch[1],ans[i]-root->ch[0]->s);139 root->ch[1]->ch[0]->rev^=1;140 } 141 return 0;142 }
                
               
              
             
            
           
          
         
        
       
      

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 486  Solved: 203

[][][]

Description

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1 < = Pi < = N），Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6

3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

HINT

 

Source