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

2022 ICPC 香港 L

L. Permutation Compression

数据结构。

首先要让 \(a\) 删除数后得到 \(b\),显然要满足 \(b\)\(a\) 的子集。

因为每次删除的都是最大值,考虑从大往小枚举可删除的数,找左右两边比当前数大的位置,假设 \(l\)\(r\) 代表左右两边比当前数大的位置,那么 \([l+1,r-1]\) 这个区间内都以 \(i\) 为最大值,那么只要存在 \(L_i\) 小于等于 \(r-l-1\) 就可以把 \(i\) 删掉;把 \(i\) 删掉后,为了防止 \(i\) 对后续的影响,需要标记一下,在后续有 \(j\) 找两边最大值时越过了 \(i\) 的位置,需要减掉它的影响,所以对 \(j\) 来说,删除 \(j\) 的区间长度为 \(r-l-1-cnt\)\(cnt\) 代表 \([l+1,r-1]\) 区间内有多少个比 \(j\) 大的数被删掉了,可以用线段树维护这个过程。

最后比较一下每个数可删除的区间长度是不是都能找到一个 \(L_i\) 对应即可,可以将两者排序后一一比较即可。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(std::vector(n_, v_));}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F &&pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F &&pred) {return findLast(1, 0, n, l, r, pred);}
};constexpr int inf = 1E9;struct Info {int max = -inf, cnt = 0;
};Info operator+(const Info &l, const Info &r) {return {std::max(l.max, r.max), l.cnt + r.cnt};
}void solve() {int n, m, k;std::cin >> n >> m >> k;SegmentTree<Info> seg(n);std::vector<int> a(n), b(m), c(k), vis(n), pos(n);for(int i = 0; i < n; i += 1) {std::cin >> a[i];a[i] -= 1;pos[a[i]] = i;seg.modify(i, {a[i], 0});}for(int i = 0; i < m; i += 1) {std::cin >> b[i];b[i] -= 1;vis[b[i]] = 1;}for(int i = 0; i < k; i += 1) {std::cin >> c[i];}int idx = 0;for(int i = 0; i < n; i += 1) {if(idx < m && a[i] == b[idx]) {idx += 1;}}if(idx != m) {std::cout << "NO\n";return;}std::vector<int> sz;for(int i = n - 1; i >= 0; i -= 1) {if(vis[i]) continue;int l = -1,r = n;auto x = seg.findLast(0, pos[i], [&](auto p) {return p.max > i;});l = x;x = seg.findFirst(pos[i] + 1, n, [&](auto p) {return p.max > i;});if(x != -1) {r = x;}l += 1, r -= 1;sz.push_back(r - l + 1 - seg.rangeQuery(l, r + 1).cnt);seg.modify(pos[i], {0, 1});}if(c.size() < sz.size()) {std::cout << "NO\n";return;}sort(c.begin(), c.end());sort(sz.begin(), sz.end());for(int i = 0; i < sz.size(); i += 1) {if(c[i] > sz[i]) {std::cout << "NO\n";return;}}std::cout << "YES\n";}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=31575

相关文章:

  • 2025 年乡村波形护栏厂家最新推荐排行榜:聚焦优质企业,助力乡村道路安全建设选型参考道路/高速/乡村道路/乡村公路波形护栏板厂家推荐
  • 员工签到微信小程序系统:企业考勤管理的高效解决方案
  • AI 姓氏头像生成小程序管理系统:专属头像定制与流量变现解决方案
  • AI元人文:元规则、元道德与哪吒模型
  • 知音 CMS:全场景音频与小说分销一体化解决方案
  • 2025年锅炉厂家最新权威推荐榜:工业锅炉、燃气锅炉、电热锅炉、蒸汽锅炉专业制造商实力解析与选购指南
  • CCSP2025 游记
  • powershell上移文件夹下的所有文件
  • 2025 年国内算力云公司最新推荐排行榜:聚焦 AI 训推与 MaaS 服务,助力企业精准选优质合作伙伴算力云大模型/算力云深度学习/微调算力云/蓝耘算力云公司推荐
  • 2025 年国内云计算公司最新推荐排行榜:聚焦 AI 训推与大模型需求的优质厂商精选指南模型训推云计算/大模型云计算/AI开发云计算公司推荐
  • 2025年防水连接器厂家最新推荐排行榜,连接器,航空插头,工业网线,专业防水与耐用性能深度解析
  • 2025年清洗机厂家最新权威推荐榜:高压清洗机、工业清洗机、超声波清洗机源头厂家综合实力解析
  • 2025年微弧氧化厂家最新推荐排行榜,微弧氧化/铝合金微弧氧化/镁合金微弧氧化/黑色微弧氧化/钛合金微弧氧化/微弧氧化技术加工,渔具/雷达/医疗器械微弧氧化专业供应商
  • 2025 年永磁电机厂家最新推荐排行榜:聚焦高效节能电机品牌,助力采购者精准选优质产品直流/无刷/风机/节能/高效永磁电机厂家推荐
  • 2025年武汉防水公司最新权威推荐榜:商铺装修防水,别墅补漏防水,厂房防潮防水专业施工与长效保障口碑之选
  • Prometheus源码专题【左扬精讲】—— 监控系统 Prometheus 3.4.0 源码解析:recording rule
  • 2025年液压阀块厂家最新推荐排行榜,液压阀块加工,阀块零件机加工,液压阀加工,各种液压阀块专业制造商精选
  • 2025年干燥设备厂家最新权威推荐榜:小型喷雾/实验室离心喷雾/双锥回转真空/搪瓷双锥/旋转闪蒸/振动流化床/真空耙式/单层带式/多层带式/立式沸腾/卧式沸腾/滚筒刮板干燥机
  • 2025 年国内冷却塔生产厂家最新推荐排行榜:聚焦节能优势与多行业适配性的优质企业精选工业/横流/逆流/全钢/圆型/方形冷却塔厂家推荐
  • 2025 冷水机组厂家最新推荐排行榜:聚焦节能技术与客户口碑,精选国产实力品牌解析
  • 如何实现cmd可以访问conda但不能通过默认环境访问python
  • Gephi 0.9.2超星系保姆级下载安装教程及配置教程(新手适用,附安装包下载)
  • Perforce:无法删除Stream Depot怎么处理
  • 2025 加工中心小程序最新推荐排行榜:涵盖五轴 / 卧式 / 立式机型,揭秘实力品牌核心优势
  • Perforce:Stream实战指南
  • C语言
  • 2025 年无氧烘箱厂家推荐榜:洁净/高真空/HMDS/真空无氧烘箱/聚焦环保节能与洁净需求,这家企业成行业优选
  • 2025年立式扒胎机厂家最新权威推荐榜:专业设备批发与高效服务口碑之选
  • 植物大战僵尸杂交版下载安装教程:PC/安卓/iOS 全平台保姆级攻略【2025最新版】
  • 洛谷题单指南-进阶数论-CF757B Bashs Big Day