JZOJ 5947.初音未来(miku)
题目大意
维护一个数列 \(a_n\),\(m\) 次操作,每次对区间 \([l..r]\) 进行升序排序
求最后询问区间 \([L..R]\),输出 \(a_L,a_{L+1},···,a_{R}\)
思路
首先很容易想到暴力,这题暴力太好打了!!!
然而我们需要正解
于是有了后文
我们发现排序一段区间如果用冒泡排序的话就要 \(O(S^2)\),其中 \(S\) 为区间大小
进而挖掘冒泡排序的本质,如果 \(a[i]>a[i+1]\) 的话两数就要交换(本题需升序,故符号为大于,降序反之)
发现我们在进行交换时做了没必要的比较
如果能直接找到形如 \(a[i]>a[i+1]\) 的两个数直接交换,那么交换的次数一共加起来最多是 \(O(n^2)\) 级别的
那么,对于一个待排序区间,只有找到形如 \(a[i]>a[i+1]\) 的两个数直接交换,一直到区间没有这对数,那么排序就完成了
下次对于已经交换过的一对相邻的数是不会再交换的,即不会再花费时间
那么总的复杂度就是 \(O((n^2+m)\log n)\) 的
可以接受
用线段树维护,初始时全为极大数(例如 \(0x3f3f3f3f\)),根据冒泡排序的交换顺序,找到最靠左的一对数交换
所以我们如果发现形如 \(a[i]>a[i+1]\) 的两个数,就把把线段树 \(i\) 位置的值改成 \(i\),然后维护一个 \(min\) 值,这样查区间最小就能找到最靠左的数
具体考虑,就是对于一个操作,我们找到最靠左的一对形如 \(a[i]>a[i+1]\) 的两个数直接交换,考虑交换后 \(a[i]\) 对 \(a[i-1]\) 的影响和 \(a[i+1]\) 对 \(a[i+2]\) 的影响。如果又产生了形如 \(a[i]>a[i+1]\) 的一对数,我们把线段树 \(i\) 位置的值改成 \(i\),直到再无这种数。当然两数交换后我们要把线段树 \(i\) 位置的值改成 \(0x3f3f3f3f\)
\(Code\)
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1505;
int n , m , L , R , a[N] , seg[N << 2];
inline void pushup(int k){seg[k] = min(seg[k << 1] , seg[k << 1 | 1]);}
inline void build(int l , int r , int k)
{
if (l == r)
{
seg[k] = 0x3f3f3f3f;
return;
}
int mid = (l + r) >> 1;
build(l , mid , k << 1);
build(mid + 1 , r , k << 1 | 1);
pushup(k);
}
inline void change(int x , int v , int l , int r , int k)
{
if (l == r && l == x)
{
seg[k] = v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) change(x , v , l , mid , k << 1);
if (x > mid) change(x , v , mid + 1 , r , k << 1 | 1);
pushup(k);
}
inline int query(int x , int y , int l , int r , int k)
{
if (x <= l && r <= y) return seg[k];
int mid = (l + r) >> 1 ,res = 0x3f3f3f3f;
if (x <= mid) res = min(res , query(x , y , l , mid , k << 1));
if (y > mid) res = min(res , query(x , y , mid + 1 , r , k << 1 | 1));
return res;
}
int main()
{
freopen("miku.in" , "r" , stdin);
freopen("miku.out" , "w" , stdout);
scanf("%d%d%d%d" , &n , &m , &L , &R);
build(1 , n , 1);
for(register int i = 1; i <= n; i++)
{
scanf("%d" , a + i);
if (i > 1 && a[i - 1] > a[i]) change(i - 1 , i - 1 , 1 , n , 1);
}
int x , y;
for(register int i = 1; i <= m; i++)
{
scanf("%d%d" , &x , &y);
if (x == y) continue;
while (1)
{
int l = query(x , y - 1 , 1 , n , 1);
if (l == 0x3f3f3f3f) break;
swap(a[l] , a[l + 1]);
change(l , 0x3f3f3f3f , 1 , n , 1);
if (l - 1 && a[l - 1] > a[l]) change(l - 1 , l - 1 , 1 , n , 1);
if (l + 2 <= n && a[l + 1] > a[l + 2]) change(l + 1 , l + 1 , 1 , n , 1);
}
}
for(register int i = L; i <= R; i++) printf("%d " , a[i]);
}
最新文章
- Reed-Solomon码,QR
- Fresco简单的使用—SimpleDraweeView
- PHPDBG
- Windows Phone7 快递查询
- VR全景,让VR不再是“空中楼阁“——智慧城市常诚
- linux pagecache限制与查看
- 规约模式(Specification Pattern)
- [struts2学习笔记] 第五节 编写struts2的action代码
- qq侧滑
- Android实训案例(一)——计算器的运算逻辑
- android最火的开源项目
- 初识Java——循环语句
- Windows下的OpenCVSharp配置
- BZOJ_2600_[Ioi2011]ricehub_二分答案
- 【Spark篇】---Spark中Shuffle文件的寻址
- laravel的消息队列剖析
- maven依赖和传递
- Centos7.2中安装pip
- Windows系统安装nginx及配置
- P1547 Out of Hay