题解 P4689 【[Ynoi2016]这是我自己的发明】
Owen_codeisking
2018-11-22 08:26:26
# [更好的阅读体验戳这里](https://www.cnblogs.com/owencodeisking/p/10003463.html)
话说这道题数据是不是都是链啊，我不手动扩栈就全 $RE$...
不过 $A$ 了这题还是很爽的，通过昨晚到今天早上的奋斗，终于肝出了这题
其实楼上说的也差不多了，就是把区间拆掉然后莫队瞎搞
弱化版：[bzoj [SNOI2017]一个简单的询问](https://www.lydsy.com/JudgeOnline/problem.php?id=5016)
那我先讲弱化版吧
可以发现
$$\sum_{x=0}^{inf}get(l_1,r_1,x)\times get(l_2,r_2,x)=\sum_{x=0}^{inf}get(0,r_1,x)\times get(0,r_2,x)-\sum_{x=0}^{inf}get(0,l_1-1,x)\times get(0,r_2,x)$$
$$-\sum_{x=0}^{inf}get(0,r_1,x)\times get(0,l_2-1,x)+\sum_{x=0}^{inf}get(0,l_1-1,x)\times get(0,l_2-1,x)$$
我们对上面的式子直接上莫队，开两个数组统计即可
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100000+10;
int n,m,a[maxn],b[maxn],c[maxn],tot,blo;ll ans[maxn],now;
struct Query{
int l,r,id,v;
}q[maxn<<2];
bool cmp(Query a,Query b){
if((a.l-1)/blo!=(b.l-1)/blo)
return (a.l-1)/blo<(b.l-1)/blo;
return a.r<b.r;
}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void addb(int x){now+=(ll)c[a[x]];b[a[x]]++;}
inline void delb(int x){now-=(ll)c[a[x]];b[a[x]]--;}
inline void addc(int x){now+=(ll)b[a[x]];c[a[x]]++;}
inline void delc(int x){now-=(ll)b[a[x]];c[a[x]]--;}
int main()
{
n=read();blo=sqrt(n);
for(int i=1;i<=n;i++) a[i]=read();
m=read();
int l1,r1,l2,r2;
for(int i=1;i<=m;i++){
l1=read(),r1=read(),l2=read(),r2=read();
q[++tot]=(Query){r1,r2,i,1};
if(l1>1) q[++tot]=(Query){l1-1,r2,i,-1};
if(l2>1) q[++tot]=(Query){l2-1,r1,i,-1};
if(l1>1&&l2>1) q[++tot]=(Query){l1-1,l2-1,i,1};
}
sort(q+1,q+tot+1,cmp);
int L=0,R=0;
for(int i=1;i<=tot;i++){
while(L<q[i].l) addb(++L);
while(L>q[i].l) delb(L--);
while(R<q[i].r) addc(++R);
while(R>q[i].r) delc(R--);
ans[q[i].id]+=(ll)q[i].v*now;
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
```
然后写完弱化版就来做这题了……我的代码洛谷 $AC$，$bzoj\ AC$，$loj\ TLE$，强行上 $fread\ fwrite$ 才卡过去
其实这道题差不多，转化为 $dfs$ 序，然后类似树剖换根的思想分类讨论：
1、$x=rt$
2、$rt$ 在以 $1$ 为根时 $x$ 的子树中
3、$rt$ 不在以 $1$ 为根时 $x$ 的子树中
然后第一种和第三种情况比较简单，第二种情况要找 $rt$ 在哪里，我用的树剖，其实还可以用倍增，转化为两段区间，然后合并 $x$ 的区间和 $y$ 的区间
那么就要分九种情况讨论了 ~~怪不得lxl的题目那么毒瘤~~
严重压行后 $91$ 行，还是比较清爽的
$Code\ Below:$
```cpp
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100000+10;
int n,m,rt=1,a[maxn],mp[maxn],b[maxn],c[maxn],cnt,blo,t;ll ans[maxn*5],now;
int top[maxn],siz[maxn],son[maxn],fa[maxn],id[maxn],head[maxn],to[maxn<<1],nxt[maxn<<1],tot,tim;
struct Query{int l,r,id,v;}q[maxn*80];
bool cmp(Query a,Query b){return ((a.l-1)/blo!=(b.l-1)/blo)?((a.l-1)/blo<(b.l-1)/blo):(a.r<b.r);}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs1(int x,int f){
siz[x]=1;fa[x]=f;int maxson=-1;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=f){
dfs1(to[i],x);siz[x]+=siz[to[i]];
if(maxson<siz[to[i]]) maxson=siz[to[i]],son[x]=to[i];
}
}
void dfs2(int x,int topf){
id[x]=++tim;mp[tim]=a[x];top[x]=topf;
if(son[x]) dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
inline int getson(int x,int y){
while(top[x]!=top[y]){x=top[x];if(fa[x]==y) return x;x=fa[x];}
return son[y];
}
inline void addb(int x){now+=(ll)c[mp[x]];b[mp[x]]++;}
inline void delb(int x){now-=(ll)c[mp[x]];b[mp[x]]--;}
inline void addc(int x){now+=(ll)b[mp[x]];c[mp[x]]++;}
inline void delc(int x){now-=(ll)b[mp[x]];c[mp[x]]--;}
inline void Add(int l1,int r1,int l2,int r2,int id){
if(l1<1||l2<1||r1>n||r2>n||l1>r1||l2>r2) return ;
q[++cnt]=(Query){r1,r2,id,1};
if(l1>1) q[++cnt]=(Query){l1-1,r2,id,-1};
if(l2>1) q[++cnt]=(Query){l2-1,r1,id,-1};
if(l1>1&&l2>1) q[++cnt]=(Query){l1-1,l2-1,id,1};
}
int main()
{
n=read(),m=read();blo=sqrt(n);
int i,opt,x,y,z,l1,r1,j=0,L=0,R=0;
for(i=1;i<=n;i++) mp[i]=a[i]=read();
sort(mp+1,mp+n+1);t=unique(mp+1,mp+n+1)-mp-1;
for(i=1;i<=n;i++) a[i]=lower_bound(mp+1,mp+t+1,a[i])-mp;
for(i=1;i<n;i++){x=read(),y=read();add(x,y);add(y,x);}
dfs1(rt,0);dfs2(rt,rt);
for(i=1;i<=m;i++){
opt=read();
if(opt==1) rt=read();
if(opt==2){
j++;x=read(),y=read();
if(x==rt){
if(y==rt) Add(1,n,1,n,j);
else if(id[y]<id[rt]&&id[rt]+siz[rt]<=id[y]+siz[y])
z=getson(rt,y),Add(1,n,1,id[z]-1,j),Add(1,n,id[z]+siz[z],n,j);
else Add(1,n,id[y],id[y]+siz[y]-1,j);
}
else if(id[x]<id[rt]&&id[rt]+siz[rt]<=id[x]+siz[x]){
z=getson(rt,x);l1=id[z];r1=id[z]+siz[z]-1;
if(y==rt) Add(1,l1-1,1,n,j),Add(r1+1,n,1,n,j);
else if(id[y]<id[rt]&&id[rt]+siz[rt]<=id[y]+siz[y])
z=getson(rt,y),Add(1,l1-1,1,id[z]-1,j),Add(1,l1-1,id[z]+siz[z],n,j),Add(r1+1,n,1,id[z]-1,j),Add(r1+1,n,id[z]+siz[z],n,j);
else Add(1,l1-1,id[y],id[y]+siz[y]-1,j),Add(r1+1,n,id[y],id[y]+siz[y]-1,j);
}
else {
if(y==rt) Add(id[x],id[x]+siz[x]-1,1,n,j);
else if(id[y]<id[rt]&&id[rt]+siz[rt]<=id[y]+siz[y])
z=getson(rt,y),Add(id[x],id[x]+siz[x]-1,1,id[z]-1,j),Add(id[x],id[x]+siz[x]-1,id[z]+siz[z],n,j);
else Add(id[x],id[x]+siz[x]-1,id[y],id[y]+siz[y]-1,j);
}
}
}
sort(q+1,q+cnt+1,cmp);
for(i=1;i<=cnt;i++){
while(L<q[i].l) addb(++L);
while(L>q[i].l) delb(L--);
while(R<q[i].r) addc(++R);
while(R>q[i].r) delc(R--);
ans[q[i].id]+=(ll)q[i].v*now;
}
for(i=1;i<=j;i++) printf("%lld\n",ans[i]);
return 0;
}
```