Buy Tickets(线段树)

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=200010;
 4 int Tree[N*4],seq[N];
 5 int pos[N],val[N];
 6 
 7 void build(int l,int r,int rt)
 8 {
 9     Tree[rt]=r-l+1;//初始每个区间的空位数
10     if(l==r)
11         return;
12     int mid=(l+r)>>1;
13     build(l,mid,2*rt);
14     build(mid+1,r,2*rt+1);
15 }
16 void update(int p,int v,int l,int r,int rt)
17 {
18     Tree[rt]--;//每更新一次空位数-1
19     if(l==r)
20     {
21         seq[l]=v;//将value放在l位置中
22         return ;
23     }
24     int mid=(l+r)>>1;
25     if(Tree[2*rt] >= p)//左区间的空位数量够
26         update(p,v,l,mid,2*rt);//更新左区间
27     else    //左区间的空位数量不够，则p在右区间
28     {
29         p-=Tree[2*rt];//减去左区间的空位
30         update(p,v,mid+1,r,2*rt+1);//更新右区间
31     }
32 }
33 int main()
34 {
35     int n;
36     while(~scanf("%d",&n))
37     {
38         build(1,n,1);
39         for (int i = 1; i <= n; i++)
40         {
41             scanf("%d%d",&pos[i],&val[i]);
42             pos[i]++;
43         }
44         for (int i = n; i > 0; i--)//倒着更新，因为来的越晚的人越有利于占据pos位置
45         {
46             update(pos[i],val[i],1,n,1);
47         }
48         for (int i = 1; i <= n; i++)
49         {
50             if (i==1)
51                 printf("%d",seq[i]);
52             else
53                 printf(" %d",seq[i]);
54         }
55         puts("");
56     }
57     return 0;
58 }