稳定方块

瓦西亚和皮台亚摆放了m个方块。方块被编号为0到m-1(每个号码出现恰好一次)。现在建立一个座标系OX表示地面，OY的方向是竖直向上的。每一方块的左下角有一个座标而且是整点座标。

摆放好的方块一定要是稳定的。稳定的含意是每一个不在地面上的方块在他的下面至少有一个方块与他相接触。可以是共边，也可以是共点的。也就是说如果方块座标为(x,y)，要么y=0，或者存在一个方块的座标为(x-1,y-1)或者 (x,y-1) 或者 (x+1,y-1)。

现在瓦西亚和皮台亚要轮流把这些方块一个个拆下来。按照拆下来的顺序从左到右摆成一行，那么方块上面的编号就会组成一个m进制的数字。

拆的过程中，要始终保持剩下的方块稳定。瓦西亚想要最终的数字尽可能大，而皮台亚想要尽可能小，瓦西亚先开始拆。

请帮助计算一下最终形成的数字是多少，结果比较大，输出对 $10^{9} + 9$

取余后的结果。

样例解释：

先拿（0，1）编号为2

再拿（2，1）编号为0

再拿（1，0）编号为1

最后形成的数字是201，转成10进制是19。

Input单组测试数据。
第一行有一个整数 m (2≤m≤10^5)。
接下来m行，每一行有一个方块的座标xi,yi (-10^9≤xi≤10^9, 0≤yi≤10^9)，第i个的编号为i。i从0开始。
输入保证刚开始的摆放是稳定的，而且没有两个方块的座标是一样的。Output输出结果占一行。Sample Input

样例输入1
3
2 1
1 0
0 1

Sample Output

样例输出1
19

题解：
　　这个题目，想起来非常简单，我们只要用一个set维护可以拿掉物品的集合就可以了。
　　然而这个题目实现非常困难，有几处实现十分神奇，特别是用边来存上下物品这一点，还是开一下代码吧。相信可以学到很多实现的技巧。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <set>
#include <queue>
#define ll long long
const int N=1e6;
const int mod=1e9+9;
using namespace std;
struct node{
    int x,y,id;
    bool operator < (const node &h)const{
        if(h.x==x) return h.y<y;
        return h.x<x;
    }
}no[N];
int num[N],hehe[N],n,num1=0,num2=0;
set<node> s;
set<int> q;
set<node>::iterator it;
set<int>::iterator it2;
struct edge{
    int first;
    int next;
    int to;
}a[N],b[N];
bool vis[N];

void addedge(int from,int to){
    a[++num1].to=to;
    a[num1].next=a[from].first;
    a[from].first=num1;
    b[++num2].to=from;
    b[num2].next=b[to].first;
    b[to].first=num2;
    hehe[from]++;
}

bool check(int now){
    for(int i=b[now].first;i;i=b[i].next){
        int to=b[i].to;
        if(vis[to]) continue;
        if(hehe[to]==1) return 0;
    }
    return 1;
}

int getmax(){
    it2=q.end();it2--;
    while(!check(*it2)){
        q.erase(it2);it2=q.end();it2--;
    }
    return *it2;
}

int getmin(){
    it2=q.begin();
    while(!check(*it2)){
        q.erase(it2);it2=q.begin();
    }
    return *it2;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&no[i].x,&no[i].y),no[i].id=i;
    for(int i=1;i<=n;i++) s.insert(no[i]);
    for(int i=1;i<=n;i++){
        int x=no[i].x,y=no[i].y;
        node fi=(node){x-1,y-1,0},si=(node){x,y-1,0},ci=(node){x+1,y-1,0};
        if((it=s.find(fi))!=s.end()) addedge(i,it->id);//
        if((it=s.find(si))!=s.end()) addedge(i,it->id);//
        if((it=s.find(ci))!=s.end()) addedge(i,it->id);//why
    }
    for(int i=1;i<=n;i++) if(check(i)) q.insert(i);
    int m=n,id=1;
    while(m){
        int now;
        if(id==1) now=getmax();
        else now=getmin();id^=1;
        vis[now]=1;
        num[m--]=now;
        for(int i=b[now].first;i;i=b[i].next){
            int to=b[i].to;
            hehe[to]--;
        }
        for(int i=a[now].first;i;i=a[i].next){
            int to=a[i].to;
            if(vis[to]) continue;
            if(check(to)) q.insert(to);
        }
        q.erase(now);
    }
    ll ans=0;
    for(ll i=1,j=1;i<=n;i++,j=((ll)n*j%mod)){
        ans=(ans+((num[i]-1)*(ll)j)%mod)%mod;
    }
    printf("%lld
",ans);
    return 0;
}