类似排序那题，但是按照原来的做法只有部分分。
线段树分裂合并会 T 成 \(70\)。
有一个很骚的做法：模拟冒泡的过程。
冒泡的思想是依次交换相邻的逆序对，要做 \(O(n^2)\) 次。
因此我们用线段树维护一个区间内第一组相邻的逆序对。
实际上很好维护，对于一个位置 \(i\)，如果 \(a_i > a_{i + 1}\)，则在线段树上把这个位置修改成 \(i\)，否则为正无穷。
区间查询就是一个区间最小值的过程。
对于一个操作，我们一直找该区间内的相邻逆序对，对于一组相邻逆序对 \((x,x + 1)\)，我们按如下几步处理： 1. 交换 \(a_x,a_{x + 1}\)。 2. 删除线段树上位置 \(x\) 的逆序对。 3. 更新新的 \(a_x\) 对 \(a_{x - 1}\) 的贡献。 4. 更新 \(a_{x + 2}\) 对新的 \(a_{x + 1}\) 的贡献。
最多交换 \(O(n^2)\) 次，总复杂度 \(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
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]);
}