hdu 5592 ZYB's Premutation经典线段树

传送门：hdu 5592 ZYB’s Premutation

题目大意

给出N个数，第i个表示前i个有多少个逆序数，求出原序列

解题思路

非常经典的线段树求关于逆序数类的题目！ 如果某个位置没有使用过，我们就设这个位置为1，如果这个位置已经被使用过了就置为0。我们用线段树维护当前区间有多少个1。 A[i+1]-A[i]是相对于A[i]位置的新增的逆序数，x=A[i+1]-A[i]+1表示还没操作的中第x大的数，我们只需要查询的时候从后向前遍历，然后查询x值，为了保证是准确大的，我们查询的时候先遍历右区间在遍历做区间，遍历左区间的时候，要把右边区间的值减去！ 为什么要从后向前遍历呢？ 因为最后一个是肯定确定的！比如说 0 1 2 3 4 5在前五个位置中只有一个比第六个位置小，因为5-4=1，第五个位置在前四个已经确定了，这样下去对应于k位置来讲，前k-1个位置已经确定了，第k个位置的数就是剩余的数中比第k位置大A[k]-A[k-1]个数，也就是第k个未知的放的必须是第A[k]-A[k-1]+1大的数！

AC代码

#include<cstdio> #include<cstring> const int MAXN = 50000 + 5; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int sum[MAXN<<2]; void pushUp(int rt) { sum[rt] = sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { sum[rt] = r-l+1; if(l==r)return ; int mid = (l+r)>>1; build(lson); build(rson); } int query(int l,int r,int rt,int pos) { if(l==r){ sum[rt] = 0; return l; } int mid = (l+r)>>1,ret; if(sum[rt<<1|1]>=pos) ret = query(rson,pos); else ret = query(lson,pos-sum[rt<<1|1]); pushUp(rt); return ret; } int main() { int T,N,A[MAXN]; int ans[MAXN]; scanf("%d",&T); while(T--) { scanf("%d",&N); build(1,N,1); A[0] = 0; for(int i=1;i<=N;i++) scanf("%d",&A[i]); for(int i=N;i>0;i--) ans[i] = query(1,N,1,A[i]-A[i-1]+1); for(int i=1;i<=N;i++) printf("%d%c",ans[i],(i==N)?'\n':' '); } return 0; }