SPOJ QTREE 1-3題解
來源：程序員人生 發布時間：2016-03-10 14:33:18 閱讀次數：2520次
昨天刷了幾道QTREE，感覺碼長萌萌噠；
但是由于本人太弱刷不動QTREE4，動態點分治并沒有理解上去的能力；
因而暫且棄療啦，在這里寫點題解扔點代碼吧；
QTREE1
題意：
給出1個有邊權的樹；
操作1：改變某條邊權；
操作2：查詢兩點之間路徑上最大邊權；
題解：
樹鏈剖分的姿式還是挺裸的，想了想沒有甚么好辦法碼了1發；
普通的樹鏈剖分保護樹上路徑，加1個線段樹，時間復雜度O(nlog^2n)；
QTREE2
題意：
給出1個有邊權的樹；
操作1：查詢兩點之間路徑長度；
操作2：查詢兩點之間路徑上經過的第K個點；
題解：
由于是無修的，操作1可以方便的用倍增LCA弄；
操作2在跑過1次LCA以后，YY1下也就是從某個點向上K步之類的東西；
時間復雜度O(nlogn)，手滑打錯1個字母調了好久；
QTREE3
題意：
給出1個有點權的樹；
每次查詢某個點子樹中第K小點權是哪一個點；
題解：
操作只有1種，子樹保護直接在DFS序上就能夠了；
第K大用主席樹來保護，時間復雜度O(nlogn)，空間復雜度O(nlogn)；
SPOJ的1.5G內存真是太爽啦 (然后到BZOJ上就MLE了)；
代碼：
QTREE1：
#include
#include
#include#define N 11000
#define lson l,mid,no<<1 #define rson mid+1,r,no<<1|1 using namespace std; int next[N<<1],to[N<<1],len[N<<1],head[N],ce; int n,X[N],Y[N],V[N]; int val[N],deep[N],fa[N],size[N],son[N],top[N],p[N],tot; int ma[N<<2]; char op[20]; void Pushup(int no) { ma[no]=max(ma[no<<1],ma[no<<1|1]); } void update(int l,int r,int no,int k,int val) { if(l==r) ma[no]=val; else { int mid=l+r>>1;
if(k<=mid) update(lson,k,val); else update(rson,k,val); Pushup(no); } } int query(int l,int r,int no,int st,int en) { if(st<=l&&r<=en) return ma[no]; else { int mid=l+r>>1;
if(en<=mid) return query(lson,st,en); else if(st>mid) return query(rson,st,en);
else return max(query(lson,st,en),query(rson,st,en));
}
}
void add(int x,int y,int v)
{
to[++ce]=y;
len[ce]=v;
next[ce]=head[x];
head[x]=ce;
}
void dfs1(int x)
{
deep[x]=deep[fa[x]]+1;
size[x]=1;
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa[x])
{
fa[to[i]]=x;
val[to[i]]=len[i];
dfs1(to[i]);
size[x]+=size[to[i]];
if(size[to[i]]>size[son[x]])
son[x]=to[i];
}
}
}
void dfs2(int x,int t)
{
top[x]=t;
p[x]=++tot;
update(1,n,1,p[x],val[x]);
if(son[x])
dfs2(son[x],t);
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
void init()
{
memset(head,0,sizeof(head));
memset(son,0,sizeof(son));
ce=tot=0;
}
int find(int x,int y)
{
int ret=0;
while(top[x]!=top[y])
{
if(deep[top[x]]deep[Y[i]]?X[i]:Y[i];
while(scanf("%s",op)!=EOF&&op[0]!=D)
{
scanf("%d%d",&x,&y);
if(op[0]==C)
{
val[X[x]]=y;
update(1,n,1,p[X[x]],y);
}
else
{
printf("%d
",find(x,y));
}
}
}
return 0;
}
QTREE2：
#include
#include
#include#define N 110000
using namespace std;
int next[N<<1],to[N<<1],val[N<<1],head[N],ce; int fa[N][20],dis[N][20],deep[N]; char op[20]; void add(int x,int y,int v) { to[++ce]=y; val[ce]=v; next[ce]=head[x]; head[x]=ce; } void dfs(int x) { int i; deep[x]=deep[fa[x][0]]+1; for(i=1;fa[x][i⑴];i++) fa[x][i]=fa[fa[x][i⑴]][i⑴], dis[x][i]=dis[x][i⑴]+dis[fa[x][i⑴]][i⑴]; for(i=head[x];i;i=next[i]) { if(to[i]!=fa[x][0]) { fa[to[i]][0]=x; dis[to[i]][0]=val[i]; dfs(to[i]); } } } int DIST(int x,int y) { if(deep[x]=0)
{
if(deep[fa[x][t]]>=deep[y])
ret+=dis[x][t],x=fa[x][t];
t--;
}
if(x==y) return ret;
t=15;
while(t>=0)
{
if(fa[x][t]!=fa[y][t])
ret+=dis[x][t],x=fa[x][t],
ret+=dis[y][t],y=fa[y][t];
t--;
}
return ret+dis[x][0]+dis[y][0];
}
int KTH(int x,int y,int k)
{
int t=15,retx=0,rety=0,tx=x,ty=y;
if(deep[tx]>deep[ty])
{
while(t>=0)
{
if(deep[fa[tx][t]]>=deep[ty])
retx+=(1<=0)
{
if(deep[fa[ty][t]]>=deep[tx])
rety+=(1<=0)
{
if(fa[tx][t]!=fa[ty][t])
retx+=(1<=k⑴)
{
k--;
t=15;
while(t>=0)
{
if(k&1<=0)
{
if(k&1<
QTREE3：
#include
#include
#include#define N 110000
#define M 10000000
#define lson l,mid,ls[no]
#define rson mid+1,r,rs[no]
using namespace std;
int next[N<<1],to[N<<1],head[N],ce; int val[N],dis[N],which[N]; int n,L[N],R[N],tim; int size[M],ls[M],rs[M],root[N],tot; void Insert(int l,int r,int &no,int val) { int p=++tot; ls[p]=ls[no],rs[p]=rs[no],size[p]=size[no]; no=p; size[no]++; if(l==r) return ; int mid=l+r>>1;
if(val<=mid) Insert(lson,val); else Insert(rson,val); } int query(int l,int r,int nol,int nor,int k) { if(l==r) return l; else { int mid=l+r>>1;
if(k<=size[ls[nor]]-size[ls[nol]]) return query(l,mid,ls[nol],ls[nor],k); else return query(mid+1,r,rs[nol],rs[nor],k-size[ls[nor]]+size[ls[nol]]); } } void add(int x,int y) { to[++ce]=y; next[ce]=head[x]; head[x]=ce; } void dfs(int x,int pre) { L[x]=++tim; root[tim]=root[tim⑴]; Insert(1,n,root[tim],val[x]); for(int i=head[x];i;i=next[i]) if(to[i]!=pre) dfs(to[i],x); R[x]=tim; } int main() { int m,i,j,k,x,y; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",val+i); dis[i]=val[i]; } sort(dis+1,dis+n+1); for(i=1;i<=n;i++) { val[i]=lower_bound(dis+1,dis+n+1,val[i])-dis; which[val[i]]=i; } for(i=1;i
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
