JZOJ 5947.初音未来

类似排序那题,但是按照原来的做法只有部分分。
线段树分裂合并会 T 成 7070

有一个很骚的做法:模拟冒泡的过程。
冒泡的思想是依次交换相邻的逆序对,要做 O(n2)O(n^2) 次。
因此我们用线段树维护一个区间内第一组相邻的逆序对。

实际上很好维护,对于一个位置 ii,如果 ai>ai+1a_i > a_{i + 1},则在线段树上把这个位置修改成 ii,否则为正无穷。
区间查询就是一个区间最小值的过程。

对于一个操作,我们一直找该区间内的相邻逆序对,对于一组相邻逆序对 (x,x+1)(x,x + 1),我们按如下几步处理:

  1. 交换 ax,ax+1a_x,a_{x + 1}
  2. 删除线段树上位置 xx 的逆序对。
  3. 更新新的 axa_xax1a_{x - 1} 的贡献。
  4. 更新 ax+2a_{x + 2} 对新的 ax+1a_{x + 1} 的贡献。

最多交换 O(n2)O(n^2) 次,总复杂度 O((n2+m)logn)O((n^2 + m)\log{n}),可以承受。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
using namespace std;
const int N = 1500;
const int M = 1e6;
int n,m,L,R,a[N + 5];
struct node
{
int pos;
int lson,rson;
} seg[(N << 2) + 10];
int seg_tot,rt;
void change(int x,int k,int &p,int tl,int tr)
{
if(!p)
p = ++seg_tot;
if(tl == tr)
{
seg[p].pos = k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
change(x,k,ls(p),tl,mid);
else
change(x,k,rs(p),mid + 1,tr);
seg[p].pos = min(seg[ls(p)].pos,seg[rs(p)].pos);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].pos;
int mid = tl + tr >> 1;
int ret = 0x3f3f3f3f;
if(l <= mid)
ret = min(ret,query(l,r,ls(p),tl,mid));
if(r > mid)
ret = min(ret,query(l,r,rs(p),mid + 1,tr));
return ret;
}
int main()
{
freopen("miku.in","r",stdin);
freopen("miku.out","w",stdout);
seg[0].pos = 0x3f3f3f3f;
scanf("%d%d%d%d",&n,&m,&L,&R);
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,rt,1,n);
}
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
if(l == r)
continue;
while(1)
{
int x = query(l,r - 1,rt,1,n);
if(x == 0x3f3f3f3f)
break;
swap(a[x],a[x + 1]);
if(x > 1 && a[x - 1] > a[x])
change(x - 1,x - 1,rt,1,n);
change(x,0x3f3f3f3f,rt,1,n);
if(x + 1 < n && a[x + 1] > a[x + 2])
change(x + 1,x + 1,rt,1,n);
}
}
for(register int i = L;i <= R;++i)
printf("%d ",a[i]);
}