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

2025.10 国庆集训模拟赛总结

image

把门视为点,找环,答案就是环的长度


image

d4faywvv7v

amzsfknpzp


image

先预处理前缀和

然后预处理f[i]表示满足j<i且aj==ai的最大的j。

答案就变成了:

image

第一问用树套树类结构维护

第二问直接二分第一问就行,因为第一问我们在先做了。

树套树太难写,所以直接BIT套vector就行了

https://www.cnblogs.com/cjl-world/p/14255060.html

#include <bits/stdc++.h>
using namespace std;struct Fenwick {int n;vector<int> bit;Fenwick() : n(0) {}Fenwick(int n_) { init(n_); }void init(int n_) {n = n_;bit.assign(n + 1, 0);}void add(int i, int v) {for (; i <= n; i += i & -i) bit[i] += v;}int sum(int i) {int s = 0;for (; i > 0; i -= i & -i) s += bit[i];return s;}int rangeSum(int l, int r) {if (r < l) return 0;return sum(r) - sum(l - 1);}
};void solve_case() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;vector<int> a(n + 1);for (int i = 1; i <= n; ++i) cin >> a[i];vector<int> prev(n + 1, 0);{unordered_map<int,int> last;last.reserve(n * 2);for (int i = 1; i <= n; ++i) {auto it = last.find(a[i]);if (it != last.end()) prev[i] = it->second;else prev[i] = 0;last[a[i]] = i;}}vector<int> f(n + 1, 0);{Fenwick bit(n);bit.init(n);unordered_map<int,int> last;last.reserve(n * 2);for (int i = 1; i <= n; ++i) {int v = a[i];if (last.count(v)) bit.add(last[v], -1);bit.add(i, 1);last[v] = i;int leftSum = prev[i] ? bit.sum(prev[i]) : 0;f[i] = bit.sum(i) - leftSum;}}vector<vector<int>> vec(n + 1);for (int i = 1; i <= n; ++i) {for (int j = i; j <= n; j += j & -j) vec[j].push_back(f[i]);}vector<vector<int>> nodeBit(n + 1);for (int j = 1; j <= n; ++j) {if (!vec[j].empty()) {sort(vec[j].begin(), vec[j].end());vec[j].erase(unique(vec[j].begin(), vec[j].end()), vec[j].end());nodeBit[j].assign(vec[j].size() + 1, 0);}}auto nodeAdd = [&](int j, int pos, int val) {auto &bit = nodeBit[j];int m = (int)bit.size() - 1;for (; pos <= m; pos += pos & -pos) bit[pos] += val;};auto nodeSum = [&](int j, int pos) {int s = 0;auto &bit = nodeBit[j];for (; pos > 0; pos -= pos & -pos) s += bit[pos];return s;};auto activate_idx = [&](int i) {for (int j = i; j <= n; j += j & -j) {if (vec[j].empty()) continue;int pos = int(lower_bound(vec[j].begin(), vec[j].end(), f[i]) - vec[j].begin());nodeAdd(j, pos + 1, 1);}};auto query_pref = [&](int pos, int k) {int res = 0;for (int j = pos; j > 0; j -= j & -j) {if (vec[j].empty()) continue;int cnt = int(upper_bound(vec[j].begin(), vec[j].end(), k) - vec[j].begin());res += nodeSum(j, cnt);}return res;};vector<vector<int>> idxByPrev(n + 1);for (int i = 1; i <= n; ++i) if (prev[i] >= 1) idxByPrev[prev[i]].push_back(i);struct Q1 { int l, r, k, id; };struct Q2 { int l, r, need, id; int lo, hi, mid, res; };vector<Q1> q1s;vector<Q2> q2s;q1s.reserve(q);q2s.reserve(q);for (int i = 0; i < q; ++i) {int t,l,r,k0;cin >> t >> l >> r >> k0;if (t == 1) q1s.push_back({l,r,k0,i});else q2s.push_back({l,r,k0,i,1, r - l + 1, -1, -1});}vector<long long> ans(q, -1);for (int j = 1; j <= n; ++j) if (!nodeBit[j].empty()) fill(nodeBit[j].begin(), nodeBit[j].end(), 0);int curL = n;sort(q1s.begin(), q1s.end(), [](const Q1 &x, const Q1 &y){ return x.l > y.l; });for (auto &qq : q1s) {while (curL >= qq.l) {for (int idx : idxByPrev[curL]) activate_idx(idx);--curL;}int tot = query_pref(qq.r, qq.k) - query_pref(qq.l - 1, qq.k);ans[qq.id] = tot;}if (!q2s.empty()) {bool any = true;while (true) {any = false;vector<int> act;act.reserve(q2s.size());for (int i = 0; i < (int)q2s.size(); ++i) {if (q2s[i].lo <= q2s[i].hi) {any = true;q2s[i].mid = (q2s[i].lo + q2s[i].hi) >> 1;act.push_back(i);}}if (!any) break;sort(act.begin(), act.end(), [&](int u, int v){ return q2s[u].l > q2s[v].l; });for (int j = 1; j <= n; ++j) if (!nodeBit[j].empty()) fill(nodeBit[j].begin(), nodeBit[j].end(), 0);curL = n;for (int idxQ : act) {auto &Q = q2s[idxQ];while (curL >= Q.l) {for (int idx : idxByPrev[curL]) activate_idx(idx);--curL;}int cnt = query_pref(Q.r, Q.mid) - query_pref(Q.l - 1, Q.mid);if (cnt >= Q.need) {Q.res = Q.mid;Q.hi = Q.mid - 1;} else {Q.lo = Q.mid + 1;}}}for (auto &Q : q2s) {if (Q.res == -1) ans[Q.id] = -1;else ans[Q.id] = Q.res;}}for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;if (!(cin >> T)) return 0;while (T--) solve_case();return 0;
}

