【题目链接】:

【题意】

给你一个初始序列1..n顺序

然后每次让你交换任意两个位置上面的数字;

让你实时输出q个操作,每个操作过后整个序列逆序对的个数;

【题解】

分块法;

分成根号n个块.

每个块按照数字升序排;

然后再用一个a数组具体记录每个位置上的数字;

找逆序对的方式如下:

对于交换l,r

查找l+1..r-1当中比a[l]小的数字,比a[l]大的数字;

查找l+1..r-1当中比a[r]小…比..大的数字;

根据这4个参数来更新逆序对的个数;

这就要求查询l+1..r-1当中比x小的数的个数;

对于belong[l]块,->belong[i]指的是第i个位置上面的数字对应的是第几个块

在l..R[belong[l]]当中找比x小的数->暴力枚举就好

在L[belong[r]]..r当中找比x小的数->也是暴力枚举；

然后在belong[l]+1..belong[r]-1这些块中,用二分(lower_bound)查找比x小的数的个数(因为是有序的,所以可以这样做);

然后如果a[l]< a[r]则再多递增一个逆序对否则减少1个

然后交换这两个数;

->有序的vector中交换,然后原数组a[i]中也要交换;

vector中的交换也可以用lower_bound实现;

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define ps push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)#define ref(x) scanf("%lf",&x)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int K = 500+20;//500个块const int N = 2e5 + 100;int n,q,belong[N],l[K],r[K],a[N];LL ans = 0;vector 
        
          v[K];void init(){    int len = sqrt(n);    if ((len*len) != n)    {        len++;    }    rep1(i, 1, n)    {        belong[i] = ((i - 1) / len) + 1;        v[belong[i]].ps(i);        a[i] = i;    }    rep1(i, 1, len)    {        l[i] = len*(i - 1) + 1;        r[i] = len*i;    }    if ((len*len) != n)        r[len] = n;}LL smaller(int L, int R, LL x){    if (L > R) return 0;    LL cnt = 0;    if (belong[L] == belong[R])    {        rep1(i, L, R)        {            if (a[i] < x)                cnt++;        }        return cnt;    }    rep1(i, L, r[belong[L]])    {        if (a[i] < x)            cnt++;    }    rep1(i, belong[L] + 1, belong[R] - 1)    {        LL pos = lower_bound(v[i].begin(), v[i].end(), x) - v[i].begin()+1;        cnt += pos;    }    rep1(i, l[belong[R]], R)        if (a[i] < x)            cnt++;    return cnt;}void change(int l, int r){    int x = belong[l],y = belong[r];    v[x].erase(lower_bound(v[x].begin(), v[x].end(), a[l]));    v[x].insert(upper_bound(v[x].begin(), v[x].end(), a[r]),a[r]);    v[y].erase(lower_bound(v[y].begin(), v[y].end(), a[r]));    v[y].insert(upper_bound(v[y].begin(), v[y].end(), a[l]), a[l]);    swap(a[l], a[r]);}int main(){    //freopen("F:\\rush.txt", "r", stdin);    rei(n), rei(q);    init();    rep1(i, 1, q)    {        int l, r;        rei(l), rei(r);        if (l > r) swap(l, r);        if (l == r)        {            printf("%lld\n", ans);            continue;        }        LL temp = smaller(l + 1, r - 1, a[l]);        LL temp1 = r - 1 - (l + 1) + 1 - temp;        //temp个数比a[l]小 temp1个数比a[l]大        //之后a[l]会跑到r位置         ans -= temp; ans += temp1;        temp = smaller(l + 1, r - 1, a[r]);        temp1 = r - 1 - (l + 1) + 1 - temp;        //temp个数比a[r]小 temp1个数比a[r]大        //之后a[r]会跑到l位置        ans += temp; ans -= temp1;        if (a[l] < a[r])            ans++;        else            ans--;        change(l, r);        printf("%lld\n", ans);    }    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);    return 0;}