题解：P15595 [ICPC 2020 Jakarta R] Shopping Changes
kohahahara
·
·
题解
P15595 [ICPC 2020 Jakarta R] Shopping Changes
题意：
有 m 次询问，第 i 次询问给出一个长 l_i 的序列，问将一个长为 n 的连续段插入序列的间隙中可以得到的最小的逆序对数。
思路：
首先求出连续段本身和序列本身所有的逆序对数，这些是无法避免会贡献到答案里的，离散化后用树状数组可以完成这一步。
考虑把连续段插入哪个位置所得的逆序对数最少，对每一个位置设 bg_i 表示 w_i 比连续段中多少个数要大，lw_i 表示 w_i 比连续段中多少个数要小，将连续段排序后可以二分解决。
### 细节：
1. 要开 long long。
2. 不能每次询问都 memset 树状数组，会超时。
3. 因为我们考虑的是位置与位置之间的空隙，所以 $pre_i$ 与 $suf_i$ 的下标含义要考虑清楚。
4. 树状数组下标不能为 $0$。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,len,bas;
const int N = 2e5+10,inf=1e18;
int c[N],b[N*2],c2[N];
int l[N],bg[N],lw[N];
vector<int> w[N];
int t[2*N],pre[N],suf[N];
int lowbit(int x){return x&(-x);}
void add(int p,int x){
for(int i=p;i;i-=lowbit(i)){
t[i]+=x;
}
}
int ask(int p){
int res=0;
for(int i=p;i<=len+1;i+=lowbit(i))res+=t[i];
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i];c2[i]=c[i];
b[++len]=c[i];
}
sort(c2+1,c2+1+n);
for(int i=1;i<=m;i++){
cin>>l[i];
for(int j=1;j<=l[i];j++){
int x;
cin>>x;
w[i].push_back(x);
b[++len]=x;
}
}
sort(b+1,b+1+len);
len=unique(b+1,b+1+len)-b-1;
for(int i=1;i<=n;i++){
int x=lower_bound(b+1,b+1+len,c[i])-b;
bas+=ask(x+2);
add(x+1,1);
}
memset(t,0,sizeof(t));
for(int i=1;i<=m;i++){
int num=0;
for(int j=0;j<l[i];j++){
int v=w[i][j];
int x=lower_bound(b+1,b+1+len,v)-b;
num+=ask(x+2);add(x+1,1);
bg[j]=lower_bound(c2+1,c2+1+n,v)-c2-1;
lw[j]=n-(upper_bound(c2+1,c2+1+n,v)-c2)+1;
}
pre[0]=0;
for(int j=1;j<=l[i];j++){
pre[j]=pre[j-1]+bg[j-1];
}
suf[l[i]]=0;
for(int j=l[i]-1;j>=0;j--){
suf[j]=suf[j+1]+lw[j];
}
int ans=inf;
for(int j=0;j<=l[i];j++){
ans=min(ans,bas+num+pre[j]+suf[j]);
}
cout<<ans<<endl;
for(int j=0;j<l[i];j++){
pre[j]=suf[j]=0;
int x=lower_bound(b+1,b+1+len,w[i][j])-b;
add(x+1,-1);
}
}
return 0;
}
```