【GDOI2017模拟2.14】A

2019-11-08 18:46:08

字体：大中小

来源：转载

供稿：网友

Description 这里写图片描述 Input

这里写图片描述 Sample Input

5 5 4 3 4 2 3 3 2 4 5 1 1 3 2 1 2 5 2 6 7 0 7 7 0 2 4 2 这里写图片描述 Sample Output

0 0 3 0 3 1 0 0 1 1 2 0

Data Constraint 这里写图片描述注意：Q<=300000

Hint 这里写图片描述

题解

一开始想的是用一些神奇的离线方法做，想了半天之后发现这题是强制在线的QAQ 然后就看了一发题解，结果题解只有：主席树入门题这几个字(。・・)ノ想了一会儿之后想到可以用权值线段树对每个节点维护它到根节点路径上点权值的分布情况于是就发现了用主席树的方法

首先我们用主席树预处理每一个节点到根节点路径的点权值的情况，然后每一次询问一组(x,y)，我们就可以随便倍增一下，然后主席树快速算出两点之间的点的分布情况就可以了

贴代码

var tree:array[0..6000005,1..3]of longint; a,b:array[0..600005,1..2]of longint; bz:array[0..300005]of boolean; cc,root,fa,deep:array[0..300005]of longint; ff:array[0..300005,0..19]of longint; i,j,k,l,m,n,x,y,z,p,last,tmp,t,xx,yy,q:longint; tt:array[0..3]of longint;PRocedure qsort(l,r:longint);var i,j,mid:longint;begin i:=l; j:=r; mid:=a[(i+j) div 2,1]; repeat while a[i,1]<mid do inc(i); while a[j,1]>mid do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j);end;procedure star;begin b[a[1,1],1]:=1; for i:=2 to n*2-2 do if a[i,1]<>a[i-1,1] then begin b[a[i-1,1],2]:=i-1; b[a[i,1],1]:=i; end; b[a[i,1],2]:=i;end;procedure make_ff;var i,j:longint;begin for j:=1 to 18 do for i:=1 to n do ff[i,j]:=ff[ff[i,j-1],j-1];end;procedure maketree(var num,x:longint;l,r:longint);var mid:longint;begin tree[p]:=tree[x]; inc(tree[p,3]); x:=p; inc(p); if l=r then exit; mid:=(l+r) div 2; if num<=mid then maketree(num,tree[x,1],l,mid) else maketree(num,tree[x,2],mid+1,r);end;procedure find(v1,v2,l,r,x,y,z:longint);var mid:longint;begin if (l=x) and (r=y) then tt[z]:=tt[z]+tree[v2,3]-tree[v1,3] else begin mid:=(l+r) div 2; if y<=mid then find(tree[v1,1],tree[v2,1],l,mid,x,y,z) else if x>mid then find(tree[v1,2],tree[v2,2],mid+1,r,x,y,z) else begin find(tree[v1,1],tree[v2,1],l,mid,x,mid,z); find(tree[v1,2],tree[v2,2],mid+1,r,mid+1,y,z); end; end;end;procedure dfs(x:longint);var i:longint;begin bz[x]:=true; for i:=b[x,1] to b[x,2] do if (i<>0) and (bz[a[i,2]]=false) then begin fa[a[i,2]]:=x; ff[a[i,2],0]:=x; deep[a[i,2]]:=deep[x]+1; root[a[i,2]]:=root[x]; maketree(cc[a[i,2]],root[a[i,2]],1,m); dfs(a[i,2]); end;end;begin //assign(input,'jzoj4969.in'); reset(input); assign(input,'a.in'); reset(input); assign(output,'a.out'); rewrite(output); readln(n,m,q); for i:=1 to n do read(cc[i]); readln; for i:=1 to n-1 do begin readln(a[i,1],a[i,2]); a[n+i-1,1]:=a[i,2]; a[n+i-1,2]:=a[i,1]; end; qsort(1,n*2-2); star; p:=1; maketree(cc[1],root[1],1,m); deep[1]:=1; dfs(1); make_ff; for i:=1 to q do begin readln(x,y,z); x:=x xor last; y:=y xor last; z:=z xor last; xx:=x; yy:=y; if deep[y]>deep[x] then begin tmp:=x; x:=y; y:=tmp; end; k:=deep[x]; for j:=18 downto 0 do if k-1<<j>=deep[y] then begin k:=k-1<<j; x:=ff[x,j]; end; for j:=18 downto 0 do if ff[x,j]<>ff[y,j] then begin x:=ff[x,j]; y:=ff[y,j]; end; if x<>y then x:=ff[x,0]; fillchar(tt,sizeof(tt),0); if z>1 then begin find(root[x],root[xx],1,m,1,z-1,1); find(root[x],root[yy],1,m,1,z-1,1); end; find(root[x],root[xx],1,m,z,z,2); find(root[x],root[yy],1,m,z,z,2); if z<m then begin find(root[x],root[xx],1,m,z+1,m,3); find(root[x],root[yy],1,m,z+1,m,3); end; if cc[x]<z then inc(tt[1]) else if cc[x]=z then inc(tt[2]) else inc(tt[3]); last:=tt[1] xor tt[2]; last:=last xor tt[3]; writeln(tt[1],' ',tt[2],' ',tt[3]); end; close(input); close(output);end.

上一篇：leecode 解题总结：124. Binary Tree Maximum Path Sum

下一篇：LintCode Kth Smallest Number in A Unsorted Array