20140819 暑訓 資料結構與演算法

allenwhale

明天的投影片，有興趣可以先看看更新投影片錯誤

遊客，如果您要查看本帖隱藏內容請回復

[C++] 純文本查看 復制代碼

#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);
}

KD Tree可以參考 比投影片裡詳細

[C++] 純文本查看 復制代碼

#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[i]-tn.v[i])*(L.v[i]-tn.v[i]);
        }
        
        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);
                }
        }
}

visitorIKC

Thanks for the presentation.

林宇翔

                         謝謝

amoshuangyc

回。謝~

Brad

謝謝
來預習

lacy

jd3

^
OwO^
|

jd3

   ^           ^
        OwO

sma7

謝謝

domen111

我今天終於AC Treap啦! (感動)
可是怎麼覺得投影片裡面的code有bug? 還是只是我的寫法不同
1. sz預設應該是1
2. sz=SIZE(L)+SIZE(R)+1;
3. mn=max(num,max(MAXNUM(L),MAXNUM(R)));