luogu1975 排队（分块）

luogu1975 排队（分块）

给你一个长度为n的序列，每次交换给定的两个数，输出每次操作后的逆序对个数。

首先考虑求出刚开始的逆序对。接着相当于带修改的求区间中比x大的数。

可以用分块，每个块内排序，然后维护排序后的块。每次查询，块外二分，块内暴力。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=2e4+5, maxbar=2e2+5;
int n, a[maxn], b[maxn], ans;
int m, barlen, bel[maxn], cntbar;
struct node{
    int id, v;
}sted[maxn], t;
bool cmp(const node &a, const node &b){ return a.v<b.v; }

int tmp[maxn];
void msort(int l, int r){  //[l, r)
    if (l==r-1) return;
    int mid=(l+r)>>1;
    msort(l, mid); msort(mid, r);
    int i=l, j=mid, cnt=0;
    while (i<mid&&j<r){
        if (b[i]<=b[j]) tmp[cnt++]=b[i++], ans+=j-mid;
        else tmp[cnt++]=b[j++];
    }
    while (i<mid) tmp[cnt++]=b[i++], ans+=j-mid;
    while (j<r) tmp[cnt++]=b[j++];
    for (int i=0; i<cnt; ++i) b[l+i]=tmp[i];
}

//在[l, r)中大于x的数有几个
int bigger(int l, int r, int x){
    if (l>=r) return 0;
    int cnt=0; int bl=bel[l]+1, br=bel[r-1]-1;
    if (bel[l]==bel[r-1]){
        for (int i=l; i<r; ++i) if (a[i]>x) ++cnt;
        return cnt;
    }
    t.v=x;
    for (int i=bl; i<=br; ++i)
        cnt-=upper_bound(sted+i*barlen, sted+(i+1)*barlen, t, cmp)
                -(sted+(i+1)*barlen);
    for (int i=l; i==l||bel[i]==bel[i-1]; ++i)
        if (a[i]>x) ++cnt;
    for (int i=r-1; i==r-1||bel[i]==bel[i+1]; --i)
        if (a[i]>x) ++cnt;
    return cnt;
}

//在[l, r)中小于x的数有几个
int smaller(int l, int r, int x){
    if (l>=r) return 0;
    int cnt=0; int bl=bel[l]+1, br=bel[r-1]-1;
    if (bel[l]==bel[r-1]){
        for (int i=l; i<r; ++i) if (a[i]<x) ++cnt;
        return cnt;
    }
    t.v=x;
    for (int i=bl; i<=br; ++i)
        cnt+=lower_bound(sted+i*barlen, sted+(i+1)*barlen, t, cmp)
                -(sted+i*barlen);
    for (int i=l; i==l||bel[i]==bel[i-1]; ++i)
        if (a[i]<x) ++cnt;
    for (int i=r-1; i==r-1||bel[i]==bel[i+1]; --i)
        if (a[i]<x) ++cnt;
    return cnt;
}

//维护sorted数组
 int change(int pos, int num){
    for (int i=bel[pos]*barlen; i<(bel[pos]+1)*barlen; ++i)
        if (sted[i].id==pos){ pos=i; break; }
    sted[pos].v=num;
    while (sted[pos].v>sted[pos+1].v&&bel[pos]==bel[pos+1])
        swap(sted[pos], sted[pos+1]), ++pos;
    while (sted[pos].v<sted[pos-1].v&&bel[pos]==bel[pos-1])
        swap(sted[pos], sted[pos-1]), --pos;
    return pos;
}

void modify(int pos, int num){
    ans-=bigger(0, pos, a[pos]);
    ans-=smaller(pos, n, a[pos]);
    a[pos]=num; change(pos, num);
    ans+=bigger(0, pos, num);
    ans+=smaller(pos, n, num);
}

int main(){
    scanf("%d", &n); barlen=sqrt(n);
    for (int i=0; i<n; ++i){
        scanf("%d", &a[i]);
        b[i]=sted[i].v=a[i]; sted[i].id=i;
    }
    msort(0, n); printf("%d
", ans);
    for (int i=0; i<n; ++i) bel[i]=i/barlen; cntbar=bel[n-1]+1;
    for (int i=0; i<cntbar; ++i) 
        sort(sted+i*barlen, sted+min((i+1)*barlen, n), cmp);
    scanf("%d", &m); int x, y, tmp;
    for (int i=0; i<m; ++i){
        scanf("%d%d", &x, &y); --x; --y; tmp=a[x];
        modify(x, a[y]); modify(y, tmp);
        //for (int j=0; j<n; ++j) printf("%d ", sted[j].v);
        //puts("");
        printf("%d
", ans);
    }
    return 0;
}