BZOJ2141 排队 题解

题目链接：#2141. 排队

题意：

一句话题意：

给定 $n$ 个数，$Q$ 次询问，每次交换两个不同位置的数，然后输出逆序对数。

$1 \le n \le 2\times 10^4,~1\le Q \le 2 \times 10^3$

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。

不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为 $h_i (1\le h_i \le 10^9)$ ，我们定义一个序列的杂乱程度为：满足 $h_i>h_j$ 的 $(i, j)$ 数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

这题还是比较水的。

首先朴素的逆序对不会有人不会吧（不会吧不会吧 ，不会的戳这里

考虑一次修改会对答案产生什么影响

设交换 $a_l$ 和 $a_r$ ，则显然只有 $(l,r)$ 的数会影响答案

于是我们依次考虑每个 $a_i (l < i < r)$

经过观察可以发现， $a_i$ 对答案的影响和它与 $a_l,a_r$ 的大小有关

则 $a_i$ 对答案的贡献为

$$\mathrm{sgn}(a_i-a_l) + \mathrm{sgn}(a_r-a_i)$$

其中 $\mathrm{sgn}(x)=\begin{cases}1,&x>0\\0,&x=0\\ -1,&x<0\end{cases}$

时间复杂度 $O(n \log n + nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e4+15)

int n,Q;
int a[N],b[N],tmp[N];
int sgn(int x){return (x>0)-(x<0);}
int solve(int l,int r)
{
    if(l==r) return 0;
    int mid=(l+r) >> 1,res=0;
    res+=solve(l,mid)+solve(mid+1,r);
    int i=l,j=mid+1,k=l;
    for(; i<=mid; i++)
    {
        while(b[i]>b[j] && j<=r)
            res+=mid-i+1,tmp[k++]=b[j++];
        tmp[k++]=b[i];
    }
    while(j<=r) tmp[k++]=b[j++];
    for(int t=l; t<=r; t++) b[t]=tmp[t];
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i],b[i]=a[i];
    int ans=solve(1,n),l,r;
    cout << ans << '\n';
    for(cin >> Q; Q--; )
    {
        cin >> l >> r; if(l>r) swap(l,r);
        if(a[l]==a[r]) cout << ans << '\n';
        else
        {
            for(int i=l; i<r; i++)
                ans+=sgn(a[i]-a[l])+sgn(a[r]-a[i]);
            swap(a[l],a[r]);
            cout << ans << '\n';
        }
    }
    return 0;
}