学步园

静态二叉检索树。

其实说来奇怪，

学ACM这么长时间了，而且我还是负责基础数据结构的，

居然连这个都没写过。

//我发现我现在做的题都好水啊咋办咋办。。

题目链接：http://poj.org/problem?id=2482

题意：

给出平面上的一些点，每个点有权值

问用一个w*h的矩形最多框住的点权和是多少

矩形边框上的点不算在矩形内

算法：

把每个点拆成四个点，(x,y,val),(x,y+h,-val),(x+w,y,-val),(x+w,y+h,val)

对y进行离散化

由于是每个点加入之后都查询一次最大值，

所以插入时，值为负的应当在前。也就是排序时应该按照(x,val)点对排序，而不是按照(x,y,val)三元组排序

然后用二叉检索树对于每个节点维护两个值。

对于节点rt，假设它所在的子树种最靠左的点(即y值最小的点)是l，那么

sum[rt]=sum of [l,rt]

tr[rt]=max(sum of(l,x)) x是节点rt及其两棵子树种的任意点

trick: x,y虽然是int范围，但加上w,h后就会越界。

代码如下：

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN=11000;
vector<long long>hash;
vector<pair<pair<long long, int>, long long> >node;
int tr[MAXN<<3],sum[MAXN<<3];

void update(int l, int r, int x, int c, int rt) {

    int mid=(l+r)>>1;
    if(mid==x) {
        sum[rt]+=c;
    } else if(x<mid) {
        update(l,mid-1,x,c,rt<<1);
        sum[rt]+=c;
    } else {
        update(mid+1,r,x,c,rt<<1|1);
    }
    tr[rt]=sum[rt];
    if(l<mid) {
        tr[rt]=max(tr[rt],tr[rt<<1]);
    }
    if(r>mid) {
        tr[rt]=max(tr[rt],sum[rt]+tr[rt<<1|1]);
    }
}

int main() {
    int n,w,h;
    while(scanf("%d%d%d",&n,&w,&h)==3) {
        hash.clear();
        node.clear();
        for(int i=0; i<n; i++) {
            long long x,y;
            int val;
            scanf("%lld%lld%d",&x,&y,&val);
            node.push_back(make_pair(make_pair(x,val),y));
            node.push_back(make_pair(make_pair(x+w,-val),y));
            node.push_back(make_pair(make_pair(x,-val),y+h));
            node.push_back(make_pair(make_pair(x+w,val),y+h));
            hash.push_back(y);
            hash.push_back(y+h);
        }
        sort(hash.begin(),hash.end());
        hash.erase(unique(hash.begin(),hash.end()),hash.end());
        sort(node.begin(),node.end());
        memset(tr,0,sizeof(tr));
        memset(sum,0,sizeof(sum));
        int ans=0;
        int lim=hash.size();
        for(int i=0; i<node.size(); i++) {
            update(0,lim-1,lower_bound(hash.begin(),hash.end(),node[i].second)-hash.begin(),node[i].first.second,1);
            ans=max(ans,tr[1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}