题目

洛谷等许多 \(OJ\) 都有

思路

考试题，今日无意又做了一次

然后发现自己读错题了······

其实询问时只要 \(k\) 轮排序后的逆序对个数并不需要真的对序列进行更改

很显然 \(k\) 轮操作后每一个位置产生逆序对个数比 \(k\) 小的都没了，比 \(k\) 大的都减了 \(k\)

那么我们只要求每一个位置产生逆序对个数比 \(k\) 大的所有的和减去他们的个数乘 \(k\) 就好了

所以只要对交换时的两个数进行分类讨论，分别算下他们交换后对逆序对个数的影响就行了

开树状数组维护，一个记贡献的和，一个记个数（权值为下标）

\(Code\)

#include<cstdio>

#include<iostream>

#include<cstring>

#define LL long long

using namespace std;

const int N = 2e5 + 5;

int n , m , p[N] , num[N];

struct BIT{

	LL c[N];

	int lowbit(int x){return x & (-x);}

	void add(int x , int v){for(; x <= n; x += lowbit(x)) c[x] += v;}

	LL query(int x)

	{

		LL res = 0;

		for(; x; x -= lowbit(x)) res += c[x];

		return res;

	}

}a , b;

int main()

{

	scanf("%d%d" , &n , &m);

	for(register int i = 1; i <= n; i++)

	{

		scanf("%d" , &p[i]);

		num[i] = a.query(n) - a.query(p[i]);

		a.add(p[i] , 1);

	}

	memset(a.c , 0 , sizeof a.c);

	for(register int i = 1; i <= n; i++)

	if (num[i] != 0) a.add(num[i] , num[i]) , b.add(num[i] , 1);

	int t , k;

	for(; m; m--)

	{

		scanf("%d%d" , &t , &k);

		if (t == 1)

		{

			if (p[k] > p[k + 1])

			{

				if (num[k + 1] != 0) a.add(num[k + 1] , -num[k + 1]) , b.add(num[k + 1] , -1) , num[k + 1]--;

				if (num[k + 1] != 0) a.add(num[k + 1] , num[k + 1]) , b.add(num[k + 1] , 1);

			}

			else{

				if (num[k] != 0) a.add(num[k] , -num[k]) , b.add(num[k] , -1);

				num[k]++ , a.add(num[k] , num[k]) , b.add(num[k] , 1);

			}

			swap(p[k] , p[k + 1]) , swap(num[k] , num[k + 1]);

		}

		else {

			if (k >= n)

			{

				printf("0\n");

				continue;

			}

			printf("%lld\n" , a.query(n) - a.query(k) - (b.query(n) - b.query(k)) * k);

		}

	}

}

巴特西

[NOI Online 提高组]冒泡排序

题目

思路

\(Code\)

最新文章

热门文章