HDU 5592——ZYB's Premutation——————【线段树单点更新、单点查询】

ZYB's Premutation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 637    Accepted Submission(s): 301

Problem Description
ZYB has a premutation P,but he only remeber the reverse log of each prefix of the premutation,now he ask you to 
restore the premutation.

Pair (i,j)(i<j) is considered as a reverse log if Ai>Aj is matched.

 
Input
In the first line there is the number of testcases T.

For each teatcase:

In the first line there is one number N.

In the next line there are N numbers Ai,describe the number of the reverse logs of each prefix,

The input is correct.

1≤T≤5,1≤N≤50000

 
Output
For each testcase,print the ans.
 
Sample Input
1
3
0 1 2
 
Sample Output
3 1 2
 
Source
 
题目大意:给你一个长度为n的序列。给出前缀的逆序,问你原始序列是什么。
 
解题思路:首先处理出来每个数的逆序。然后从后处理,如果逆序为2,那么这个数是当前所有数中的第3大的数。那么在线段树中查找第3个为1的位置。   这是个偏想法的比较有意思的题。
 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn = 55000;
struct SegTree{
int sum;
}segs[maxn*4];
int a[maxn],ans[maxn];
void PushUp(int rt){
segs[rt].sum = segs[rt*2].sum + segs[rt*2+1].sum;
}
void buildtree(int rt,int L,int R){
if(L == R){
segs[rt].sum = 1;
return ;
}
buildtree(lson);
buildtree(rson);
PushUp(rt);
}
int query(int rt,int L,int R,int k){
if(L == R){
segs[rt].sum = 0;
return L;
}
int ret ;
if(segs[rt*2+1].sum >= k){
ret = query(rson,k);
}else{
ret = query(lson,k-segs[rt*2+1].sum);
}
PushUp(rt);
return ret;
}
int main(){
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
buildtree(1,1,n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
for(int i = n; i >= 1; i--){
ans[i] = query(1,1,n,a[i]-a[i-1]+1);
}
printf("%d",ans[1]);
for(int i = 2; i <= n; i++){
printf(" %d",ans[i]);
}puts("");
}
return 0;
}

  

上一篇:iOS上传AppStore被拒原因及处理方案


下一篇:AppStore被拒原因及总结