寒假集训专题五-But Tickets

Buy tickets--插队问题

题意

给n个数对pos，val，表示某人要插队的位置和权值，按顺序输出队伍的权值

思路

若按找正序想，难以确定每个人的位置

若按照倒序想，首先可以确定最后一个人的位置，然后再从后往前依次确定每个人的位置（若该位置有空,则插入，若没有，则往后查找）

因为涉及到查找，当目标是第一个空却需要插入至最后一个空此时的时间是2e5,有2e5个数一定超时，所以采用线段树的方法。

先把位置变成1，n

eg.

拿第一个举例

插入3 49

找到3的位置，直接插入

插入 2 33

找到 2 的位置，大小足够 插入

插入2 51

到 1-2的结点 大小为1（已经被占了一个）

所以转移到插入3-4结点

此时的插入要求的位置也要变化 p=p-tr[ u<<1 ]

有1个位置，3已经被用过，只能插入4

记得用scanf 和 printf

AC代码

#include
#include
#include
#include
using namespace std;
typedef pair PII;
const int N=2e5+7;
int b[N];
struct node{
	int l,r,size;
}tr[N<<2];
void bt(int u,int l,int r)
{
	if(l==r)
	{
		tr[u]={l,r,1};
		return;
	}
	tr[u]={l,r,0};
	int mid=l+r>>1;
	bt(u<<1,l,mid);
	bt(u<<1|1,mid+1,r);
	tr[u].size=tr[u<<1].size+tr[u<<1|1].size;
}
void update(int u,PII &p)
{
	if(tr[u].l==tr[u].r)
	{
		b[tr[u].l]=p.second;
		tr[u].size--;
		return ;
	}
	if(tr[u<<1].size>=p.first)
	{
		update(u<<1,p);
	}
	else
	{
		p.first=p.first-tr[u<<1].size;
		update(u<<1|1,p);
	}
	tr[u].size=tr[u<<1].size+tr[u<<1|1].size;
}
signed main()
{
	
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		memset(b,0,sizeof(b));
	vector ve(n);
	for(int i=0;i=0;i--)
	{
		update(1,ve[i]);
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",b[i]); 
	}
	printf("\n");
	}
}