当前位置: 首页 > news >正文

2025/10/20~2025/?/? 做题笔记 - sb

2025/10/20

AT_arc181_d Prefix Bubble Sort

很显然的有每一次交换都会恰好减少一个逆序对,于是题目转化为每次会产生多少次交换。

那么考虑如何统计交换次数

  • 发现当前缀 max 变化时不会产生答案,但是这个折线非常困难维护,不考虑这种做法
  • 考虑每个数往后交换多少次是难的,那么考虑有多少个数会往前交换。可以发现当前面有数大于这个数时,这个数一定会产生一次交换,那么直接统计有多少个数前面有大于它的数即可。由于题目限制了 \(A_i\) 单调不减,直接线段树简单维护即可

没有想到可以换一种贡献方式,老是在一棵树上吊死。

Code

#include <iostream>using namespace std;
using ll = long long;const int kN = 2e5 + 1;int n, m, a[kN];
ll ans;
struct BIT {int tr[kN];void Update(int x, int k) {for (; x < kN; x += x & -x)tr[x] += k;}int Query(int x) {int res = 0;for (; x; x -= x & -x)res += tr[x];return res;}
} Bit;
struct Point {int mn, cnt, tag;
} tr[kN << 2];void Func(int x, int k) {tr[x].mn += k, tr[x].tag += k;
}
void Pushdown(int x) {Func(x * 2, tr[x].tag), Func(x * 2 + 1, tr[x].tag), tr[x].tag = 0;
}
void Find(int x, int l, int r) {if (tr[x].mn > 0)return;if (l == r)return tr[x].mn = tr[x].tag = 1e9, tr[x].cnt = 0, void();Pushdown(x);int m = (l + r) / 2;Find(x * 2, l, m), Find(x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
void Update(int nl, int nr, int x = 1, int l = 1, int r = n) {if (nl <= l && r <= nr)return Func(x, -1), Find(x, l, r);Pushdown(x);int m = (l + r) / 2;if (nl <= m)Update(nl, nr, x * 2, l, m);if (nr > m)Update(nl, nr, x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
void Build(int x = 1, int l = 1, int r = n) {if (l == r)return tr[x].cnt = a[l] > 0, tr[x].mn = a[l] ? a[l] : 1e9, void();int m = (l + r) / 2;Build(x * 2, l, m), Build(x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
int Query(int nl, int nr, int x = 1, int l = 1, int r = n) {if (nl <= l && r <= nr)return tr[x].cnt;Pushdown(x);int m = (l + r) / 2, res = 0;if (nl <= m)res = Query(nl, nr, x * 2, l, m);if (nr > m)res += Query(nl, nr, x * 2 + 1, m + 1, r);return res;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> n;for (int i = 1, x; i <= n; i++) {cin >> x;a[i] = Bit.Query(n - x + 1), Bit.Update(n - x + 1, 1), ans += a[i];}Build();cin >> m;for (int i = 1, x; i <= m; i++) {cin >> x;ans -= Query(1, x), Update(1, x);cout << ans << '\n';}return 0;
}

http://www.hskmm.com/?act=detail&tid=35353

相关文章:

  • 10-20 Extra-Problem 总结
  • ansible底层文件传输机制中默认模式遇到权限拒绝后启用管道模式可以得到解决
  • 10月20日记
  • Rust 编译加速的最佳实践
  • 20232304 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • 笔记本 光驱 的内部结构及用法: 应急强大的系统启动 (恢复) 光盘 (DVD+R/RW)
  • Android 源码解析系列1- Android init 进程启动流程
  • 分层图
  • 10.20总结
  • 学习相关
  • 题解:Luogu P10644 [NordicOI 2022] 能源网格 Power Grid
  • 题解:Luogu P10004 [集训队互测 2023] Permutation Counting 2
  • 题解:Luogu P2075 区间 LIS
  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统