POI 2001 Glodmine 金礦

發現座標的範圍很大,而點並不是很多,首先想到了離散化的方法。然後橫向掃描每個帶狀的區間,對於每個帶狀區間,再縱向掃描其中點的個數。這種方法是最容易想到的,但是時間複雜度卻高達O(N^2logN)。關鍵在於優化每次確定帶狀區間的縱向掃描。

顯然對於確定的帶狀區間,我們掃描時只需考慮它們的縱座標。如果我們把一個縱座標爲y的點描述成兩個事件(y,1)和 (y+h+1,-1),然後把所有事件按照第一關鍵字排序,定義S[i]爲前i項事件的第二關鍵字之和,那麼Max{S[i]}就是確定的帶狀區間內高度 爲w的矩形最多覆蓋到的點數。爲什麼是這樣,我們可以想象有兩個擋板,分別是y=A-h-1(下板)和y=A(上板),從下向上移動擋板,從而確定一個矩 形。某個點的第一個事件爲(y,1),當上板A=y時,該點被覆蓋,若A繼續增大,使得A-h-1=y,該點就恰好離開了覆蓋區域,反過來我們可以以爲是 A=y+h+1,所以定義第二個事件爲(y+h+1,-1)。這樣,前i個事件的第二關鍵字和S[i],就代表了矩形在某個位置時覆蓋的點數。S[i]的 最大值就是確定的帶狀區間內最大的覆蓋點數。

帶狀區間的左右掃描,也可以考慮成兩個擋板之間的問題,首先確定擋板的初始位置在最左端,依次向右移動左右兩個擋板。確定一個區間後,統 計點事件的最大前綴和成了最關鍵的問題。由於左右擋板是移動的,我們需要動態統計一個排序結構。於是我們想到了用平衡樹,維護每個點事件的第一關鍵字(y 座標)升序,並記錄權。移動右擋板時,把右擋邊新位置所在線上的所有點對應的兩個點事件加入平衡樹;移動左擋板時,把左擋板時,把左擋邊所在線上的所有點 事件從平衡樹中刪除。

爲了快速統計出最大的前綴和,在此基礎上,我們還需要對於平衡樹中每個節點維護其子樹所有節點權值和,以及子樹中最大的前綴和。定義p的權值爲p.w,以節點p爲根的子樹的權值和爲p.s,以節點p爲根的子樹的最大的前綴和爲p.m,我們可以遞推算出p.m的值。

p.m=Max{
    p.left.m; //最大前綴和的尾元素在左子樹
    p.left.s+p.w; //最大前綴和的尾元素就是p
    p.left.s+p.w+p.right.m; //最大前綴和的尾元素在右子樹
}

於是全部序列的最大前綴和就是根節點root.m。

於是得到的算法如下:

  1. 建立離散化座標系;
  2. 左右掃描,確定帶狀區間,維護平衡樹中節點;
  3. 統計對於確定帶狀區間,平衡樹中元素最大的前綴和;
算法總的時間複雜度爲O(NlogN),可以解決問題了。編程中細節要注意,尤其是在於平衡樹維護平衡性時要對節點m值重新計算。我用了 Treap,在插入一個點要旋轉時,注意要先重新計算旋轉到子樹的點的m值,再計算子樹根節點的m值。而刪除僅僅懶惰刪除即可,重要的是維護m值。

