【GDOI2017模擬2.14】A

2019-11-08 18:46:08

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

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 這里寫圖片描述

題解

一開始想的是用一些神奇的離線方法做，想了半天之后發(fā)現(xiàn)這題是強(qiáng)制在線的QAQ 然后就看了一發(fā)題解，結(jié)果題解只有：主席樹入門題這幾個(gè)字(。??)ノ想了一會(huì)兒之后想到可以用權(quán)值線段樹對(duì)每個(gè)節(jié)點(diǎn)維護(hù)它到根節(jié)點(diǎn)路徑上點(diǎn)權(quán)值的分布情況于是就發(fā)現(xiàn)了用主席樹的方法

首先我們用主席樹預(yù)處理每一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)路徑的點(diǎn)權(quán)值的情況，然后每一次詢問一組(x,y)，我們就可以隨便倍增一下，然后主席樹快速算出兩點(diǎn)之間的點(diǎn)的分布情況就可以了

貼代碼

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 解題總結(jié)：124. Binary Tree Maximum Path Sum

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