2025 牛客寒假 6 部分题解 (E, D, H, I)
本文首先发布于个人博客，博客园不定期更新，推荐去我的博客阅读。I 小鸡的排列构造的 checker
看题第一反应是主席树。
定义 \(lst\) 表示值 \(x\) 出现的下标（因为是排列只会出现一次），则每次询问中要求的区间排名即为 \(lst\) 上 \(p\) 左侧在 \(\) 之间的数的个数，加上 \(l\) 就是答案。使用扫描线——离线树状数组解决即可。（如果你没有学过二位数点，类比树状数组求逆序对即可）。
赛时代码：
int n, m;cin >> n >> m;vector p(n + 1);for (int &num : p | views::drop(1)) { cin >> num;}struct Query { int l, r, c, id;};vector queryByCVal(n + 1);for (int i = 0; i < m; i++) { Query query; auto & = query; cin >> l >> r >> c; id = i; queryByCVal].push_back(query);}vector lst(n + 1);for (int i = 1; im;int parity = 0;for (int i = 1; i > l >> r >> c; parity = (r - l + 1) & 1;}if (parity == 1) { for (int i = n - 1; i >= 1; i -= 2) { cout
页:
[1]