image

直接按时间顺序处理每个区间,记录这个点能否被访问。

然后树剖维护即可。


image

找到最大的d,使得区间[l+d,r-d]不合法但是[l+d-1,r-d+1]合法,并将合法区建设为[l1,r1]。

容易发现[1,n]一定会被转移到[l1,r1],并且[l1,r1]后决策只有两种,就是先手动左面或者右面,然后就只能拿一边了,二分出两种情况,只要有一种是奇数先手就是赢得,所以直接判奇偶性即可

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

相关文章:

  • 详细介绍:https和http有什么区别-http各个版本有什么区别
  • CF2150F Cycle Closing
  • Easysearch 字段隐身之谜:source_reuse 与 ignore_above 的陷阱解析
  • QOJ856 Cactus 广义串并联图
  • CF2152 订题
  • 静态路由
  • Kruskal 重构树学习笔记
  • GJ Round 2025赛季
  • ASP.NET Core 中读取 UserAgent 的正确姿势
  • vLLM推理加速指南:7个技巧让QPS提升30-60%
  • Git学习记录(二):代码patch
  • 2025年10月化妆品代工厂最新推荐排行榜:聚焦 OEM/ODM/ 网红爆款需求,精选优质企业助品牌高效合作
  • Exchange安全漏洞分析:ProxyOracle攻击链详解
  • 牛客 周赛111 20251008
  • 本人于2025上半学期编码需要遵守的规范(参考腾讯内部编码规范)
  • 10.8 CSP-JS 模拟赛 T5. xor
  • 防抖 解释
  • 从零到一搭建:vue3+vite7+antfu+stylelint+githooks,全流程配置,附带源码,集成css变量使用,下载即用
  • bat批处理脚本文件-获取当前时间的几种方法
  • 二分图最大权完美匹配 KM算法
  • 2025.10.8模拟赛
  • Python 中的排序排序函数及区别
  • RL | 速读 IJCAI 2025 的强化学习论文
  • IDM弹窗解决 - -一叶知秋
  • PHP+MySQL开发语言 在线下单订水送水小脚本源码及搭建指南
  • Sliding Window Algorithm
  • 国庆模拟赛总结
  • 深入解析:video-audio-extractor:视频转换为音频
  • 10.8 CSP-JS 模拟赛 T4. discover
  • 20251008 模拟测 总结