本帖最後由 allenwhale 於 2014-12-16 03:03 編輯
明天的投影片，有興趣可以先看看更新投影片錯誤
[mw_shl_code=cpp,true]#include <stdio.h>
#define max(a,b) (a>b?a:b)
int a[100010];
struct seg
{
seg *L,*R;
int l,r;
int mx;
};
seg* build(int l,int r)
{
seg *tr;
if(l==r)
{
tr=new seg();
tr->l=tr->r=l;
tr->mx=a[l];
return tr;
}
int mid=(l+r)>>1;
tr->L=build(l,mid);
tr->R=build(mid+1,r);
tr->l=l,tr->r=r;
tr->mx=max(tr->L->mx,tr->R->mx);
return tr;
}
int query(seg *tr,int l,int r)
{
if(tr->l==l&&tr->r==r)
{
return tr->mx;
}
int mid=(l+r)>>1;
if(r<=mid)return query(tr->L,l,r);
else if(l>mid)return query(tr->R,l,r);
else return max(query(tr->L,l,mid),query(tr->R,mid+1,r));
}
void modify(seg *tr,int idx,int v)
{
if(tr->l==idx&&tr->r==idx)
{
tr->mx=v;
a[idx]=v;
return ;
}
int mid=(l+r)>>1;
if(idx<=mid)modify(tr->L,idx,v);
else modify(tr->R,idx,v);
}[/mw_shl_code]KD Tree可以參考 比投影片裡詳細
[mw_shl_code=cpp,true]#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXD10
#define MAXN 50010
int dim=10;
struct Node
{
int v[MAXD+1];
int num;
Node()
{
num=-1;
memset(v,0,sizeof(v));
}
bool operator < (const Node& a)const
{
return num<a.num;
}
}s[MAXN+1],s2[MAXN+1];
struct KD_tree
{
KD_tree *ltree,*rtree;
Node node;
KD_tree(Node _n=Node())
{
ltree=rtree=NULL;
node=_n;
}
};
int cmpd;
bool cmp(Node a,Node b)
{
return a.v[cmpd]<b.v[cmpd];
}
KD_tree* build(int l,int r,int d)
{
KD_tree *tr;
if(l==r)
{
tr=new KD_tree(s[l]);
return tr;
}
if(l>r)return NULL;
cmpd=d;
int mid=(l+r)>>1;
nth_element(s+l,s+mid,s+r+1,cmp);
tr=new KD_tree(s[mid]);
tr->ltree=build(l,mid-1,(d+1)%dim);
tr->rtree=build(mid+1,r,(d+1)%dim);
return tr;
}
typedef pair<int,Node> pdn;
priority_queue<pdn> pq;
int max_dis=0x3f3f3f3f;
void query(KD_tree *tr,int m,int d,Node L)
{
//printf("d = %d\n",d);
Node tn=tr->node;
int dis=0;
//printf("count %d\n",tn.num+1);
for(int i=0;i<dim;i++)
{
dis+=(L.v
-tn.v)*(L.v-tn.v);
}
if(tn.num==L.num)dis=0x3f3f3f3f;
//printf("dis = %d\n",dis);
if(dis<max_dis)
{
pq.push(make_pair(dis,tn));
if((int)pq.size()>m)
{
max_dis=pq.top().first;
pq.pop();
}
}
//printf("max_dis = %d\n",max_dis);
if(L.v[d]<tn.v[d])
{
if(tr->ltree)
{
query(tr->ltree,m,(d+1)%dim,L);
}
if(tr->rtree)
{
if((L.v[d]-tn.v[d])*(L.v[d]-tn.v[d])<=max_dis)
query(tr->rtree,m,(d+1)%dim,L);
}
}
else
{
if(tr->rtree)
{
query(tr->rtree,m,(d+1)%dim,L);
}
if(tr->ltree)
{
if((L.v[d]-tn.v[d])*(L.v[d]-tn.v[d])<=max_dis)
query(tr->ltree,m,(d+1)%dim,L);
}
}
}
[/mw_shl_code]
