USACO 2013 November Contest, Silver Problem 2. Crowded Cows (Copy on Write 線段樹模板)

http://www.usaco.org/index.php?page=viewproblem2&cpid=344

要用copy on write 線段樹支援！！！

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;

struct Node {
    Node* lc;
    Node* rc;
    int val;
    Node() {
        lc=rc=NULL;
        val=-1;
    }
    void pull() {
        if (lc==NULL && rc==NULL) val=-1;
        else if (lc==NULL && rc!=NULL) val=rc->val;
        else if (lc!=NULL && rc==NULL) val=lc->val;
        else if (lc!=NULL && rc!=NULL) val=max(rc->val,lc->val);
    }
};

void modify(Node* node,int L,int R,int pos,int val) {  //similar to build
    if (L==R) {
        assert(L==pos);
        node->val=val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) {
        if (node->lc==NULL) {
            Node* tmp = new Node();
            node->lc=tmp;
        }
        modify(node->lc,L,mid,pos,val);
    }
    else if (pos>mid) {
        if (node->rc==NULL) {
            Node* tmp = new Node();
            node->rc=tmp;
        }
        modify(node->rc,mid+1,R,pos,val);
    }
    node->pull();
}

int query(Node* node,int L,int R,int l,int r) {
    if (L>r||l>R) return -1;
    else if (l<=L && R<=r) return node->val;
//    else if (L==R) return node->val;
    int mid=(L+R)>>1;
    int q1=-1;
    if (node->lc==NULL) q1=-1;
    else q1=query(node->lc,L,mid,l,r);
    int q2=-1;
    if (node->rc==NULL) q2=-1;
    else q2=query(node->rc,mid+1,R,l,r);
//    cout<<"return "<<max(q1,q2)<<endl;
    return max(q1,q2);
}

const int MAX_N = 50002;
const int MAX_H = 1000000005;

int x[MAX_N], h[MAX_N];

int main () {
    freopen("crowded.in","r",stdin);
    freopen("crowded.out","w",stdout);
    int n,d;
    while (scanf("%d %d",&n,&d) != EOF) {
        Node* root = new Node();
        for (int i=0;n>i;i++) {
            scanf("%d %d",&x[i],&h[i]);
            modify(root,1,MAX_H,x[i],h[i]);
        }
        int ans=0;
        //start query
        for (int i=0;n>i;i++) {
            //left side
            int anss=0;
            if (x[i]!=1) {
                int L=(x[i]-d),R=x[i]-1;
                if (L<=1) L=1;
                int tmp=query(root,1,MAX_H,L,R);
                if (tmp>=2*h[i]) {
                    anss++;
                }
            }
            if (x[i]!=MAX_H) {
                int L=(x[i]+1),R=x[i]+d;
                if (R>=MAX_H) R=MAX_H;
                int tmp=query(root,1,MAX_H,L,R);
                if (tmp>=2*h[i]) {
                    anss++;
                }
            }
            if (anss==2) ans++;
        }
        printf("%d\n",ans);
//        for (int x=1;20>=x;x++) cout << x << " = " << query(root,1,MAX_H,x,20)<<endl;
    }
}