首页 > 代码库 > POJ 2828 Buy Tickets （线段树 单点更新 变形）

POJ 2828 Buy Tickets （线段树 单点更新 变形）

2024-07-15 20:21:00   216人阅读

题目链接

题意：有N个人排队，给出各个人想插队的位置和标识，要求输出最后的序列。

分析：因为之前的序列会因为插队而变化，如果直接算时间复杂度很高，所以可以用

线段树逆序插入，把序列都插到最后一层，len记录该区间里还剩余多少位置，插入的时候就插到剩余的第几个位置，

比如1，2已经插入了，如果再想插入第3个位置，则实际上插入的是5. 因为是逆序的，所以在3之前除了现在的1，2

还有之前的1，2.

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 const int maxn = 200000+10; 7 using namespace std; 8 int n, ans[maxn]; 9 struct node10 {11     int p, v;12 }a[maxn];13 struct line14 {15    int l, r, len; //区间剩余的长度16 }tr[4*maxn];17 void build(int o, int l, int r)18 {19     tr[o].l = l; tr[o].r = r;20     tr[o].len = r-l+1;21     if(l==r) return;22     int mid = (l+r)/2;23     build(2*o, l, mid);24     build(2*o+1, mid+1, r);25 }26 void update(int o, int p, int v)27 {28     tr[o].len --;29     if(tr[o].l==tr[o].r)30     {31         ans[tr[o].l] = v;  //ans记录最后一层的值32         return;33     }34     if(p<tr[2*o].len) update(2*o, p, v);35     else update(2*o+1, p-tr[2*o].len, v);36 }37 int main()38 {39     int i;40     while(~scanf("%d", &n))41     {42         for(i = 0; i < n; i++)43         scanf("%d%d", &a[i].p, &a[i].v);44         build(1, 0, n-1);45         for(i = n-1; i >= 0; i--) //逆序46         update(1, a[i].p, a[i].v);47 48         for(i = 0; i < n-1; i++)49         printf("%d ", ans[i]);50         printf("%d\n", ans[i]);51     }52     return 0;53 }

 


联系
我们