【BZOJ4940】【YNOI2016】这是我自己的发明
阅读此篇文章前请先跟我大喊三声:dllxl!dllxl!dllxl!
咳咳。
题意:
Description
Input
Output
题解:
非常不推荐去阅读原题面(看完题面就知道出题人系列)
众所周知,云南省选全是毒瘤数据结构题
其实这是一道BZOJ二合一。。。BZOJ3083 遥远的国度+BZOJ5016一个简单的询问(题解咕咕咕中)
如果没有换根操作,先来考虑如何处理询问(BZOJ5016):
首先按照dfs序把问题转化到序列上,询问就变成了选取序列中的两个区间,答案即为在两个区间中出现过的每个数分别在两个区间出现次数的乘积;
用公式表达就是:
$ans=\sum\limits_{x=1}^{\infty}sum(l_1,r_1,x)\times sum(l_2,r_2,x)$,其中$sum(l,r,x)$表示数字$x$在区间$[l,r]$中出现的次数。
这个东西。。。不好处理啊。。。
一般这种多组询问且不知所云不好维护的东西都会想到分块,然后快(du)乐(liu)莫队?
那就推一推前缀形式:
$ans=\sum\limits_{x=1}^{\infty}sum(l_1,r_1,x)\times sum(l_2,r_2,x)$
$=\sum\limits_{x=1}^{\infty}(sum(1,r_1,x)-sum(1,l_1-1,x))\times(sum(1,r_2,x)-sum(1,l_2-1,x))$
$=\sum\limits_{x=1}^{\infty}sum(1,r_1,x)·sum(1,r_2,x)-sum(1,r_1,x)·sum(1,l_2-1,x)-sum(1,l_1-1,x)·sum(1,r_2,x)+sum(1,l_1-1,x)·sum(1,l_2-1,x)$
设$f(n,m)=\sum\limits_{x=1}^{\infty}sum(1,n,x)·sum(1,m,x)$
则$ans=f(r_1,r_2)-f(r_1,l_2-1)-f(l_1-1,r_2)+f(l_1-1,l_2-1)$
所以可以询问一拆四然后直接上莫队……
然后看换根(BZOJ3083):
数据结构学傻了->这题一定能用LCT!
啊LCT不能维护子树信息……
数据结构学傻了*2->换根一定能用树剖记录!
啊dfs序会变然后就不能维护了……
因此我们要大力分类讨论:
设根为root,所求子树的根为rt
1.root==rt:continue;
2.root不在rt的子树中:即换根后rt子树中的dfs顺序不会变,所以直接遍历即可;
3.rt在root的子树中:
分析此时的dfs顺序:应该是从root开始,访问到rt的子节点中是root的祖先的节点(记为点F),再访问rt,最后才是其它节点。那么在rt之前访问到的只有F的子树,其它的都是rt子树中的节点。众所周知子树dfs序连续,所以查询rt此时的子树就相当于查询线段树中$[1,l-1]$和$[r+1,n]$中的节点。
所以只有第三种情况特殊求一个F,然后直接维护即可;
求点F可以用树上倍增,当然在bzoj3083原题中是树剖就可以用树剖找。
然后就可以喜闻乐见的把两题拼在一起,码码码~
要注意的是由于换根的三种情况比较麻烦,莫队要拆成九个询问,于是常数upup
最后的时间复杂度是$O(n\sqrt{m})$,原题由于友(du)善(liu)出题人lxl的无私馈赠因此要大力卡常+调参+fread、fwrite才能过,而小视野非常良心的开了两倍时限,于是就开心过掉啦~
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
//typedef long long ll;
struct edge{
int v,next;
}a[];
struct nd{
int x,id;
friend bool operator <(nd a,nd b){
return a.x<b.x;
}
}s[];
int BLK,n,m,op,u,v,l,r,rt=,tot=,tim=,cnt=,tmp=,head[],ans[],pos[],cl[],ll[],rr[],num[],in[],out[],dep[],fa[][];
bool isans[];
struct task{
int l,r,op,id;
friend bool operator <(task a,task b){
return pos[a.l]==pos[b.l]?pos[a.r]<pos[b.r]:pos[a.l]<pos[b.l];
}
}t[];
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void dfs(int u,int ff,int dpt){
in[u]=++tim;
dep[u]=dpt;
fa[u][]=ff;
for(int i=;i<=;i++)fa[u][i]=fa[fa[u][i-]][i-];
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(v!=ff){
dfs(v,u,dpt+);
}
}
out[u]=tim;
}
/*int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int l=dep[u]-dep[v];
for(int i=19;i>=0;i--){
if((1<<i)&l)u=fa[u][i];
}
if(u==v)return u;
for(int i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i],v=fa[v][i];
}
}
return fa[u][0];
}*/
int get(int u){
return (dep[u]<dep[rt]&&in[u]<=in[rt]&&in[rt]<=out[u])?u:rt;
}
int getfa(int u,int l){
for(int i=;i>=;i--){
if((<<i)&l)u=fa[u][i];
}
return u;
}
void mv1l(int x){
tmp+=rr[cl[x]];
ll[cl[x]]++;
}
void mv2l(int x){
tmp-=rr[cl[x]];
ll[cl[x]]--;
}
void mv1r(int x){
tmp+=ll[cl[x]];
rr[cl[x]]++;
}
void mv2r(int x){
tmp-=ll[cl[x]];
rr[cl[x]]--;
}
int main(){
memset(head,-,sizeof(head));
memset(isans,,sizeof(isans));
scanf("%d%d",&n,&m);
BLK=(int)sqrt(n);
for(int i=;i<=n;i++)pos[i]=(i-)/BLK+;
for(int i=;i<=n;i++){
scanf("%d",&s[i].x);
s[i].id=i;
}
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(,,);
sort(s+,s+n+);
for(int i=;i<=n;i++){
if(s[i].x!=s[i-].x)cnt++;
cl[in[s[i].id]]=cnt;
}
cnt=;
for(int i=;i<=m;i++){
scanf("%d%d",&op,&u);
if(op==)rt=u;
else{
scanf("%d",&v);
isans[i]=true;
if(u==v&&u==rt){
t[++cnt]=(task){n,n,,i};
continue;
}
if(u!=v&&v==rt)swap(u,v);
int fu=get(u),fv=get(v);
if(u!=v&&u==rt){
if(fv==v){
v=getfa(rt,dep[rt]-dep[v]-);
t[++cnt]=(task){n,in[v]-,,i};
t[++cnt]=(task){n,n,,i};
t[++cnt]=(task){n,out[v],-,i};
}else{
t[++cnt]=(task){n,out[v],,i};
t[++cnt]=(task){n,in[v]-,-,i};
}
continue;
}
if(fu==u&&fv!=v){
swap(u,v);
swap(fu,fv);
}
if(fu!=u&&fv!=v){
t[++cnt]=(task){out[u],out[v],,i};
t[++cnt]=(task){out[u],in[v]-,-,i};
t[++cnt]=(task){in[u]-,in[v]-,,i};
t[++cnt]=(task){in[u]-,out[v],-,i};
}else if(fu!=u&&fv==v){
v=getfa(rt,dep[rt]-dep[v]-);
t[++cnt]=(task){out[u],in[v]-,,i};
t[++cnt]=(task){out[u],n,,i};
t[++cnt]=(task){out[u],out[v],-,i};
t[++cnt]=(task){in[u]-,in[v]-,-,i};
t[++cnt]=(task){in[u]-,n,-,i};
t[++cnt]=(task){in[u]-,out[v],,i};
}else{
u=getfa(rt,dep[rt]-dep[u]-);
v=getfa(rt,dep[rt]-dep[v]-);
t[++cnt]=(task){n,in[v]-,,i};
t[++cnt]=(task){n,n,,i};
t[++cnt]=(task){n,out[v],-,i};
t[++cnt]=(task){out[u],in[v]-,-,i};
t[++cnt]=(task){out[u],n,-,i};
t[++cnt]=(task){out[u],out[v],,i};
t[++cnt]=(task){in[u]-,in[v]-,,i};
t[++cnt]=(task){in[u]-,n,,i};
t[++cnt]=(task){in[u]-,out[v],-,i};
}
}
}
sort(t+,t+cnt+);
l=t[].l,r=t[].r;
for(int i=;i<=l;i++)ll[cl[i]]++;
for(int i=;i<=r;i++){
rr[cl[i]]++;
tmp+=ll[cl[i]];
}
ans[t[].id]+=tmp*t[].op;
for(int i=;i<=cnt;i++){
while(l<t[i].l)mv1l(++l);
while(l>t[i].l)mv2l(l--);
while(r<t[i].r)mv1r(++r);
while(r>t[i].r)mv2r(r--);
ans[t[i].id]+=tmp*t[i].op;
}
for(int i=;i<=m;i++){
if(isans[i])printf("%d\n",ans[i]);
}
return ;
}
最新文章
- AE开发实现Spatial Join Analysis
- 转:通过代码理解Asp.net4中的几种ClientIDMode设置.
- 无DLL远程注入
- java web 学习十三(使用session防止表单重复提交)
- 淘宝IP地址查询
- (?m)
- 【HDOJ】1297 Children’s Queue
- JSP include HTML出现乱码
- jquery cleditor 光标经常点不进去问题解决方法 bootstrap 富文本框 控件
- Unix/Linux环境C编程入门教程(19)Red Hat Entetprise Linux 7.0环境搭建
- android之ArrayAdapter的重写
- CATransition 转场动画解析
- 机器学习——XGBoost大杀器,XGBoost模型原理,XGBoost参数含义
- html文档知识补充
- Spring Ioc 常用注解
- 第四章 FFmpeg转码
- TensorFlow框架下的RNN实践小结
- iframe动态改变内嵌页面高度
- Android Studio:Multiple dex files define Landroid/support/annotation/AnimRes
- [QT][DEMO] QTableWidget 设置某一列禁止编辑