bzoj 2648 SJY擺棋子

• 錢限題.題面可以看這裡.
• 若對每個點都算一遍距離,顯然 \(T\) 爆,在此思想基礎上使用 \(kd-tree\) 配合估價函數來剪枝效果較好.
• 具體來說,對于 \(kd-tree\) 上的一個節點,我們知道它這顆子樹所管轄的範圍,算出我們查詢的節點到這個範圍内可能的最小距離(下界),若這個距離都比目前記錄的答案劣或相等,再搜尋這顆子樹顯然沒有意義.
• 這樣就完成了最優性剪枝.
• 還有一個剪枝,若左子樹的距離下界小于右子樹的距離下界,則應先搜尋左子樹,否則先搜尋右子樹.
• 感性了解一下,若一個兒子的距離下界小,先搜尋它,答案更有可能變得更小,如果小于或等于了另一個兒子的距離下界,就沒有必要再搜另一個了
• 對于加點的操作,就和二叉搜尋樹一樣,從根節點往下,通過比較确定往哪邊走,走到适當的位置插入即可.疊代代替遞歸,常數較小,但要注意走的同時用新節點更新目前節點的資訊.
• 插入過多時,由于 \(kd-tree\) 無法進行旋轉操作保持平衡,樹高可能會變得很大,使其退化成鍊,有三種方法處理.
  • 1.記錄一個平衡因子 \(\alpha\) ,像替罪羊樹那樣,及時拍扁重構.這樣寫最穩定,時間上(應該是)最優的.
  • 2.不及時重構,每加入一定量的節點後對整棵樹重構,這個量大概在 \(10^4\) 級别,可自行調整.這樣寫不太穩定,但實作非常簡單,隻多了幾行.
  • 3.離線處理,将所有加點操作都讀進來,一開始就全部建好,給每個點加個标記表示是否已經被插入(可用),真正插入時修改标記.這種寫法不太推薦,每種操作都要額外考慮标記問題,比較繁瑣,而且在資瓷離線的情況下,使用一些離線算法,編寫難度和時間效率都遠勝于 \(kd-tree\) .

\(kd-tree\) 最近點問題下大概是 \(O(玄學)\) , 處理矩形問題下最壞是 \(O(kn^{1-\frac 1 k})\) ???不會證明,有 \(dalao\) 得到了證明或證僞麻煩告知...

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
    int x=0;
    bool pos=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
            pos=0;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
    return pos?x:-x;
}
const int MAXN=5e5+10;
int n,m,Dimen;
int rt,K=25000;
struct node{
    int v[2];
    int mi[2],ma[2];
    int ls,rs;
    bool operator < (const node &rhs) const
        {
            return v[Dimen]<rhs.v[Dimen]; 
        }
}Tree[MAXN<<1],A[MAXN<<1];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
#define inf 1e9
void init()
{
    for(int i=0;i<2;++i)
        {
            Tree[0].mi[i]=inf;
            Tree[0].ma[i]=-inf;
        }
}
inline void pushup(int o)
{
    for(int i=0;i<2;++i)
        {
            root.mi[i]=min(root.mi[i],min(lson.mi[i],rson.mi[i]));
            root.ma[i]=max(root.ma[i],max(lson.ma[i],rson.ma[i]));
        }
}
int BuildTree(int l,int r,int dimen)
{
    Dimen=dimen;
    int mid=(l+r)>>1;
    int o=mid;
    nth_element(A+l,A+mid,A+r+1);
    for(int i=0;i<2;++i)
        {
            root.v[i]=A[mid].v[i];
            root.mi[i]=root.ma[i]=root.v[i];
        }
    root.ls=root.rs=0;
    if(l<=mid-1)
        root.ls=BuildTree(l,mid-1,dimen^1);
    if(mid+1<=r)
        root.rs=BuildTree(mid+1,r,dimen^1);
    pushup(o);
    return o;
}
node querynode;
int ans;//最近距離 
int estimate(int o)//估計o到querynode的距離 
{
    if(!o)
        return inf;
    int res=0;
    for(int i=0;i<2;++i)
        {
            if(querynode.v[i]<root.mi[i])
                res+=root.mi[i]-querynode.v[i];
            else if(querynode.v[i]>root.ma[i])
                res+=querynode.v[i]-root.ma[i];
        }
    return res;
}
void query(int o)
{
    int dist=abs(root.v[0]-querynode.v[0])+abs(root.v[1]-querynode.v[1]);//實際距離 
    ans=min(ans,dist);
    int dl=estimate(root.ls),dr=estimate(root.rs);
    if(dl<dr)
        {
            if(dl<ans)
                query(root.ls);
            if(dr<ans)
                query(root.rs);
        }
    else
        {
            if(dr<ans)
                query(root.rs);
            if(dl<ans)
                query(root.ls);
        }
}
void Insert()//像平衡樹一樣,比較大小向下走,走到合适的地方接上 
{
    ++n;
    for(int i=0;i<2;++i)
        {
            A[n].v[i]=Tree[n].v[i]=read();
            Tree[n].mi[i]=Tree[n].ma[i]=Tree[n].v[i];
        }
    for(int o=rt,dimen=0;o;dimen^=1)
        {
            for(int i=0;i<2;++i)
                {
                    root.mi[i]=min(root.mi[i],Tree[n].mi[i]);
                    root.ma[i]=max(root.ma[i],Tree[n].ma[i]);
                }
            if(Tree[n].v[dimen]<root.v[dimen])
                {
                    if(root.ls)
                        o=root.ls;
                    else
                        {
                            root.ls=n;
                            return;
                        }
                }
            else
                {
                    if(root.rs)
                        o=root.rs;
                    else
                        {
                            root.rs=n;
                            return;
                        }
                }
        }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        for(int j=0;j<2;++j)
            A[i].v[j]=read();
    init();
    rt=BuildTree(1,n,0);
    while(m--)
        {
            int op=read();
            if(op==1)
                {
                    Insert();
                    if(n%K==0)
                        rt=BuildTree(1,n,0);
                }
            else
                {
                    querynode.v[0]=read();
                    querynode.v[1]=read();
                    ans=inf;
                    query(rt);
                    printf("%d\n",ans);
                }
        }
    return 0;
}                

轉載于:https://www.cnblogs.com/jklover/p/10406843.html