2018.10.14 loj#516. DP 一般看规律(启发式合并)

时间:2021-09-01 02:47:34

传送门

注意到一种颜色改了之后就不能改回去了。

因此可以启发式合并。

每次把小的合并给大的。

这样每个数最多被合并logloglog次。

如果维护一棵比较下标的平衡树的话,对于答案有贡献的就是每个数与前驱和后继的差值。

于是就用setsetset实现啦。

代码:

#include<bits/stdc++.h>
#define N 100005
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int n,m,tot=0,ans=2147483647;
map<int,set<int> >S;
inline void query(int i,int pos){
	set<int>::iterator it=S[i].lower_bound(pos);
	if(it!=S[i].end())ans=min(ans,(*it)-pos);
	if(it!=S[i].begin())--it,ans=min(ans,pos-(*it));
}
int main(){
	n=read(),m=read();
	for(int val,i=1;i<=n;++i)query((val=read()),i),S[val].insert(i);
	while(m--){
		int x=read(),y=read();
		if(x==y){printf("%d\n",ans);continue;}
		if(S[x].size()>S[y].size())swap(S[x],S[y]);
		for(set<int>::iterator it=S[x].begin();it!=S[x].end();++it)query(y,(*it)),S[y].insert(*it);
		S[x].clear(),printf("%d\n",ans);
	}
	return 0;
}

2018.10.14 loj#516. DP 一般看规律(启发式合并)的更多相关文章

  1. 2018&period;10&period;14 loj&num;6012&period; 「网络流 24 题」分配问题(费用流)

    传送门 费用流水题. 依然是照着题意模拟建边就行了. 为了练板子又重新写了一遍费用流. 代码: #include<bits/stdc++.h> #define N 305 #define ...

  2. 2018&period;10&period;14 loj&num;6011&period; 「网络流 24 题」运输问题(费用流)

    传送门 费用流入门题. 直接按照题意模拟. 把货物的数量当做容量建边. 然后跑一次最小费用流和最大费用流就行了. 代码: #include<bits/stdc++.h> #define N ...

  3. 2018&period;10&period;14 loj&num;6003&period; 「网络流 24 题」魔术球(最大流)

    传送门 网络流好题. 这道题可以动态建图. 不难想到把每个球iii都拆点成i1i_1i1​和i2i_2i2​,每次连边(s,i1),(i2,t)(s,i_1),(i_2,t)(s,i1​),(i2​, ...

  4. &lbrack;LOJ&num;516&rsqb;「LibreOJ β Round &num;2」DP 一般看规律

    [LOJ#516]「LibreOJ β Round #2」DP 一般看规律 试题描述 给定一个长度为 \(n\) 的序列 \(a\),一共有 \(m\) 个操作. 每次操作的内容为:给定 \(x,y\ ...

  5. LibreOJ &num;516&period; 「LibreOJ β Round &num;2」DP 一般看规律

    二次联通门 : LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律 /* LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律 set ...

  6. loj516 「LibreOJ β Round &num;2」DP 一般看规律

    传送门:https://loj.ac/problem/516 [题解] 那段代码求的是相同的数中间隔最小的值. 离散后用set维护每个值出现次数,每次操作相当于合并两个set,这步可以启发式合并. 加 ...

  7. loj516 DP一般看规律(set启发式合并)

    题目: https://loj.ac/problem/516 分析: 每次将一个颜色更改为另一个颜色相当于将两个集合合并 然后对于答案的更新,一个点插入到一个集合中,那么可能更新答案的就是其前驱节点或 ...

  8. &lbrack;2016北京集训试题7&rsqb;thr-&lbrack;树形dp&plus;树链剖分&plus;启发式合并&rsqb;

    Description Solution 神仙操作orz. 首先看数据范围,显然不可能是O(n2)的.(即绝对不是枚举那么简单的),我们考虑dp. 定义f(x,k)为以x为根的子树中与x距离为k的节点 ...

  9. 2018&period;10&period;14 NOIP训练 猜数游戏(决策单调性优化dp)

    传送门 一道神奇的dp题. 这题的决策单调性优化跟普通的不同. 首先发现这道题只跟r−lr-lr−l有关. 然后定义状态f[i][j]f[i][j]f[i][j]表示猜范围为[L,L+i−1][L,L ...

随机推荐

  1. Visual Studio&plus;TFS--强大的项目管理工具

    一.前言 微软的Visual Studio非常强大,可以无缝结合Git或自家的TFS(Team Foundation Server),进行项目管理非常方便,从需求分析.开发.测试.维护,几乎可以贯穿软 ...

  2. 1029 C语言文法定义与C程序的推导过程

    1 阅读并理解提供给大家的C语言文法文件. 2 参考该文件写出一个自己好理解版的现实版的完整版的C语言文法. 3 给出一段C程序,写出用上述文法产生这段C程序的推导过程. program → exte ...

  3. ASP&period;NET从MVC5升级到MVC6

    1-1)文件结构的升级(Area和Filter知识总结) - ASP.NET从MVC5升级到MVC6   ASP.NET从MVC5升级到MVC6 总目录 MVC5项目结构 带有Areas和Filter ...

  4. Codeforces478D-Red-Green Towers-DP

    不是特别难的一道dp题. 给r个红块,g个绿块,计算这些块能磊出的最高塔的方案数. 塔的每一层都比上一层多一块,每一层只能有一种颜色. dp[i][j]表示第i层,j个红块的方案数. 则dp[i][j ...

  5. Java的 volatile关键字的底层实现原理

    我们知道volatile关键字的作用是保证变量在多线程之间的可见性,它是java.util.concurrent包的核心,没有volatile就没有这么多的并发类给我们使用.本文详细解读一下volat ...

  6. GlusterFS分布式存储学习笔记

    分布式文件系统 分布式文件系统(Distributed File System)是指文件系统管理的物理存储资源并不直接与本地节点相连,而是分布于计算网络中的一个或者多个节点的计算机上.目前意义上的分布 ...

  7. Tree总结

    树结构问题因为容易写出解法,因此经常出现在面试题中 1. 树的种类 1) Tree 2) Binary Trees 3) Binary Search Trees(BST) : used to sort ...

  8. servlet中url-pattern之&sol;与&sol;&ast;的区别

  9. MySQL ALTER讲解

    当我们需要修改数据表名或者修改数据表字段时,就需要使用到MySQL ALTER命令. 开始本章教程前让我们先创建一张表,表名为:testalter_tbl. root@host# mysql -u r ...

  10. 触发器二&lpar;DML触发器&rpar;&lpar;学习笔记&rpar;

    DML触发器(语句触发器) 由DML语句进行触发,当用户执行了INSERT,UPDATE,DELETE操作时就会触发操作 示例一.只有在每个月的10日才允许办理,新员工入职与离职,其他时间不允许增加和 ...