萌新求助,思路是维护每个数在他前面比它大的数的数量 的前缀前缀和,然后也过了前4割点,为什么后面的点我的程序输出和答案相差很大?是思路错了还是实现错了?
/*
name: [NOI Online #1 提高组] 冒泡排序
id: P6186
date: 2022/12/23
*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, m, p[N];
ll bit[3][N], b[N], ans;
void add(int op, int x, ll v){
while(x <= n){
bit[op][x] += v;
x += x & (-x);
}
}
ll qry(int op, int x){
ll ans = 0;
while(x){
ans += bit[op][x];
x -= x & (-x);
}
return ans;
}
ll ask(int op, int l, int r){
return qry(op, r) - qry(op, l-1);
}
int main(){
// freopen("P6186_5.in", "r", stdin);
// freopen("_out.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i){
scanf("%d", &p[i]);
b[i] = ask(0, p[i]+1, n);
ans += b[i];
add(0, p[i], 1);
add(1, b[i]+1, n-(b[i]+1)+1);
add(2, b[i]+1, 1);
}
while(m--){
int t, c;
scanf("%d%d", &t, &c);
if(t == 1){
if(p[c] > p[c+1]){
-- ans;
add(1, b[c+1]+1, -(n-(b[c+1]+1)+1));
add(2, b[c+1]+1, -1);
-- b[c+1];
add(1, b[c+1]+1, (n-(b[c+1]+1)+1));
add(2, b[c+1]+1, 1);
} else {
++ ans;
add(1, b[c]+1, -(n-(b[c]+1)+1));
add(2, b[c]+1, -1);
++ b[c];
add(1, b[c]+1, n-(b[c]+1)+1);
add(2, b[c]+1, 1);
}
swap(p[c], p[c+1]);
swap(b[c], b[c+1]);
} else {
if(c >= n){
puts("0");
continue;
}
ll res = ask(1, 1, c) - ask(2, 1, c) * (ll)(n-c);
printf("%lld\n", ans - n*c + res);
}
}
return 0;
}