資料(CDQ分治+樹狀數組）

時間限制：3秒  記憶體限制：128M

【問題描述】

　　為了寫論文，Alex 經常要整理大量的資料。這一次，Alex 面臨一個嚴峻的考驗：他需要實作一個資料結構來維護一個點集。現在，二維平面上有N 個點。Alex 需要實作以下三種操作：

　　1. 在點集裡添加一個點；

　　2. 給出一個點，查詢它到點集裡所有點的曼哈頓距離的最小值；

　　3. 給出一個點，查詢它到點集裡所有點的曼哈頓距離的最大值。

　　兩個點的曼哈頓距離定義為它們的橫坐标差的絕對值與縱坐标差的絕對值的和。這麼困難的問題，Alex 當然不會做，隻好再次請你幫忙了。

【輸入格式】

　　第一行包含一個整數N，表示點集最初的點數。

　　接下來N 行，每行兩個整數，依次表示每個點的橫坐标和縱坐标。

　　第N+2 行包含一個整數Q，表示詢問的數目。

　　接下來Q 行，每行三個整數，依次表示詢問的類型，點的橫坐标和縱坐标。0 類型表示添加一個點，1 類型表示查詢到該點的曼哈頓距離的最小值，2 類型表示查詢最大值。

【輸出格式】

輸出若幹行，依次表示每個查詢操作的答案。

【輸入樣例】

7 5

6 2

3 1

1 6 1

1 5 5

2 7 1

0 3 2

1 1 0

【輸出樣例】

【資料範圍】

30%的資料：1 ≤ N, Q ≤ 1,000；

60%的資料：1 ≤ N, Q ≤ 40,000；

有30%的資料滿足沒有添加點的操作；

100%的資料：1 ≤ N, Q ≤ 100,000，點的坐标是不超過10^9的非負整數。

這道題開始做的時候打了個樹套樹，結果算了一下，又爆記憶體又逾時,畢竟我用的線段樹套線段樹（其實套平衡樹就不爆記憶體了）。

正解應該是用CDQ分治的思想。

關于CDQ的詳細内容

我們可以直接把開始有的n個點看做是操作1，然後重要的就是合并的時候，前面對後面的影響了。

我們要求的是一個帶絕對值的式子，我們可以分4種情況來去掉絕對值，去掉後我們就會發現每種情況都可以直接用一個樹狀數組來記錄。

詳細的記錄方法見代碼注釋：

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const ll inf=ll;

struct shu
{
    ll x,y,id,ans,name;
    friend bool operator <(shu a,shu b)
    {
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
    }
}a[maxn];

bool cmp(shu a,shu b){
    return a.name<b.name;
}

ll bx[maxn],by[maxn],bit[maxn][];
int totx,toty,n,m;

ll lowbit(ll x){
    return x&(-x);
}

void in(ll x,ll t){
    while(x<=toty)
    {
        bit[x][]=min(bit[x][],t);
        bit[x][]=max(bit[x][],t);
        x+=lowbit(x);
    }
}

ll findmin(ll x){
    ll ans=inf;
    while(x)
    {
        ans=min(bit[x][],ans);
        x-=lowbit(x);
    }
    return ans;
}

ll findmax(ll x){
    ll ans=-inf;
    while(x)
    {
        ans=max(bit[x][],ans);
        x-=lowbit(x);
    }
    return ans;
}

void out(ll x){
    while(x<=toty)
    {
        bit[x][]=inf;
        bit[x][]=-inf;
        x+=lowbit(x);
    }
}

ll read(){
    ll x=;
    char ch=getchar();
    while(ch<''||ch>'') ch=getchar();
    while(ch>=''&&ch<='')
    {
        x=x*+ch-'';
        ch=getchar();
    }
    return x;
}

void init()
{
    n=read();
    for(int i=;i<=n;i++)
    {
        a[i].x=read();a[i].y=read();a[i].id=0;
        bx[i]=a[i].x;
        by[i]=a[i].y;
        a[i].name=i;
    }
    m=read();
    for(int i=;i<=m;i++)
    {
        a[i+n].id=read();a[i+n].x=read();a[i+n].y=read();
        bx[i+n]=a[i+n].x;
        by[i+n]=a[i+n].y;
        if(a[i+n].id==) a[i+n].ans=inf;
        if(a[i+n].id==) a[i+n].ans=-inf;
        a[i+n].name=i+n;
    }
    sort(bx+,bx++n+m);
    sort(by+,by++n+m);
    totx=toty=;
    for(int i=;i<=n+m;i++) 
    {
        if(bx[i]!=bx[i-]) bx[++totx]=bx[i];
        if(by[i]!=by[i-]) by[++toty]=by[i];
    }
    for(int i=;i<=n+m;i++)
    {
        a[i].x=lower_bound(bx+,bx+totx+,a[i].x)-bx;
        a[i].y=lower_bound(by+,by+toty+,a[i].y)-by;
    }
    for(int i=;i<=toty;i++)
    bit[i][]=inf,bit[i][]=-inf;
}

void work(int l,int r)
{
    if(l==r||r<=n) return;
    int m=(l+r)>>;
    work(l,m);
    work(m+,r);
    sort(a+l,a+m+);
    sort(a+m+,a+r+);
    //  x1-x2+y1-y2
    int t=l;
    for(int i=m+;i<=r;i++)if(a[i].id>0)
    {
        while(t<=m&&a[t].x<=a[i].x)
        {
        //記錄x2+y2的值，我們保證了x2<=x1就直接在樹狀數組上查詢y1前的值就可以了.
            if(a[t].id==) in(a[t].y,bx[a[t].x]+by[a[t].y]);
            t++;
        }
        if(a[i].id==) a[i].ans=min(a[i].ans,bx[a[i].x]+by[a[i].y]-findmax(a[i].y));
        else a[i].ans=max(a[i].ans,bx[a[i].x]+by[a[i].y]-findmin(a[i].y));
    }
    t--;
    while(t>=l)
    {
        if(a[t].id==) out(a[t].y);
        t--;
    }
    // x1-x2+y2-y1
    t=l;
    for(int i=m+;i<=r;i++)if(a[i].id>0)
    {
        while(t<=m&&a[t].x<=a[i].x)
        {
        //記錄x2-y2的值，這裡的y2要大于y1,是以我們就用toty+-y來當下表好用樹狀數組，剩下種情況差不多，就留着讀者體會了，不懂可以回複
            if(a[t].id==) in(toty+-a[t].y,bx[a[t].x]-by[a[t].y]);
            t++;
        }
        if(a[i].id==) a[i].ans=min(a[i].ans,bx[a[i].x]-by[a[i].y]-findmax(toty+-a[i].y));
        else a[i].ans=max(a[i].ans,bx[a[i].x]-by[a[i].y]-findmin(toty+-a[i].y));
    }
    t--;
    while(t>=l)
    {
        if(a[t].id==) out(toty+-a[t].y);
        t--;
    }
    //
    t=m;
    for(int i=r;i>m;i--)if(a[i].id>0)
    {
        while(t>=l&&a[t].x>=a[i].x)
        {
            if(a[t].id==) in(toty+-a[t].y,bx[a[t].x]+by[a[t].y]);
            t--;
        }
        if(a[i].id==) a[i].ans=min(a[i].ans,findmin(toty+-a[i].y)-bx[a[i].x]-by[a[i].y]);
        else a[i].ans=max(a[i].ans,findmax(toty+-a[i].y)-bx[a[i].x]-by[a[i].y]);
    }
    t++;
    while(t<=m)
    {
        if(a[t].id==) out(toty+-a[t].y);
        t++;
    }
    //
    t=m;
    for(int i=r;i>m;i--)if(a[i].id>0)
    {
        while(t>=l&&a[t].x>=a[i].x)
        {
            if(a[t].id==) in(a[t].y,bx[a[t].x]-by[a[t].y]);
            t--;
        }
        if(a[i].id==) a[i].ans=min(a[i].ans,findmin(a[i].y)-bx[a[i].x]+by[a[i].y]);
        else a[i].ans=max(a[i].ans,findmax(a[i].y)-bx[a[i].x]+by[a[i].y]);
    }
    t++;
    while(t<=m)
    {
        if(a[t].id==) out(a[t].y);
        t++;
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    init();
    work(,n+m);
    sort(a+,a+n+m+,cmp);
    for(int i=n+;i<=n+m;i++)if(a[i].id>0)
    printf("%d\n",(int)a[i].ans);
    return ;
}

再外送一個我的樹套樹做法，雖然什麼都超，但如果沒辦法了還是可以用的，畢竟還是有70分的。

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
const int inf=;

struct shu
{
    int x,y,id;
}a[maxn];
int lc[maxn*],rc[maxn*],cnt=,root[maxn*],root1=;
int lt[maxn*],rt[maxn*],cnt2=;
ll minv[maxn*][],maxv[maxn*][];
ll bx[maxn],by[maxn];
int n,m,totx,toty;

void buid(int &now,int l,int r){
    now=++cnt;
    if(l==r) return;
    int m=(l+r)>>;
    buid(lc[now],l,m);
    buid(rc[now],m+,r);
}

void up(int now){
    for(int i=;i<;i++)
    {
        minv[now][i]=min(minv[lt[now]][i],minv[rt[now]][i]);
        maxv[now][i]=max(maxv[lt[now]][i],maxv[rt[now]][i]);
    }
}

void add(int &now,int l,int r,int x,int y){
    if(!now) now=++cnt2;
    if(l==r)
    {
        minv[now][]=min(minv[now][],bx[x]+by[y]);
        maxv[now][]=max(maxv[now][],bx[x]+by[y]);
        minv[now][]=min(minv[now][],bx[x]-by[y]);
        maxv[now][]=max(maxv[now][],bx[x]-by[y]);
        return;
    }
    int m=(l+r)>>;
    if(y<=m) add(lt[now],l,m,x,y);
    else add(rt[now],m+,r,x,y);
    up(now);
}

void in(int now,int l,int r,int x,int y){
    add(root[now],,toty,x,y);
    if(l==r) return;
    int m=(l+r)>>;
    if(x<=m) in(lc[now],l,m,x,y);
    else in(rc[now],m+,r,x,y);
}

ll read(){
    ll x=;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=x*+ch-'0';
        ch=getchar();
    }
    return x;
}

void init(){
    n=read();
    for(int i=;i<=n;i++)
    {
        a[i].x=read();a[i].y=read();
        bx[i]=a[i].x;
        by[i]=a[i].y;
    }
    m=read();
    for(int i=;i<=m;i++)
    {
        a[i+n].id=read();a[i+n].x=read();a[i+n].y=read();
        bx[i+n]=a[i+n].x;
        by[i+n]=a[i+n].y;
    }
    sort(bx+,bx++n+m);
    sort(by+,by++n+m);
    totx=toty=;
    for(int i=;i<=n+m;i++) 
    {
        if(bx[i]!=bx[i-]) bx[++totx]=bx[i];
        if(by[i]!=by[i-]) by[++toty]=by[i];
    }
    for(int i=;i<=n+m;i++)
    {
        a[i].x=lower_bound(bx+,bx+totx+,a[i].x)-bx;
        a[i].y=lower_bound(by+,by+toty+,a[i].y)-by;
    }
    buid(root1,,totx);
    for(int i=;i<maxn*;i++)
    {
        maxv[i][]=maxv[i][]=-inf;
        minv[i][]=minv[i][]=inf;
    }
}

int max0(int now,int l,int r,int x,int y,int id){
    if(!now||l>=y) 
    {
        if(id) return maxv[now][];
        return minv[now][];
    }
    int m=(l+r)>>;
    ll t1,t2;
    if(id) t1=t2=-inf;
    else t1=t2=inf;
    if(m>=y) t2=max0(lt[now],l,m,x,y,id);
    t1=max0(rt[now],m+,r,x,y,id);
    if(id) return max(t1,t2);
    return min(t1,t2);
}

int find0max(int now,int l,int r,int x,int y,int id){
    if(l>=x) return max0(root[now],,toty,x,y,id);
    int m=(l+r)>>;
    ll t1,t2;
    if(id) t1=t2=-inf;
    else t1=t2=inf;
    if(m>=x) t2=find0max(lc[now],l,m,x,y,id);
    t1=find0max(rc[now],m+,r,x,y,id);
    if(id) return max(t1,t2);
    return min(t1,t2);
}

int max1(int now,int l,int r,int x,int y,int id){
    if(!now||r<=y) 
    {
        if(id) return maxv[now][];
        return minv[now][];
    }
    int m=(l+r)>>;
    ll t1,t2;
    if(id) t1=t2=-inf;
    else t1=t2=inf;
    t2=max1(lt[now],l,m,x,y,id);
    if(m<y) t1=max1(rt[now],m+,r,x,y,id);
    if(id) return max(t1,t2);
    return min(t1,t2);
}

int find1max(int now,int l,int r,int x,int y,int id){
    if(l>=x) return max1(root[now],,toty,x,y,id);
    int m=(l+r)>>;
    ll t1,t2;
    if(id) t1=t2=-inf;
    else t1=t2=inf;
    if(m>=x) t2=find1max(lc[now],l,m,x,y,id);
    t1=find1max(rc[now],m+,r,x,y,id);
    if(id) return max(t1,t2);
    return min(t1,t2);
}

ll min0(int now,int l,int r,int x,int y,int id){
    if(!now||r<=y) 
    {
        if(!id) return maxv[now][];
        return minv[now][];
    }
    int m=(l+r)>>;
    ll t1,t2;
    if(!id) t1=t2=-inf;
    else t1=t2=inf;
    t2=min0(lt[now],l,m,x,y,id);
    if(m<y) t1=min0(rt[now],m+,r,x,y,id);
    if(!id) return max(t1,t2);
    return min(t1,t2);
}

ll find0min(int now,int l,int r,int x,int y,int id){
    if(r<=x) return min0(root[now],,toty,x,y,id);
    int m=(l+r)>>;
    ll t1,t2;
    if(!id) t1=t2=-inf;
    else t1=t2=inf;
    t2=find0min(lc[now],l,m,x,y,id);
    if(m<x) t1=find0min(rc[now],m+,r,x,y,id);
    if(!id) return max(t1,t2);
    return min(t1,t2);
}

ll min1(int now,int l,int r,int x,int y,int id){
    if(!now||l>=y) 
    {
        if(!id) return maxv[now][];
        return minv[now][];
    }
    int m=(l+r)>>;
    ll t1,t2;
    if(!id) t1=t2=-inf;
    else t1=t2=inf;
    if(m>=y) t2=min1(lt[now],l,m,x,y,id);
    t1=min1(rt[now],m+,r,x,y,id);
    if(!id) return max(t1,t2);
    return min(t1,t2);
}

ll find1min(int now,int l,int r,int x,int y,int id){
    if(r<=x) return min1(root[now],,toty,x,y,id);
    int m=(l+r)>>;
    int t1,t2;
    if(!id) t1=t2=-inf;
    else t1=t2=inf;
    t2=find1min(lc[now],l,m,x,y,id);
    if(m<x) t1=find1min(rc[now],m+,r,x,y,id);
    if(!id) return max(t1,t2);
    return min(t1,t2);
}

int find(int x,int y,int id)
{
    ll t1,t2,t3,t4,t,tt;
    t1=find0max(root1,,totx,x,y,id)-bx[x]-by[y];
    t2=find1max(root1,,totx,x,y,id)-bx[x]+by[y];
    t3=bx[x]+by[y]-find0min(root1,,totx,x,y,id);
    t4=bx[x]-by[y]-find1min(root1,,totx,x,y,id);
    /*if(id) t=-1;
    else t=inf;
    if(t1<0||t1>inf) t1=t;
    if(t2<0||t2>inf) t2=t;
    if(t3<0||t3>inf) t3=t;
    if(t4<0||t4>inf) t4=t;*/
    if(id) return max(max(t1,t2),max(t3,t4));
    return min(min(t1,t2),min(t3,t4));
}

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    init();
    for(int i=;i<=n;i++)
    in(root1,,totx,a[i].x,a[i].y);
    for(int i=n+;i<=n+m;i++)
    {
        if(a[i].id==) in(root1,,totx,a[i].x,a[i].y);
        if(a[i].id==) printf("%d\n",find(a[i].x,a[i].y,));
        if(a[i].id==) printf("%d\n",find(a[i].x,a[i].y,));
    }
    return ;
}

資料(CDQ分治+樹狀數組）

繼續閱讀

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

詳解STM32單片機的堆棧

Linux裝置模型（中）之上層容器