我的代码有没有素质?
查看原帖
我的代码有没有素质?
390770
D2T1xubiaoshi楼主2022/12/23 23:24

萌新求助,思路是维护每个数在他前面比它大的数的数量 的前缀前缀和,然后也过了前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;
}

2022/12/23 23:24
加载中...