【插队问题-线段树-思维巧妙】【poj2828】Buy Tickets

时间:2024-11-13 21:04:56

可耻的看了题解

巧妙的思维

逆序插入,pos 代表的意义为前面要有pos个空格才OK;

证明:仔细思考一下就觉得是正确的,但是要想到这种方式还是要很聪明,空格是前面的几个数字所形成的,所以要特地留出来,因为这几个空格是既定的事实

线段树实现

线段的意义:当前线段留的空格数,满足区间和性质

代码如下:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=222222;
int tree[maxn*4];
int ANS[maxn];
int a[maxn],b[maxn];
int N;
void input()
{
for(int i=1;i<=N;i++) scanf("%d%d",&a[i],&b[i]);
}
void pushup(int rt)
{
tree[rt]=(tree[rt<<1]+tree[rt<<1|1]);
}
int build(int l,int r,int rt)
{
if(l==r) {tree[rt]=1;return 0;}
int m=(l+r)>>1;
build(rson);
build(lson);
pushup(rt);
}
int updata(int p,int k,int l,int r,int rt)//单点更新
{
int m,ok=0;
if(l==r) {tree[rt]=0;ANS[l]=k;return 1;}
m=(l+r)>>1;
if(p<tree[rt<<1]) updata(p,k,lson);
else updata(p-tree[rt<<1],k,rson);
pushup(rt);
return ok;
}
void solve()
{
for(int i=N;i>=1;i--)
{
updata(a[i],b[i],1,N,1);
}
for(int i=1;i<=N;i++)
{
printf("%d",ANS[i]);
if(i!=N) printf(" ");
}
printf("\n");
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
// init();
while(scanf("%d",&N)!=EOF)
{
build(1,N,1);
input();
solve();
}
return 0;
}