SPOJ QTREE 1-3题解
来源：程序员人生 发布时间：2016-03-10 14:33:18 阅读次数：2314次
昨天刷了几道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
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