/* 
 * Problem: POI2001 kop
 * Author: Guo Jiabao
 * Time: 2009.2.7 16:16
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAXN=15001;
struct point{int x,y;};
struct linknode{int s;linknode *next;};
class Treap_node
{
    public:
        Treap_node *left,*right;
        int fix,weight,sum,m,key;
        Treap_node(int tk,int w):key(tk),weight(w),sum(w),m(w){fix=rand();left=right=0;}
        inline int leftsum (){return left ?left ->sum:0;}
        inline int rightsum(){return right?right->sum:0;}
};

int H,W;//區域高度 寬度
int N,L,Lc=-1,MaxAns;
int D[MAXN];
point P[MAXN];
linknode LS[MAXN],*Line[MAXN];
Treap_node *Treap_root;

void Treap_Rotate_Right(Treap_node *&p)
{
    Treap_node *q=p->left;
    q->sum+=p->rightsum()+p->weight;
    p->sum=q->rightsum()+p->rightsum()+p->weight;
    p->left=q->right;
    q->right=p;
    p=q;
}

void Treap_Rotate_Left(Treap_node *&p)
{
    Treap_node *q=p->right;
    q->sum+=p->leftsum()+p->weight;
    p->sum=q->leftsum()+p->leftsum()+p->weight;
    p->right=q->left;
    q->left=p;
    p=q;
}

void Treap_maintain(Treap_node *&p)
{
    int lm,ls,rm;
    lm=ls=rm=0;
    if (p->left)
        lm=p->left->m,ls=p->left->sum;
    if (p->right)
        rm=p->right->m;
    p->m=lm;
    if (ls + p->weight > p->m)    p->m = ls + p->weight;
    if (ls + p->weight + rm > p->m) p->m=ls + p->weight + rm;
}

void Treap_edit(Treap_node *&p,int v,int delta)
{
    if (!p)
        p=new Treap_node(v,delta);
    else
    {
        if ( v < p->key )
        {
            p->sum+=delta;
            Treap_edit(p->left,v,delta);
            if (p->left && p->left->fix < p->fix)
            {
                Treap_Rotate_Right(p);
                Treap_maintain(p->right);
            }
            Treap_maintain(p);
        }
        else if ( v > p->key )
        {
            p->sum+=delta;
            Treap_edit(p->right,v,delta);
            if (p->right && p->right->fix < p->fix)
            {
                Treap_Rotate_Left(p);
                Treap_maintain(p->left);
            }
            Treap_maintain(p);
        }
        else
        {
            p->weight+=delta;
            p->sum+=delta;
            Treap_maintain(p);
        }
    }
}

void linktable_ins(linknode *&p,int v)
{
    if (p)
    {
        linknode *t=p;
        p=&LS[++Lc];
        p->next=t;
    }
    else
        p=&LS[++Lc];
    LS[Lc].s=v;
}

void init()
{
    freopen("kop.in","r",stdin);
    freopen("kop.out","w",stdout);
    scanf("%d%d%d",&W,&H,&N);
    for (int i=1;i<=N;i++)
        scanf("%d%d",&P[i].x,&P[i].y);
}

inline int cmp(const void *a,const void *b)
{
    return ((point *)a)->x - ((point *)b)->x;
}

void discrete() //離散化橫座標 建立鏈表
{
    int i,lastv=-1;
    qsort(P+1,N,sizeof(P[0]),cmp);
    L=0;
    for (i=1;i<=N;i++)
    {
        if (P[i].x!=lastv)
        {
            lastv=P[i].x;
            D[++L]=P[i].x;
            linktable_ins(Line[L],P[i].y);
        }
        else
            linktable_ins(Line[L],P[i].y);
    }
}

void RemoveLine(int p)
{
    for (linknode *k=Line[p];k;k=k->next)
    {
        Treap_edit(Treap_root,k->s,-1);
        Treap_edit(Treap_root,k->s+H+1,1);
    }
}

void AddLine(int p)
{
    for (linknode *k=Line[p];k;k=k->next)
    {
        Treap_edit(Treap_root,k->s,1);
        Treap_edit(Treap_root,k->s+H+1,-1);
    }
}


void scanx() //橫向掃描 確定區間
{
    int Lb,Rb;
    AddLine(1);
    for (Lb=Rb=1;Rb<L && Lb<=L;)
    {
        while (Rb+1<=L && D[Rb+1]-D[Lb]<=W)
            AddLine(++Rb);
        if (Treap_root->m>MaxAns)
            MaxAns=Treap_root->m;
        RemoveLine(Lb++);
    }
}

void solve()
{
    discrete();
    scanx();
    printf("%d",MaxAns);
}

int main()
{
    init();
    solve();
    return 0;
}
<h2><span class="mw-headline">金礦 </span></h2>

問題描述

金礦的老師傅年底要退休了。經理爲了獎賞他的盡職盡責的工作,決定在一塊包含 n(n ≤ 15000) 個採金點的長方形土地中劃出一塊長度爲 S ,寬度爲 W 的區域獎勵給他(1 ≤ s , w ≤ 10 000)。老師傅可以自己選擇這塊地的位置,顯然其 中包含的採金點越多越好。你的任務就是計算最多能得到多少個採金點。如果一個採金點的位置在長方形的邊上,它也應當被計算在內。

輸入格式

輸入文件的第一行有兩個整數,中間用一個空格隔開,表示長方形土地的長和寬即s和w(1&lt;=s,w&lt;=10 000)。第二行有一個整數n(1&lt;=n&lt;=15 000),表示金礦數量。下面的n行與金礦相對應,每行兩個整數x和y (-30 000&lt;=x,y&lt;=30 000),中間用一個空格隔開,表示金礦的座標。

輸出格式

輸出文件只有一個整數,表示選擇的最大金礦的數。

輸入樣例
1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2
輸出樣例
4

相關日誌