POI 2001 Goldmine(Treap)

テーマリンク
Goldmine
Time Limit:1000 MSMemory Limit:30000 KB Total Submit:157 Acctepted:50
Description Byteman,one of the most derving employee of The Goldmine of Byteland,about to retire by the end of the year.The Goldmine management would liketo reward hihihimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimimition of the lot.Of course、A value of the lot depends on the location.The value of the lot is a number of gold nuggets in the ara of the loam(ia nugget lies the border of the lot、then it is is the the the of the lot).Youtasssssssssssssssssk proproproprograaaaatototototototototototototototototototototototototototototototototototototoloam( iffffffm thethethethethethethethethethethethethethethethethethethethethethethethethetheアニメーションIn order to simplify we asume that the terran of the Goldmine is boundless、but the ara of goldnugggetsoccurrence is limited.Task Write a program which:1.reads the location of gonugggts、2.ppputtitititiaaaaaaaaaaaaaaaaaaaaaaaaaaaaathethethethethethegogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogogowrites the result.
Input In the first line there are two positive integers and w separated by a single space,(1<=s,w==10 000)they denote the lengths of lot's sides-parallel to the OX-axe and OY-axe respively.The is one positive integer n written in the second line,(1<=n==15,000)It denotes the number of nuggets in the ara of the Goldmine.In the follwing n ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininin
Output The out shout contain exactly one integer equal to the value of the most valuable lot of a given size.
Sample Input 1 2 12 0 1 2 3 3 5 5 5 4 4 1 4 0 5 5 0 2 3 3 2 2 2 2
Sample Output 4
ソurce
POI 2001 III Stage
二次元平面にはn個の整数点があり、現在はSの長方形があり、幅はWである.長さと幅はそれぞれX軸、Y軸と平行です.この長方形は最大何個の点をカバーできますか?(点は長方形の辺でも上書きされます)
まず点をX順に並べて、前から後にかけて点を掃いて、毎回現在点を集合に入れて、集合を維持します.集合中点から現在点までの距離はSを超えません.現在の集合については、Y軸方向の長さがwの区間で最大集合のいくつの点をカバーできるかを求めます.
この問題に対して、縦座標はyであり、配列下標yで＋1、配列下標(y＋w＋1)で−1となります.配列のプレフィックスとsum[i]は、区間[i-w,i]の点の数です.問題は、行列の最大プレフィックスとを求めることです.
この問題は平衡樹or線分樹or樹状配列で解決できます.
ツリーコードのバランス:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<string.h>
#define nn 110000
#define mod 100003
typedef long long LL;
typedef unsigned long long LLU;
using namespace std;
int s,w;
int n;
pair<int,int>gold[nn];
void Sort(pair<int,int>*a,int l,int r)
{
    if(r==l)
        return ;
    int tem=rand()%(r-l+1)+l;
    swap(*(a+tem),*(a+r));
    int i;
    int k=l;
    for(i=l;i<=r;i++)
    {
        if(*(a+i)<=*(a+r))
        {
            swap(*(a+k),*(a+i));
            k++;
        }
    }
    if(k-2>l)
        Sort(a,l,k-2);
    if(k<r)
        Sort(a,k,r);
}
struct node
{
    int val1;
    int key;
    int val2;
    int num;
    int sum;
    int maxsum;
    node* son[2];
}*root;
void update(node *id)
{
    id->sum=id->val2;
    if(id->son[0]!=NULL)
    {
        id->sum+=id->son[0]->sum;
        id->maxsum=max(id->son[0]->maxsum,id->son[0]->sum+id->val2);
    }
    else
        id->maxsum=id->val2;
    if(id->son[1]!=NULL)
    {
        id->sum+=id->son[1]->sum;
        if(id->son[0]!=NULL)
            id->maxsum=max(id->maxsum,id->son[0]->sum+id->val2+id->son[1]->maxsum);
        else
            id->maxsum=max(id->maxsum,id->val2+id->son[1]->maxsum);
    }
}
void Rotate(node* &id,int d)
{
    node* tem=id->son[d];
    id->son[d]=tem->son[d^1];
    tem->son[d^1]=id;
    update(id);
    update(tem);
    id=tem;
}
void Insert(node* &id,pair<int,int>val)
{
    if(id==NULL)
    {
        id=new node;
        id->num=1;
        id->val1=val.first;
        id->val2=val.second;
        id->key=(rand()*rand())%nn;
        id->sum=val.second;
        id->maxsum=val.second;
        id->son[0]=id->son[1]=NULL;
        return ;
    }
    if(id->val1==val.first)
    {
        id->num++;
        id->val2+=val.second;
        update(id);
    }
    else if(id->val1>val.first)
    {
        Insert(id->son[0],val);
        update(id);
        if(id->son[0]->key<id->key)
        {
            Rotate(id,0);
        }
    }
    else
    {
        Insert(id->son[1],val);
        update(id);
        if(id->son[1]->key<id->key)
        {
            Rotate(id,1);
        }
    }
}
void Delete(node *&id,pair<int,int>val)
{
    if(id==NULL)
        return ;
    if(id->val1==val.first)
    {
        if(id->num==1)
        {
            if(id->son[0]==NULL)
                id=id->son[1];
            else if(id->son[1]==NULL)
                id=id->son[0];
            else
            {
                if(id->son[0]->key<id->son[1]->key)
                {
                    Rotate(id,0);
                    Delete(id->son[1],val);
                }
                else
                {
                    Rotate(id,1);
                    Delete(id->son[0],val);
                }
            }
        }
        else
        {
            id->num--;
            id->val2-=val.second;
        }
    }
    else if(id->val1>val.first)
    {
        Delete(id->son[0],val);
    }
    else
    {
        Delete(id->son[1],val);
    }
    if(id!=NULL)
        update(id);
}
int main()
{
    int i;
    while(scanf("%d%d",&s,&w)!=EOF)
    {
        root=NULL;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&gold[i].first,&gold[i].second);
        }
        Sort(gold,1,n);
        int pre=1;
        int ans=0;
        for(i=1;i<=n;i++)
        {
            while(gold[i].first-gold[pre].first>s)
            {
                Delete(root,make_pair(gold[pre].second,1));
                Delete(root,make_pair(gold[pre].second+w+1,-1));
                pre++;
            }
            Insert(root,make_pair(gold[i].second,1));
            Insert(root,make_pair(gold[i].second+w+1,-1));
            ans=max(ans,root->maxsum);
        }
        printf("%d
",ans);
    }
    return 0;
}

