当前位置: 首页 > news >正文

[SPOJ]COT2

题意:给一棵带点权的树,多次询问两点间路径上的不同权值数

学习了一下莫队上树(雾

先求出栈入栈序$p_{1\cdots 2n}$,记$st_x$为$x$在$p$中第一次出现的位置,$ed_x$为$x$在$p$中最后一次出现的位置

对于一个询问$(x,y)$,先令$st_x\lt st_y$,求出其$lca$,若$x=lca$,则询问$[st_x,st_y]$,否则询问$[ed_x,st_y]$还有$lca$(因为$[ed_x,st_y]$不包含$lca$)

于是我们成功地把问题转化到序列上,普通地莫队即可

不应处理出现两次的数(因为它入栈一次,出栈一次,在路径之外)

#include<stdio.h>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
struct ask{
	int l,r,lca,sid,qid;
}q[100010];
int to[80010],nex[80010],h[40010],dep[40010],fa[40010][16],v[40010],p[80010],st[40010],ed[40010],ti[40010],ex[40010],ans[100010],M;
map<int,int>mp;
map<int,int>::iterator it;
bool cmp(ask a,ask b){
	if(a.sid==b.sid)return a.r<b.r;
	return a.sid<b.sid;
}
void add(int a,int b){
	M++;
	to[M]=b;
	nex[M]=h[a];
	h[a]=M;
}
void dfs(int x){
	st[x]=++M;
	p[M]=x;
	for(int i=h[x];i;i=nex[i]){
		if(to[i]!=fa[x][0]){
			fa[to[i]][0]=x;
			dep[to[i]]=dep[x]+1;
			dfs(to[i]);
		}
	}
	ed[x]=++M;
	p[M]=x;
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int i;
	for(i=15;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(i=15;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int sum;
void add(int);
void del(int x){
	if(ex[x]==0)return add(x);
	ti[v[x]]--;
	if(ti[v[x]]==0)sum--;
	ex[x]=0;
}
void add(int x){
	if(ex[x])return del(x);
	if(ti[v[x]]==0)sum++;
	ti[v[x]]++;
	ex[x]=1;
}
int main(){
	int n,m,i,j,x,y,l,r,sq;
	scanf("%d%d",&n,&m);
	sq=sqrt(n);
	for(i=1;i<=n;i++){
		scanf("%d",v+i);
		mp[v[i]]=1;
	}
	for(i=1,it=mp.begin();it!=mp.end();it++,i++)it->second=i;
	for(i=1;i<=n;i++)v[i]=mp[v[i]];
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	M=0;
	dep[1]=1;
	dfs(1);
	for(j=1;j<16;j++){
		for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(st[x]>st[y])swap(x,y);
		j=lca(x,y);
		q[i].r=st[y];
		if(x==j)
			q[i].l=st[x];
		else{
			q[i].l=ed[x];
			q[i].lca=j;
		}
		q[i].sid=q[i].l/sq;
		q[i].qid=i;
	}
	sort(q+1,q+m+1,cmp);
	l=r=1;
	add(1);
	for(i=1;i<=m;i++){
		while(l>q[i].l){
			l--;
			add(p[l]);
		}
		while(r<q[i].r){
			r++;
			add(p[r]);
		}
		while(l<q[i].l){
			del(p[l]);
			l++;
		}
		while(r>q[i].r){
			del(p[r]);
			r--;
		}
		if(q[i].lca)add(q[i].lca);
		ans[q[i].qid]=sum;
		if(q[i].lca)del(q[i].lca);
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}

转载于:https://www.cnblogs.com/jefflyy/p/8337804.html

相关文章:

  • 设置时间
  • 28次课(使用w查看系统负载、vmstat命令、top命令、sar命令、nload命令)
  • 错误:update 忘了加 where
  • 编程常用动词细微差别
  • lpeg学习笔记- -
  • nslookup工具的使用方法
  • 菜鸟入门【ASP.NET Core】2:部署到IIS
  • 23种简洁好看的扁平化模板
  • TransE论文剩余部分
  • 《Effective C++》 笔记:Tips01-Tips04
  • 实现数据排序的几种方法
  • Laravel整合Bootstrap 4的完整方案
  • Android存储方式之SQLite的使用
  • Redis项目实战 .net StackExchange.Redis
  • [Json.net]快速入门
  • 【mysql】环境安装、服务启动、密码设置
  • CODING 缺陷管理功能正式开始公测
  • gcc介绍及安装
  • GDB 调试 Mysql 实战(三)优先队列排序算法中的行记录长度统计是怎么来的(上)...
  • Iterator 和 for...of 循环
  • javascript 哈希表
  • magento2项目上线注意事项
  • Spring声明式事务管理之一:五大属性分析
  • 编写符合Python风格的对象
  • 当SetTimeout遇到了字符串
  • 两列自适应布局方案整理
  • LIGO、Virgo第三轮探测告捷,同时探测到一对黑洞合并产生的引力波事件 ...
  • Spark2.4.0源码分析之WorldCount 默认shuffling并行度为200(九) ...
  • 我们雇佣了一只大猴子...
  • 支付宝花15年解决的这个问题,顶得上做出十个支付宝 ...
  • ​软考-高级-系统架构设计师教程(清华第2版)【第15章 面向服务架构设计理论与实践(P527~554)-思维导图】​
  • #pragma data_seg 共享数据区(转)
  • (1) caustics\
  • (1)常见O(n^2)排序算法解析
  • (delphi11最新学习资料) Object Pascal 学习笔记---第7章第3节(封装和窗体)
  • (python)数据结构---字典
  • (草履虫都可以看懂的)PyQt子窗口向主窗口传递参数,主窗口接收子窗口信号、参数。
  • (附源码)springboot 智能停车场系统 毕业设计065415
  • (九)One-Wire总线-DS18B20
  • (没学懂,待填坑)【动态规划】数位动态规划
  • (三)Hyperledger Fabric 1.1安装部署-chaincode测试
  • (四)TensorRT | 基于 GPU 端的 Python 推理
  • (转)c++ std::pair 与 std::make
  • ./configure,make,make install的作用
  • .babyk勒索病毒解析:恶意更新如何威胁您的数据安全
  • .Net CF下精确的计时器
  • .NET Core IdentityServer4实战-开篇介绍与规划
  • .NET Micro Framework初体验
  • .NET4.0并行计算技术基础(1)
  • .net开源工作流引擎ccflow表单数据返回值Pop分组模式和表格模式对比
  • .NET设计模式(8):适配器模式(Adapter Pattern)
  • @data注解_一枚 架构师 也不会用的Lombok注解,相见恨晚
  • @media screen 针对不同移动设备
  • @Transaction注解失效的几种场景(附有示例代码)
  • [ IOS ] iOS-控制器View的创建和生命周期