poj 2828--Buy Tickets(线段树)

时间:2021-11-06 17:02:58

Description

Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…

The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.

It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!

People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.

Input

There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:

  • Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
  • Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.

There no blank lines between test cases. Proceed to the end of input.

Output

For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.

题意:按顺序给你n个人,给你他想要排的位置pos和他拥有的值val后来着可以插队比如pos[0]=0,pos[1]=0,那么pos[0]就变成了1被插队了。

问最后n个人排好后各自位置是多少,输出各个位置上对应的val值。

举一个例子6个人 1 2 3 4 5 6 位置,倒过来考虑因为最后一个选位置没人和他抢。假设他要2号位那么序列变为 1 0 2 3 4 5前面选2好位的只能退一位。

当前一个人选4号位那么 1 0 2 3 0 4,以此类推排好位置。这种方法用到前缀和就是一开始全部位置初值为1然后求个位置的前缀和,如果这个位置被选了

那么这个位置的值就变成0,更新。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 2e6 + 10;
int re;
int pos[M] , Val[M] , last[M];
struct TnT {
int l , r , val;
}T[M << 2];
void build(int l , int r , int p) {
int mid = (l + r) >> 1;
T[p].l = l , T[p].r = r;
if(T[p].l == T[p].r) {
T[p].val = 1;
return ;
}
build(l , mid , p << 1);
build(mid + 1 , r , (p << 1) | 1);
T[p].val = T[p << 1].val + T[(p << 1) | 1].val;
}
void updata(int num , int p) {
if(T[p].l == T[p].r) {
T[p].val = 0;
re = T[p].l;
return ;
}
if(num <= T[p << 1].val) {
updata(num , p << 1);
}
else {
updata(num - T[p << 1].val , (p << 1) | 1);
}
T[p].val = T[p << 1].val + T[(p << 1) | 1].val;
}
int main()
{
int n;
while(scanf("%d" , &n) != EOF) {
build(1 , n , 1);
for(int i = 0 ; i < n ; i++) {
scanf("%d%d" , &pos[i] , &Val[i]);
pos[i]++;
}
for(int i = n - 1 ; i >= 0 ; i--) {
updata(pos[i] , 1);
last[re] = Val[i];
}
for(int i = 1 ; i <= n ; i++) {
printf("%d " , last[i]);
}
printf("\n");
}
return 0;
}

poj 2828--Buy Tickets(线段树)的更多相关文章

  1. poj 2828 Buy Tickets &lpar;线段树(排队插入后输出序列)&rpar;

    http://poj.org/problem?id=2828 Buy Tickets Time Limit: 4000MS   Memory Limit: 65536K Total Submissio ...

  2. POJ 2828 Buy Tickets &lpar;线段树 or 树状数组&plus;二分&rpar;

    题目链接:http://poj.org/problem?id=2828 题意就是给你n个人,然后每个人按顺序插队,问你最终的顺序是怎么样的. 反过来做就很容易了,从最后一个人开始推,最后一个人位置很容 ...

  3. POJ 2828 Buy Tickets 线段树 倒序插入 节点空位预留(思路巧妙)

    Buy Tickets Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 19725   Accepted: 9756 Desc ...

  4. POJ 2828 Buy Tickets &vert; 线段树的喵用

    题意: 给你n次插队操作,每次两个数,pos,w,意为在pos后插入一个权值为w的数; 最后输出1~n的权值 题解: 首先可以发现,最后一次插入的位置是准确的位置 所以这个就变成了若干个子问题, 所以 ...

  5. POJ 2828 Buy Tickets&lpar;线段树&amp&semi;&num;183&semi;插队&rpar;

    题意  n个人排队  每一个人都有个属性值  依次输入n个pos[i]  val[i]  表示第i个人直接插到当前第pos[i]个人后面  他的属性值为val[i]  要求最后依次输出队中各个人的属性 ...

  6. POJ 2828 Buy Tickets&lpar;线段树单点&rpar;

    https://vjudge.net/problem/POJ-2828 题目意思:有n个数,进行n次操作,每次操作有两个数pos, ans.pos的意思是把ans放到第pos 位置的后面,pos后面的 ...

  7. poj 2828 Buy Tickets &lpar;线段树&rpar;

    题目:http://poj.org/problem?id=2828 题意:有n个人插队,给定插队的先后顺序和插在哪个位置还有每个人的val,求插队结束后队伍各位置的val. 线段树里比较简单的题目了, ...

  8. POJ - 2828 Buy Tickets &lpar;段树单点更新&rpar;

    Description Railway tickets were difficult to buy around the Lunar New Year in China, so we must get ...

  9. POJ 2828 Buy Tickets(排队问题,线段树应用)

    POJ 2828 Buy Tickets(排队问题,线段树应用) ACM 题目地址:POJ 2828 Buy Tickets 题意:  排队买票时候插队.  给出一些数对,分别代表某个人的想要插入的位 ...

  10. poj 2828 Buy Tickets&lpar;树状数组 &vert; 线段树&rpar;

    题目链接:poj 2828 Buy Tickets 题目大意:给定N,表示有个人,给定每一个人站入的位置,以及这个人的权值,如今按队列的顺序输出每一个人的权值. 解题思路:第K大元素,非常巧妙,将人入 ...

