主席树 莫队

[SDOI2018]原题识别

Posted by Dispwnl on April 9, 2019

题目

题目描述

“人肉题库” 小 $Q$ 刷题非常勤奋，题量破万。每当有人拿题目请教他时，小 $Q$ 总能在 $1$ 秒内报出这 是哪个 $OJ$ 的哪道题。因此，小 $Q$ 是被当作 “原题搜索机” 一样的存在。

有一天，小 $Q$ 来到了一棵 $n$ 个节点的有根树下，这棵树的根节点为 $1$ 号点，且每个节点都印着一道 题目。凭借超大的题量，小 $Q$ 迅速识别出了每道题的来源，并发现有些题目被搬运了好多次。他把每个 节点的题目都做了一个分类，第 $i$ 个节点的题目对应的题目种类为 $a_i$，当且仅当 $a_i=a_j$ 时，$i$ 点和 $j$点的题目来源是相同的。

同一道题目做多次除了增加 $AC$ 数以外，对本身的水平没有任何提高。为了调查这棵树的题目质量， 小 $Q$ 会不断提出以下两种询问共 $m$ 次：

  • $1$ $x$ $y$：如果将 $x$ 点到 $y$ 点的最短路径上的所有点 (包括 $x$ 和 $y$) 对应的题目都做一遍，那么一共可 以做到多少道本质不同的题目？
  • $2$ $A$ $B$：如果在 $A$ 点到根的最短路径上 (包括 $A$ 点和根) 等概率随机选择一个点 $x$，在 $B$ 点到根的最短路径上 (包括 $B$ 点和根) 等概率随机选择一个点 $y$，那么询问 $1$ $x$ $y$ 的答案期望是多少？

定义 $cnt_x$ 表示 $x$ 点到根最短路径上的节点个数，因为小 $Q$ 不喜欢分数，而且第 $2$ 类询问的答案一 定可以表示成$\frac{ans}{cnt_A*cnt_B}$的形式，你只需要告诉他 $ans$ 的值就可以了。

识别这些题目消耗了小 $Q$ 太大的精力，他没有办法自己去计算这些简单的询问的答案。请写一个程序回答小 $Q$ 的所有 $m$ 个问题。

输入输出格式

输入格式：

第一行包含一个正整数 $T$，表示测试数据的组数。 每组数据第一行包含 $5$ 个正整数 $n, p, SA, SB, SC$，其中 $n$ 表示树的节点个数。

为了在某种程度上减少输入量，树边和每个点的题目种类 $a[]$ 将由以下代码生成：

unsigned int SA, SB, SC;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%u%u%u", &n, &p, &SA, &SB, &SC);
    for(int i = 2; i <= p; i++)
    addedge(i - 1, i);
    for(int i = p + 1; i <= n; i++)
    addedge(rng61() % (i - 1) + 1, i);
    for(int i = 1; i <= n; i++)
    a[i] = rng61() % n + 1;
}

第二行包含一个正整数 $m$，表示询问次数。

接下来 $m$ 行，每行 $3$ 个正整数，形式为 $1$ $x$ $y$ 或者 $2$ $A$ $B$依次表示每个询问。

输出格式：

对于每组数据，输出 $m$ 行，每行一个整数，依次回答每个询问。

输入输出样例

输入样例#1：

2
5 3 10000 12345 54321
3
1 2 3
2 1 3
1 3 2
10 6 23456 77777 55555
5
1 1 10
2 3 5
2 7 5
2 5 4
1 8 6

输出样例#1：

1
5
1
4
34
61
45
3

说明

$-1 ≤ T ≤ 3,2 ≤ p ≤ n ≤ 100000,1 ≤ m ≤ 200000\;-10000 ≤ SA, SB, SC ≤ 1000000,1 ≤ x, y, A, B ≤ n$

子任务 $1$（$30$ 分）：只含第 $1$ 类询问。

子任务 $2$（$30$ 分）：满足 $p = n$。

子任务 $3$（$40$ 分）：没有任何附加的限制。

题解

因为有几个变量是l_l,l_r,r_l,r_r

昊哥指着l_r说这不海鸥吗

昊哥指着l_l,r_r说这是顺拐的海鸥

r_l就是内八字的海鸥了

首先子任务$1$就是个树上莫队

第$2$类询问先考虑在链上的情况，设查询$x,y$的答案且$x$是$y$的祖先

考虑计算每个位置$t$对这个询问的贡献，设相同权值的前一个点为$T$，$d_x$为点$x$的深度，分情况讨论

  • 如果$t$是$x,y$的祖先，那么能产生的贡献为$(d_t-d_T)(d_x-d_t+1+d_y-d_t+1)$，拆开式子后为$-2{d_t}^2+2d_Td_t-d_T(d_x+d_y+2)+d_t(d_x+d_y+2)$，可以维护$d_t,d_T,d_td_T$的和处理

  • 如果$t$是$y$的祖先，$x$的孩子，那么能产生的贡献为$(d_y-d_t+1)(d_x-d_T)$，拆开式子后为$d_xd_y-d_xd_t+d_x-d_T(d_y+1)+d_td_T$，跟上面一样维护就行了，值得注意的是只有$T$为$x$祖先的时候才能产生贡献，所以用主席树维护即可

