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;
}