HDU 5592 ZYB's Premutation
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5592
题意：
http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=654&pid=1003
题解：
对给的n个数做差分，即a[i]=a[i]-a[i-1]，然后对做完差分之后的数组从后往前扫一遍（最后一个数就是代表整个序列中比它大的数有a[n-1]个，即，它是第a[n-1]+1大的数），每次求还未求出的数中的第（a[i]+1）大(第1大就是最大的意思)。
代码：
线段树：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define lson (o<<1) 5 #define rson ((o<<1)|1) 6 #define M (l+(r-l)/2) 7 using namespace std; 8 9 const int maxn=50000+10; 10 11 int n,arr[maxn],ans[maxn]; 12 13 int sumv[maxn<<2]; 14 15 void build(int o,int l,int r){ 16 if(l==r){ 17 sumv[o]=1; 18 }else{ 19 build(lson,l,M); 20 build(rson,M+1,r); 21 sumv[o]=sumv[lson]+sumv[rson]; 22 } 23 } 24 25 int _ret; 26 void query(int o,int l,int r,int k){ 27 if(l==r){ 28 _ret=l; 29 sumv[o]=0; 30 }else{ 31 if(sumv[rson]>=k) query(rson,M+1,r,k); 32 else query(lson,l,M,k-sumv[rson]); 33 sumv[o]=sumv[lson]+sumv[rson]; 34 } 35 } 36 37 int main(){ 38 int tc; 39 scanf("%d",&tc); 40 while(tc--){ 41 scanf("%d",&n); 42 build(1,1,n); 43 for(int i=0;i<n;i++) scanf("%d",arr+i); 44 for(int i=n-1;i>0;i--) arr[i]-=arr[i-1]; 45 for(int i=n-1;i>=0;i--){ 46 query(1,1,n,arr[i]+1); 47 ans[i]=_ret; 48 } 49 for(int i=0;i<n-1;i++) printf("%d ",ans[i]); 50 printf("%d ",ans[n-1]); 51 } 52 return 0; 53 }
二分+树状数组：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M (low+(hig-low)/2) 6 using namespace std; 7 8 const int maxn=50000+10; 9 10 int n,arr[maxn],ans[maxn]; 11 12 int sumv[maxn]; 13 14 void add(int p,int x){ 15 while(p<=n){ 16 sumv[p]+=x; 17 p+=p&(-p); 18 } 19 } 20 21 int sum(int p){ 22 int ret=0; 23 while(p>0){ 24 ret+=sumv[p]; 25 p-=p&(-p); 26 } 27 return ret; 28 } 29 //lower_bound 30 int solve(int k){ 31 int low=0,hig=n; 32 while(low+1<hig){ 33 if(sum(M)<k) low=M; 34 else hig=M; 35 } 36 add(hig,-1); 37 return hig; 38 } 39 40 void init(){ 41 memset(sumv,0,sizeof(sumv)); 42 } 43 44 int main(){ 45 int tc; 46 scanf("%d",&tc); 47 while(tc--){ 48 scanf("%d",&n); 49 init(); 50 for(int i=1;i<=n;i++) add(i,1); 51 for(int i=0;i<n;i++) scanf("%d",arr+i); 52 for(int i=n-1;i>0;i--) arr[i]-=arr[i-1]; 53 for(int i=n-1;i>=0;i--){ 54 ans[i]=solve(i+1-arr[i]); 55 } 56 for(int i=0;i<n-1;i++) printf("%d ",ans[i]); 57 printf("%d ",ans[n-1]); 58 } 59 return 0; 60 }