发现子任务$2$就是链的情况，所以现在有$60$分啦

如果推广到树上的情况，设$x,y$的$LCA$为$v$，可以把询问拆成查询

  • $(1,fa_v),(1,x)$
  • $(1,fa_v),(1,y)$
  • $(x,v),(v,y)$

发现前面两个都是链的情况，所以可以计算，注意要去掉$(1,fa_v)(1,fa_v)$的答案

这个题的生成数据方式非常有意思，因为是先建出一条链然后随机往上连，所以每个点到主链（即点$1\sim p$构成的链）的距离期望不超过$\log n$，相同权值点的个数也很少

所以可以暴力枚举$x\to v$这条链上的点$a$，查询$y\to v$上第一个相同权值的点的深度$D$，这样答案就是$(D-d_v)(d_x-d_a+1)$

分类讨论化式子烦死了OAO

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<vector>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=2e5+5;
struct q{
	int x,y;
}c[MAX];
struct u{
	int l,r,s;
	LL x,_x,_x_;
}s[MAX*19];
int T,n,m,num,p,ans,cnt,k,tot,Tot;
unsigned int SA,SB,SC;
int h[MAX],use[MAX*6],qwq[MAX],re[MAX],In[MAX],Out[MAX],Num[MAX],a[MAX],pos[MAX],d[MAX],fa[MAX],siz[MAX],son[MAX],top[MAX],NUM[MAX*6],L[MAX*6],rt[MAX],pre[MAX];
LL Ans[MAX],D[MAX];
struct o{
	int l,r,id,lca;
	bool operator< (const o &a)
	const{
		if(pos[l]!=pos[a.l]) return pos[l]<pos[a.l];
		return r<a.r;
	}
}qu[MAX<<1];
vector<int> vec[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
unsigned int rng61()
{
	SA^=SA<<16,SA^=SA>>5,SA^=SA<<1;
	unsigned int t=SA;
	SA=SB,SB=SC,SC^=t^SA;
	return SC;
}
void add(int x,int y)
{
	c[++num]=(q){h[x],y},h[x]=num;
	c[++num]=(q){h[y],x},h[y]=num;
}
void gen()
{
	n=read(),p=read(),SA=read(),SB=read(),SC=read();
	for(int i=2;i<=p;++i)
	  add(i-1,i);
	for(int i=p+1;i<=n;++i)
	  add(rng61()%(i-1)+1,i);
	for(int i=1;i<=n;++i)
	  a[i]=rng61()%n+1;
}
void change(int l,int r,int &k,int pre,int d,int d1)
{
	s[k=++Tot]=s[pre],s[k].x+=d,s[k]._x+=d1,s[k]._x_+=1ll*d*d1,++s[k].s;
	if(l==r) return;
	if(d1<=mid) change(l,mid,tl,s[pre].l,d,d1);
	else change(mid+1,r,tr,s[pre].r,d,d1);
}
u operator+ (u A,u B) {return (u){0,0,A.s+B.s,A.x+B.x,A._x+B._x,A._x_+B._x_};}
u operator- (u A,u B) {return (u){0,0,A.s-B.s,A.x-B.x,A._x-B._x,A._x_-B._x_};}
u ask(int l,int r,int k,int pre,int L,int R)
{
	if(l==L&&r==R) return s[pre]-s[k];
	if(R<=mid) return ask(l,mid,tl,s[pre].l,L,R);
	if(L>mid) return ask(mid+1,r,tr,s[pre].r,L,R);
	return ask(l,mid,tl,s[pre].l,L,mid)+ask(mid+1,r,tr,s[pre].r,mid+1,R);
}
void dfs(int x=1,int F=0)
{
	pre[x]=L[a[x]],L[a[x]]=x,fa[x]=F,d[x]=d[F]+(siz[x]=1),re[In[x]=++cnt]=x,D[x]=D[F]+1ll*d[x]*d[x],vec[a[x]].push_back(x);
	change(0,n,rt[x],rt[F],d[x],d[pre[x]]);
	for(int i=h[x];i;i=c[i].x)
	  if(F^c[i].y)
	  {
	  	dfs(c[i].y,x),siz[x]+=siz[c[i].y];
	  	if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
	  }
	re[Out[x]=++cnt]=x,L[a[x]]=pre[x];
}
void dfs1(int x=1,int tp=1)
{
	top[x]=tp;
	if(!son[x]) return;
	dfs1(son[x],tp);
	for(int i=h[x];i;i=c[i].x)
	  if((c[i].y^fa[x])&&(c[i].y^son[x])) dfs1(c[i].y,c[i].y);
}
int LCA(int x,int y)
{
	while(top[x]^top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return d[x]>d[y]?y:x;
}
void add(int x) {if(++NUM[a[re[x]]]==1) ++ans;}
void del(int x) {if(!--NUM[a[re[x]]]) --ans;}
void Mem()
{
	ans=cnt=num=tot=Tot=0;
	memset(h,0,sizeof(h));
	memset(rt,0,sizeof(rt));
	memset(son,0,sizeof(son));
	memset(NUM,0,sizeof(NUM));
	memset(Num,0,sizeof(Num));
	memset(use,0,sizeof(use));
	memset(vec,0,sizeof(vec));
}
LL Solve(int x,int y)
{
	if(d[x]>d[y]) swap(x,y);
	u X=ask(0,n,rt[0],rt[x],0,n),Y=ask(0,n,rt[x],rt[y],0,d[fa[x]]);
	return -d[x]-2*D[x]+2*X._x_+(X.x-X._x)*(d[x]+d[y]+2)+1ll*d[x]*d[y]*Y.s-Y.x*d[x]+1ll*d[x]*Y.s-Y._x*(d[y]+1)+Y._x_;
}
bool look(int lca,int y,int x) {return In[lca]<=In[x]&&Out[lca]>=Out[x]&&In[y]>=In[x]&&Out[y]<=Out[x];}
int main()
{
	T=read();
	while(T--)
	{
		Mem(),gen(),m=read(),dfs(),dfs1(),k=sqrt(cnt);
		for(int i=1;i<=cnt;++i)
		  pos[i]=(i-1)/k+1;
		for(int i=1,op,x,y,cnt,lca,l_l,l_r,r_l,r_r,X,Y;i<=m;++i)
		  {
		  	op=read(),x=read(),y=read(),lca=LCA(x,y),cnt=0;
			if(op==1)
			{
				qu[++tot].id=i,qu[tot].lca=lca,l_l=In[x],l_r=Out[x],r_l=In[y],r_r=Out[y];
			  	if(l_r<=r_l) qu[tot].l=l_r,qu[tot].r=r_l;
			  	else if(r_r<=l_l) qu[tot].l=r_r,qu[tot].r=l_l;
			  	else if(l_r<=r_r) qu[tot].l=l_r,qu[tot].r=r_r;
			  	else if(r_r<=l_r) qu[tot].l=r_r,qu[tot].r=l_r;
			  	if(qu[tot].lca==x||qu[tot].lca==y) qu[tot].lca=0;
			}
			else if(op==2)
			{
				if(lca==x||lca==y) Ans[i]=Solve(x,y);
				else
				{
					X=LCA(x,p),Y=LCA(y,p);
					if(d[X]>d[Y]) swap(x,y),swap(X,Y);
					u Dx=ask(0,n,rt[fa[lca]],rt[y],0,d[lca]-1);
					Ans[i]=Solve(fa[lca],y)+Solve(fa[lca],x)-Solve(fa[lca],fa[lca])+(Dx.s*(d[y]+1)-Dx.x)*(d[x]-d[lca]+1);
					for(int tt=x;tt!=lca;tt=fa[tt])
					  qwq[++cnt]=tt;
					qwq[++cnt]=lca;
					while(cnt)
					{
						int tt=qwq[cnt--],D_;
						if(use[a[tt]]!=i)
						{
							use[a[tt]]=i,D_=d[y]+1;
							for(int j=0,Cnt=vec[a[tt]].size();j<Cnt;++j)
							  if(look(lca,y,vec[a[tt]][j])) D_=min(D_,d[vec[a[tt]][j]]);
							Ans[i]+=1ll*(D_-d[lca])*(d[x]-d[tt]+1);
						}
					}
				}
			}
		  }
		sort(qu+1,qu+1+tot);
		for(int i=1,l=1,r=0,op;i<=tot;++i)
		  {
		  	op=0;
			while(r<qu[i].r) if(++Num[re[++r]]==2) del(r);
		  	else add(r);
		  	while(l<qu[i].l) if(--Num[re[l]]==1) add(l++);
		  	else del(l++);
		  	while(l>qu[i].l) if(++Num[re[--l]]==2) del(l);
		  	else add(l);
		  	while(r>qu[i].r) if(--Num[re[r]]==1) add(r--);
		  	else del(r--);
			if(qu[i].lca&&!NUM[a[qu[i].lca]]) op=1;
		  	Ans[qu[i].id]=ans+op;
		  }
		for(int i=1;i<=m;++i)
		  printf("%lld\n",Ans[i]);
	}
	return 0;
}
FRIENDS