思路
发现如果直接维护序列的话需要支持：序列插入删除，动态前缀最大值，然后再维护答案。
这个东西根本没法弄。所以我们考虑逆序对的性质。
先考虑 的怎么做。
发现一次操作最多使一个数向前移动一个位置，并且一共可以移动的次数，为其左侧比它大的数字的个数，设为 。
所以我们可以考虑维护 ，因为其和即为逆序对个数。
每次操作会使 减一，减到零之后就对答案没有贡献了，所以 在时间轴上对答案的贡献是：首项为 ，末项为 ，公差为 的等差数列。
现在我们考虑原问题。
因为 单调不降，所以对于 的 ，其在 会对答案一直产生 的贡献；在 才会对答案产生等差数列的贡献。
这相当于对于时间轴 前缀加 ， 区间加等差数列，最后前缀查询。
线段树或者差分维护一下就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| const int N = 2e5+10;
int n,m,a[N],c[N],r[N];
ll ans,sum[N];
int tr[N];
inline void add(int x){
for(int i=x;i<=n;i+=i&(~i+1)) ++tr[i];
}
inline int query(int x){
int res = 0;
for(int i=x;i;i-=i&(~i+1)) res += tr[i];
return res;
}
int main(){
read(n);
for(int i=1;i<=n;++i){
read(a[i]);
c[i] = query(n)-query(a[i]);
ans += c[i];
add(a[i]);
}
read(m);
for(int i=1;i<=m;++i) read(r[i]);
for(int i=1;i<=n;++i){
int l = lower_bound(r+1,r+1+m,i)-r;
++sum[l];
--sum[Min(l+c[i],m+1)];
}
for(int i=1;i<=m;++i) sum[i] += sum[i-1];
for(int i=1;i<=m;++i){
ans -= sum[i];
printf("%lld\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
|