Luogu P6186 [NOI Online 提高组]冒泡排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Luogu P6186 [NOI Online 提高组]冒泡排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2118字,纯文字阅读大概需要4分钟。
内容图文
![Luogu P6186 [NOI Online 提高组]冒泡排序](/upload/InfoBanner/zyjiaocheng/1220/5b49c5670b4a4c76a62705155afe6b23.jpg)
大意就是给定一个序列,对其进行两个操作,交换相邻的两个数,或者对全序列进行一遍冒泡排序。
观察题面可以发现
- 当ti=1时我们需要交换相邻的两个数
- 当ti=2时我们需要对全序列进行冒泡排序
由于数据量极大,显然暴力的模拟一定不行
我们记录第i位数前面比它大的数的数量为\(before[i]\),显然,当前序列的总逆序对数量就是所有的\(before\)之和
通过对冒泡排序的观察,我们可以发现,每一遍冒泡排序都会使得所有\(before[i]=max(before[i]-1,0)\)
我们采用树状数组差分维护这一操作,令\(sum(t)\)为当\(ti=2\),\(k=t\)时的答案
在数组最前面加入当前序列总逆序对数量,然后在第\(i\)位放\(before\)大于\(i\)的数字的数量的相反数,因为这些数字在第\(i\)轮逆序对数均会减\(1\)
最后利用差分直接求解即可
#include <bits/stdc++.h>
using namespace std;
int input[200005], before[200005], record[200005];
int n;
long long tree[200005];
inline int lowbit(int x)
{
return x & (-x);
}
void add(int x, long long val)
{
for (; x <= n; x += lowbit(x))
tree[x] += val;
return;
}
long long sum(int x)
{
long long res = 0;
for (; x > 0; x -= lowbit(x))
res += tree[x];
return res;
}
int main()
{
int m;
scanf("%d%d", &n, &m);
long long tot = 0; //先记录初始状态下的逆序对数量
for (int i = 0; i < n; i++)
{
scanf("%d", input + i);
before[i] = i - sum(input[i]); //记录比它小的数字数量
tot += before[i]; //最开始tot记录初始的答案
record[before[i]]++; //桶,record[i]=前面有i个数字比它大的数字的数量
add(input[i], 1); //树状数组作桶
}
memset(tree, 0, sizeof(tree)); //清空
add(1, tot); //实现差分,先把序列总逆序对数量放在最前面
tot = 0;
for (int i = 0; i < n; ++i)
{
tot += record[i]; //每次tot记录的是前面有小于等于i个数字比它大的数字的数量
//则n-tot即为前面有大于i个数字比它大的数字的数量
add(i + 2, -(n - tot)); //实现差分,在这一个位置会有n-tot个数字逆序对数减1
//由于下标问题,i必须+2,这样当i=0时就会储存在第2位,而第1位是放总逆序对数的
}
for (int i = 0, opt, x; i < m; i++)
{
scanf("%d%d", &opt, &x);
x = min(x, n - 1); //对opt=2的情况进行优化
if (opt == 1)
{
x--;
if (input[x] < input[x + 1])
{
swap(input[x], input[x + 1]);
swap(before[x], before[x + 1]);
add(1, 1); //逆序对总数量增加1
add(before[x + 1] + 2, -1); //由于before[x+1]增加了,所以在原before[x+1]轮时也可以使逆序对-1,所以记录-1
before[x + 1]++; //input[x]交换到x+1位上后,前面比它大的数量增加了1
}
else
{
swap(input[x], input[x + 1]);
swap(before[x], before[x + 1]);
add(1, -1); //逆序对总数量减少1
before[x]--; //input[x+1]交换到x位上后,前面的比它大的数量减少了1
add(before[x] + 2, 1); //由于before[x]减少了,所以在原before[x]轮时无法使逆序对减少,所以记录1
}
}
else
printf("%lld\n", sum(x + 1)); //直接输出答案
}
return 0;
}
原文:https://www.cnblogs.com/macesuted/p/solution-P6186.html
内容总结
以上是互联网集市为您收集整理的Luogu P6186 [NOI Online 提高组]冒泡排序全部内容,希望文章能够帮你解决Luogu P6186 [NOI Online 提高组]冒泡排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。