首页 > 代码库 > POJ 2828

POJ 2828

2024-07-16 14:10:39   219人阅读

题目大意：

不断将放进来的数字插入要求位置，最后将他们的值按在其所在顺序排序

 

简单的线段树问题，单点查询，从反向点一个个插入，线段树表示区间内还有多少空位，像找第几小的数那样自顶向下递归知道x==y

 

代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 200010 6 #define L ls,x,mid 7 #define R rs,mid+1,y 8 int sum[N<<2],order[N]; 9 void build(int cur,int x,int y)10 {11     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;12     sum[cur]=y-x+1;13     if(x==y) return;14     build(L);15     build(R);16 }17 int query(int cur,int x,int y,int k)18 {19     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;20     if(x==y) return x;21     if(sum[ls]>=k) return query(L,k);22     else return query(R,k-sum[ls]);23 }24 void update(int cur,int x,int y,int m)25 {26     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;27     sum[cur]--;28     if(x==y) return;29     if(m<=mid) update(L,m);30     else update(R,m);31 }32 int main()33 {34     int n,pos[N],val[N];35     while(~scanf("%d",&n)){36         for(int i=1;i<=n;i++) scanf("%d%d",&pos[i],&val[i]);37         build(1,1,n);38         for(int i=n;i>=1;i--){39             int ans=query(1,1,n,pos[i]+1);40             order[ans]=val[i];41             update(1,1,n,ans);42         }43         printf("%d",order[1]);44         for(int i=2;i<=n;i++) printf(" %d",order[i]);45         puts("");46     }47     return 0;48 }

 


联系
我们