p2352xds.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
using namespace std;
const int MAXN = 70000;
const int MAXS = 16001;
int b[MAXN],e[MAXN],c[MAXN];
int ans[MAXS];
int insert(int x,int v){
//    puts("i");
    if(b[v] == e[v]){
        ++c[v];
        return v;
    }
    if(x <= (b[v] + e[v]) / 2){
        b[2*v+1] = b[v];
        e[2*v+1] = (b[v] + e[v]) / 2;
        ++c[v];
        insert(x,2*v+1);
    }
    else{
        b[2*(v+1)] = (b[v] + e[v]) / 2 + 1;
        e[2*(v+1)] = e[v];
        ++c[v];
        insert(x,2*(v+1));
    }
    return v;
}
int query(int x,int v){
    int res(0);
//    puts("q");
//    cout << b[v] << " " << e[v] << endl;
    if(b[v] == e[v]) return c[v];
    if(x >= (b[v] + e[v]) / 2 || c[2*v+1] == 0) res += c[2*v+1];
    else res += query(x,2*v+1);
    if(x > (b[v] + e[v]) / 2 && c[2*(v+1)] != 0) res += query(x,2*(v+1));
    return res;
}

int main(){
    int n,t,x,y;
    scanf("%d",&n);
    b[0] = 0;   e[0] = 32000;
    memset(c,0,sizeof(c));
    memset(ans,0,sizeof(ans));
    for(int i = 0;i < n;++i){
        scanf("%d%d",&x,&y);
        t = query(x,0);
        ++ans[t];
        insert(x,0);
    }
    for(int i = 0;i < n;++i)
        printf("%d\n",ans[i]);
    system("pause");
}