随机推荐

  1. coderforces 721b

    题目描述: B. Passwords time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

  2. spring源码分析之spring注解&commat;Aspect是如何工作的?

    1.@Aspect 在xml定义:<aop:aspectj-autoproxy />,其定义在http://www.springframework.org/schema/aop/sprin ...

  3. github的初次体验及管理代码的心得

    周六早上的课上,助教给我们演示了一遍如何上传和下载代码库,新建代码库等等,但是是在linux上的,而我的笔记本的操作系统是win7的.而在教室中的尝试因为网络原因,虽然可以上github的网站,但是下 ...

  4. 视频处理控件TVideoGrabber中如何混合多个视频源(1)

    其实一个或是几个作为普通的视频源使用的TVideoGrabber组件,可以进行混合来作为一个TVideoGrabber组件使用,这些普通的组件可以是视频捕捉设备或是视频剪辑等.同时这个混合的组件独立于 ...

  5. 通知&lpar;Notification&rpar; 、 应用间通信(一)

    1 使用通知中心发送消息 1.1 问题 当一个对象需要向多个接受者发送消息的,或者不用知道消息的接收者是谁,就可以使用IOS提供的NSNotificationCenter通知中心,本案例使NSNoti ...

  6. Sublime Text 3常用插件

    操作:按下Ctrl+Shift+P调出命令面板 输入install 调出 Install Package 选项并回车,然后在列表中选中要安装的插件. 常用插件: 1---- Bracket Highl ...

  7. mysql初体验

    1.mysql数据库: 数据库----文件夹 数据表----文件 数据数据行---文件中的一行数据2. 初始: show databases; 查看当前mysql都有那些数据库,也就是根目录有哪些文件 ...

  8. css 元素溢出

    css元素溢出: 当子元素的尺寸超过父元素的尺寸时,需要设置父元素显示溢出的子元素的方式,设置的方法是通过overflow属性来设置. overflow的设置项: (1)visible 默认值 内容不 ...

  9. JS创建对象的几种方式整理

    javascript是一种“基于prototype的面向对象语言“,与java有非常大的区别,无法通过类来创建对象.那么,既然是面象对象的,如何来创建对象呢? 一:通过“字面量”方式创建对象 方法:将 ...

  10. 【iCore4 双核心板】4&period;3寸液晶模块程序发布

    一.说明 1.本资料包程序包含两部分,"CAPTURE"为液晶显示截图,"tft4.3"为ARM程序. 2.此程序只适合iCore4液晶模块. 3.iCore4 ...