POJ 2828 Buy Tickets（單點更新）

題意：有n個的排隊，每一個人都有一個val來對應，每一個後來人都會插入目前隊伍的某一個位置pos。要求把隊伍最後的狀态輸出。

逆向思維。我們可以這樣考慮，最後一個人一定會得到目前隊伍他想要的位置，如果我們往前一個階段，倒數第二個人也一定能得到他想要的位置……，也就是說，我們可以這樣處理，我們把最後一個人插入，然後忽略它，再把倒數第二個人插入。即，我們找出目前隊伍他想要插入的位置pos的真正坐标就可以。然後去更新整個隊伍的長度。如此循環，直到最後一個人。線段樹在單點更新的時候，感覺和二分查找是很相似的，可以用它實作。

/*代碼風格更新後*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=200005;

struct node
{
	int lft,rht,valu;
	int mid(){return MID(lft,rht);}
};

int x[N],y[N],res[N],n;

struct Segtree
{
	node tree[N*4];
	void build(int lft,int rht,int ind)
	{
		tree[ind].lft=lft;	tree[ind].rht=rht;
		tree[ind].valu=rht-lft+1;
		if(lft!=rht)
		{
			int mid=tree[ind].mid();
			build(lft,mid,LL(ind));
			build(mid+1,rht,RR(ind));
		}
	}
	int query(int valu,int ind)
	{
		int lft=tree[ind].lft,rht=tree[ind].rht;
		if(lft==rht)
		{
			tree[ind].valu=0;
			return lft;
		}
		else 
		{
			int pos;
			if(tree[LL(ind)].valu>=valu) pos=query(valu,LL(ind));
			else pos=query(valu-tree[LL(ind)].valu,RR(ind));
			tree[ind].valu=tree[LL(ind)].valu+tree[RR(ind)].valu;
			return pos;
		}
	}
}seg;
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		seg.build(0,n-1,1);
		for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
		for(int i=n-1;i>=0;i--)
		{
			int pos=seg.query(x[i]+1,1);
			res[pos]=y[i];
		}
		for(int i=0;i<n;i++)
			printf("%d%c",res[i],i==n-1?'\n':' ');
	}
	return 0;
}           

/*代碼風格更新前*/
#include <iostream>
#include <cstdio>
using namespace std;
const int N=200005;
int y[N];
struct Per
{
    int pos,val;
}per[N];
struct node
{
    int left,right,cnt;
    int mid(){return left+(right-left)/2;}
    int dis(){return right-left+1;}
};
struct Segtree
{
    node tree[N*4];
    void build(int left,int right,int r)
    {
        tree[r].left=left;  tree[r].right=right;
        tree[r].cnt=tree[r].dis();
        if(left<right)
        {
            int mid=tree[r].mid();
            build(left,mid,r*2);
            build(mid+1,right,r*2+1);
        }
    }
    int query(int pos,int r)
    {
        tree[r].cnt--;
        if(tree[r].left==tree[r].right) return tree[r].left;
        else
        {
            if(pos<tree[r*2].cnt) return query(pos,r*2);
            else return query(pos-tree[r*2].cnt,r*2+1);
        }
    }
}seg;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++) scanf("%d%d",&per[i].pos,&per[i].val);
        seg.build(0,n-1,1);
        for(int i=n-1;i>=0;i--)
        {
            int pos=seg.query(per[i].pos,1);
            y[pos]=per[i].val;
        }
        for(int i=0;i<n;i++)
        {
            if(i!=0) putchar(' ');
            printf("%d",y[i]);
        }
        puts("");
    }
    return 0;
}