传送门
注意到一种颜色改了之后就不能改回去了。
因此可以启发式合并。
每次把小的合并给大的。
这样每个数最多被合并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 一般看规律(启发式合并)的更多相关文章
-
2018.10.14 loj#6012. 「网络流 24 题」分配问题(费用流)
传送门 费用流水题. 依然是照着题意模拟建边就行了. 为了练板子又重新写了一遍费用流. 代码: #include<bits/stdc++.h> #define N 305 #define ...
-
2018.10.14 loj#6011. 「网络流 24 题」运输问题(费用流)
传送门 费用流入门题. 直接按照题意模拟. 把货物的数量当做容量建边. 然后跑一次最小费用流和最大费用流就行了. 代码: #include<bits/stdc++.h> #define N ...
-
2018.10.14 loj#6003. 「网络流 24 题」魔术球(最大流)
传送门 网络流好题. 这道题可以动态建图. 不难想到把每个球iii都拆点成i1i_1i1和i2i_2i2,每次连边(s,i1),(i2,t)(s,i_1),(i_2,t)(s,i1),(i2, ...
-
[LOJ#516]「LibreOJ β Round #2」DP 一般看规律
[LOJ#516]「LibreOJ β Round #2」DP 一般看规律 试题描述 给定一个长度为 \(n\) 的序列 \(a\),一共有 \(m\) 个操作. 每次操作的内容为:给定 \(x,y\ ...
-
LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律
二次联通门 : LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律 /* LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律 set ...
-
loj516 「LibreOJ β Round #2」DP 一般看规律
传送门:https://loj.ac/problem/516 [题解] 那段代码求的是相同的数中间隔最小的值. 离散后用set维护每个值出现次数,每次操作相当于合并两个set,这步可以启发式合并. 加 ...
-
loj516 DP一般看规律(set启发式合并)
题目: https://loj.ac/problem/516 分析: 每次将一个颜色更改为另一个颜色相当于将两个集合合并 然后对于答案的更新,一个点插入到一个集合中,那么可能更新答案的就是其前驱节点或 ...
-
[2016北京集训试题7]thr-[树形dp+树链剖分+启发式合并]
Description Solution 神仙操作orz. 首先看数据范围,显然不可能是O(n2)的.(即绝对不是枚举那么简单的),我们考虑dp. 定义f(x,k)为以x为根的子树中与x距离为k的节点 ...
-
2018.10.14 NOIP训练 猜数游戏(决策单调性优化dp)
传送门 一道神奇的dp题. 这题的决策单调性优化跟普通的不同. 首先发现这道题只跟r−lr-lr−l有关. 然后定义状态f[i][j]f[i][j]f[i][j]表示猜范围为[L,L+i−1][L,L ...
随机推荐
-
Visual Studio+TFS--强大的项目管理工具
一.前言 微软的Visual Studio非常强大,可以无缝结合Git或自家的TFS(Team Foundation Server),进行项目管理非常方便,从需求分析.开发.测试.维护,几乎可以贯穿软 ...
-
1029 C语言文法定义与C程序的推导过程
1 阅读并理解提供给大家的C语言文法文件. 2 参考该文件写出一个自己好理解版的现实版的完整版的C语言文法. 3 给出一段C程序,写出用上述文法产生这段C程序的推导过程. program → exte ...
-
ASP.NET从MVC5升级到MVC6
1-1)文件结构的升级(Area和Filter知识总结) - ASP.NET从MVC5升级到MVC6 ASP.NET从MVC5升级到MVC6 总目录 MVC5项目结构 带有Areas和Filter ...
-
Codeforces478D-Red-Green Towers-DP
不是特别难的一道dp题. 给r个红块,g个绿块,计算这些块能磊出的最高塔的方案数. 塔的每一层都比上一层多一块,每一层只能有一种颜色. dp[i][j]表示第i层,j个红块的方案数. 则dp[i][j ...
-
Java的 volatile关键字的底层实现原理
我们知道volatile关键字的作用是保证变量在多线程之间的可见性,它是java.util.concurrent包的核心,没有volatile就没有这么多的并发类给我们使用.本文详细解读一下volat ...
-
GlusterFS分布式存储学习笔记
分布式文件系统 分布式文件系统(Distributed File System)是指文件系统管理的物理存储资源并不直接与本地节点相连,而是分布于计算网络中的一个或者多个节点的计算机上.目前意义上的分布 ...
-
Tree总结
树结构问题因为容易写出解法,因此经常出现在面试题中 1. 树的种类 1) Tree 2) Binary Trees 3) Binary Search Trees(BST) : used to sort ...
- servlet中url-pattern之/与/*的区别
-
MySQL ALTER讲解
当我们需要修改数据表名或者修改数据表字段时,就需要使用到MySQL ALTER命令. 开始本章教程前让我们先创建一张表,表名为:testalter_tbl. root@host# mysql -u r ...
-
触发器二(DML触发器)(学习笔记)
DML触发器(语句触发器) 由DML语句进行触发,当用户执行了INSERT,UPDATE,DELETE操作时就会触发操作 示例一.只有在每个月的10日才允许办理,新员工入职与离职,其他时间不允许增加和 ...