一道题的简单(精妙)而慢和快而复杂(吐血)的解法

题目

题目链接-BZOJ4552

题目大意似乎和题目描述差不多,略。。。

题解

简单(精妙)而慢的解法

对某个区间排序。

这种操作如果选一个数,将比它小的数当成0,比它大的数当成1。

那么,就变成了对区间覆盖0或1的问题。

所以我们可以来二分答案。

若将小于等于x的全赋成0, 大于x的全赋成1。

那么就是求最小的x,使询问的位置经过若干操作后等于0。

快叫好!!!

“吼啊!”

时间复杂度

二分 O(lgn)

判定 O(mlgn)

总时间复杂度 O(mlg^2n)

代码

快而复杂(吐血)的解法

这种做法可以处理多个询问,还可以在线做。

那么是什么呢?

没错,模拟大法好!

。。。

开始第i个位置都表示区间$ [i,i] $,弄一棵动态开点的权值线段树,并且权值线段树里记录下i位置的值。

然后每棵线段树还有个rev表示是从大到小还是从小到大。

然后就可以模拟啦。

外面弄一棵线段树维护每个位置在哪个区间中。

然后修改操作就是找一段包含修改区间的连续的区间,头尾两个区间可能是部分包含的,所以还要用到线段树的split操作(雾),然后就是线段树的merge了。介绍线段树的合并与分裂的传送门

这段代码居然让我码了一个多小时。。。

时间复杂度

每次操作最多split两次,所以main函数里最多split O(n + m) 次,并且线段树节点数最多 O((n + m)lgn) 个,所以最后的时间复杂度为 O((n + m)lgn)

代码

 

一道题的简单(精妙)而慢和快而复杂(吐血)的解法
Tagged on:         

2 thoughts on “一道题的简单(精妙)而慢和快而复杂(吐血)的解法

发表评论

电子邮件地址不会被公开。 必填项已用*标注