JZOJ 5947 初音未来

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

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

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

对于一个操作，我们一直找该区间内的相邻逆序对，对于一组相邻逆序对 (x,x+1)，我们按如下几步处理： 1. 交换 ax,ax+1。 2. 删除线段树上位置 x 的逆序对。 3. 更新新的 ax 对 ax−1 的贡献。 4. 更新 ax+2 对新的 ax+1 的贡献。

最多交换 O(n2) 次，总复杂度 O((n2+m)logn)，可以承受。

代码：

#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]);
}