線分ツリーコード:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<string.h>
#include<vector>
#define nn 310000
#define mod 100003
typedef long long LL;
typedef unsigned long long LLU;
using namespace std;
int s,w;
int n;
pair<int,int>gold[nn];
void Sort(pair<int,int>* a,int l,int r)
{
    if(l==r)
        return ;
    int tem=(rand()*rand())%(r-l+1)+l;
    swap(*(a+tem),*(a+r));
    int k=l;
    for(int i=l;i<=r;i++)
    {
        if(*(a+i)<=*(a+r))
        {
            swap(*(a+i),*(a+k));
            k++;
        }
    }
    if(k-2>l)
        Sort(a,l,k-2);
    if(k<r)
        Sort(a,k,r);
}
int L[nn],R[nn];
int sum[nn],presum[nn];
void build(int id,int l,int r)
{
    L[id]=l;
    R[id]=r;
    sum[id]=presum[id]=0;
    if(l==r)
    {
        return ;
    }
    int mid=(l+r)/2;
    build(2*id,l,mid);
    build(2*id+1,mid+1,r);
}
void push_up(int id)
{
    sum[id]=sum[2*id]+sum[2*id+1];
    presum[id]=max(presum[2*id],sum[2*id]+presum[2*id+1]);
}
void update(int id,int wei,int val)
{
    if(L[id]==R[id])
    {
        sum[id]+=val;
        presum[id]+=val;
        return ;
    }
    int mid=(L[id]+R[id])/2;
    if(wei<=mid)
    {
        update(2*id,wei,val);
    }
    else
        update(2*id+1,wei,val);
    push_up(id);
}
int ve[nn];
map<int,int>ma;
int main()
{
    int i;
    while(scanf("%d%d",&s,&w)!=EOF)
    {
        scanf("%d",&n);
        int lv=0;
        ma.clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&gold[i].first,&gold[i].second);
            ve[++lv]=gold[i].second;
            ve[++lv]=gold[i].second+w+1;
        }
        sort(ve+1,ve+lv+1);
        lv=unique(ve+1,ve+lv+1)-ve-1;
        for(i=1;i<=lv;i++)
        {
            ma[ve[i]]=i;
        }
        Sort(gold,1,n);
        int pre=1;
        build(1,1,lv);
        int ans=0;
        for(i=1;i<=n;i++)
        {
            while(gold[i].first-gold[pre].first>s)
            {
                update(1,ma[gold[pre].second],-1);
                update(1,ma[gold[pre].second+w+1],1);
                pre++;
            }
            update(1,ma[gold[i].second],1);
            update(1,ma[gold[i].second+w+1],-1);
            ans=max(ans,presum[1]);
        }
        printf("%d
",ans);
    }
    return 0;
}