SPOJ QTREE 1-3例题
SPOJ QTREE 1-3题解
QTREE3：
昨天刷了几道QTREE，感觉码长萌萌哒；
然而因为本人太弱刷不动QTREE4，动态点分治并没有理解上去的能力；
于是暂且弃疗啦，在这里写点题解扔点代码吧；
QTREE1
题意：
给出一个有边权的树；
操作一：改变某条边权；
操作二：查询两点之间路径上最大边权；
题解：
树链剖分的姿势还是挺裸的，想了想没有什么好办法码了一发；
普通的树链剖分维护树上路径，加一个线段树，时间复杂度O(nlog^2n)；
QTREE2
题意：
给出一个有边权的树；
操作一：查询两点之间路径长度；
操作二：查询两点之间路径上经过的第K个点；
题解：
因为是无修的，操作一可以方便的用倍增LCA搞；
操作二在跑过一次LCA之后，YY一下也就是从某个点向上K步之类的东西；
时间复杂度O(nlogn)，手滑打错一个字母调了好久；
QTREE3
题意：
给出一个有点权的树；
每次查询某个点子树中第K小点权是哪个点；
题解：
操作只有一种，子树维护直接在DFS序上就可以了；
第K大用主席树来维护，时间复杂度O(nlogn)，空间复杂度O(nlogn)；
SPOJ的1.5G内存真是太爽啦 (然后到BZOJ上就MLE了)；
代码：
QTREE1：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#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[top[y]])
swap(x,y);
ret=max(ret,query(1,n,1,p[top[x]],p[x]));
x=fa[top[x]];
}
if(deep[x]<deep[y])
swap(x,y);
if(x!=y)
ret=max(ret,query(1,n,1,p[son[y]],p[x]));
return ret;
}
int main()
{
int c,T,i,j,k,x,y,v;
scanf("%d",&T);
for(c=1;c<=T;c++)
{
scanf("%d",&n);
init();
for(i=1;i<n;i++)
{
scanf("%d%d%d",X+i,Y+i,V+i);
add(X[i],Y[i],V[i]),add(Y[i],X[i],V[i]);
}
dfs1(1);
dfs2(1,0);
for(i=1;i<n;i++)
X[i]=deep[X[i]]>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\n",find(x,y));
}
}
}
return 0;
}
QTREE2：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#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-1];i++)
fa[x][i]=fa[fa[x][i-1]][i-1],
dis[x][i]=dis[x][i-1]+dis[fa[x][i-1]][i-1];
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]<deep[y])
swap(x,y);
int t=15,ret=0;
while(t>=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<<t),tx=fa[tx][t];
t--;
}
}
else
{
while(t>=0)
{
if(deep[fa[ty][t]]>=deep[tx])
rety+=(1<<t),ty=fa[ty][t];
t--;
}
}
if(tx!=ty)
{
t=15;
while(t>=0)
{
if(fa[tx][t]!=fa[ty][t])
retx+=(1<<t),tx=fa[tx][t],
rety+=(1<<t),ty=fa[ty][t];
t--;
}
retx++,rety++;
}
if(retx+rety+1<k) return -1;
if(retx>=k-1)
{
k--;
t=15;
while(t>=0)
{
if(k&1<<t)
x=fa[x][t];
t--;
}
return x;
}
else
{
k=rety-k+retx+1;
t=15;
while(t>=0)
{
if(k&1<<t)
y=fa[y][t];
t--;
}
return y;
}
}
void init()
{
memset(head,0,sizeof(head));
memset(dis,0,sizeof(dis));
memset(fa,0,sizeof(fa));
ce=0;
}
int main()
{
int c,T,n,m,i,j,k,x,y,v;
scanf("%d",&T);
for(c=1;c<=T;c++)
{
init();
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&v);
add(x,y,v),add(y,x,v);
}
dfs(1);
while(scanf("%s",op)!=EOF&&op[1]!='O')
{
if(op[1]=='I')
{
scanf("%d%d",&x,&y);
printf("%d\n",DIST(x,y));
}
else
{
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",KTH(x,y,k));
}
}
}
return 0;
}
QTREE3：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#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-1];
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<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&k);
printf("%d\n",which[query(1,n,root[L[x]-1],root[R[x]],k)]);
}
return 0;
}