首页 > 其他分享 >题解 QOJ2559【Endless Road】/ SS241006D【套路题】

题解 QOJ2559【Endless Road】/ SS241006D【套路题】

时间：2024-10-07 19:43:47浏览次数：1  
标签：return QOJ2559 题解 SS241006D int vec 端点 区间 id

Petrozavodsk Winter 2022. Day 2. KAIST Contest + KOI TST 2021
XXII Open Cup named after E.V. Pankratiev, Grand Prix of Daejeon

题目描述

现在有 \(10^9\) 个花盆，依次编号为 \(1,2,\dots,10^{9}\) 。

给定 \(n\) 个二元组 \(L_i,R_i(L_i<R_i)\) ，我们将进行 \(n\) 次以下操作：

  1. 设当前第 \(i\) 个二元组的权值是满足花盆 \(x\) 为空且 \(L_i<x\le R_i\) 的 \(x\) 数量。选出未被选过且权值最小的二元组 \(p\) 。如果存在多个权值最小的二元组，选择其中编号最小的。

  2. 对于 \(L_p<x\le R_p\) ，在花盆 \(x\) 中种上花。

请求出每次操作选择出的二元组 \(p\)。

保证对于 \(1\le i<j\le n,R_i-L_i\le R_j-L_j\) 。

对于所有数据，\(1\le n\le 2.5\times 10^5,0\le L_i<R_i\le 10^{9}\)，对于 \(1\le i<j\le n\) ，\(R_i-L_i\le R_j-L_j\) 。

solution

改成左闭右开。离散化。跳过一些暴力后，我们发现：两个互相包含的区间 \(i<j, [L_i, R_i)\subseteq[L_j, R_j)\)，无论如何操作，都是 \(i\) 先被栽种，\(j\) 后被栽种。可以对花盆的位置分类，发现 \(i\) 区间的权值总是不大于 \(j\) 的。而如果我们去掉包含其它区间的区间，剩下的都是左、右断点分别单调的区间（称作合法区间），对这些合法区间我们将其存放在线段树上它们各自左端点的位置，然后可以二分、懒标记等一系列操作进行栽种（发现权值减少的合法区间的左端点连续）。

剩下的问题是删除一个合法区间后怎么找到新的合法区间。我们将所有区间按照右端点升序为第一关键字，左端点降序为第二关键字，以及自身编号升序为第三关键字，对所有区间进行排序，使每个区间获得一个排名。这样排序后，两个互相包含的区间 \(i<j, [L_i, R_i)\subseteq[L_j, R_j)\)，\(i\) 的排名一定比 \(j\) 小（相当于给这个包含关系的 DAG 找了一个拓扑序）。于是，我们在删除一个合法区间时，先找到小于这个合法区间的左端点的最大的左端点（即其前一个合法区间的左端点，记为 \(t\)），新的区间的左端点起码需要 \(>t\)；再找到大于这个合法区间的排名的最小排名（即其后一个合法区间的排名，记为 \(q\)），新的区间的排名若 \(\geq q\) 则它的右端点一定 \(\geq q\) 的右端点，也不合法（取等的情况讨论一下发现也对）。有了这两个限制，我们找到的就都是合法区间。

用另一棵线段树将所有非法区间存放在线段树上它们各自排名的位置，每次删除区间时，记删除的区间的排名为 \(x\)，去找排名在 \([x, n]\) 中左端点 \(>t\) 的一个非法区间，若其排名 \(\geq q\) 则结束；否则将其升变为合法区间，并使 \(t\gets\) 其左端点。

至此可以在 \(O(n\log n)\) 的时间复杂度内解决原问题。

code

需要开两棵线段树，支持的线段树二分都有所不同。找 \(t,q\) 可以用一个 std::set，因为合法区间按照排名、或者左端点、或者右端点排序的结果都是一样的，可以随便写。插入新的合法区间时需要知晓其权值，使用另一个树状数组维护。seg1 是合法区间，seg2 是非法区间。

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) ((void)fprintf(stderr, ##__VA_ARGS__))
#else
#define endl "\n"
#define debug(...) ((void)0)
#endif
using LL = long long;
template <int N, class T>
struct fenwick {/*{{{*/
  T c[N + 10];
  fenwick() { memset(c, 0, sizeof c); }
  void add(int p, T k) { for (; p <= N; p += p & -p) c[p] += k; }
  T qry(int p) { T r = 0; for (; p >= 1; p -= p & -p) r += c[p]; return r; }
};/*}}}*/
template <class T>
struct flower {/*{{{*/
  vector<T> vec;
  template <class U> flower& operator<<(U&& x) {
    vec.push_back(forward<U>(x));
    return *this;
  }
  size_t build() {
    auto bg = vec.begin(), ed = vec.end();
    sort(bg, ed);
    vec.erase(unique(bg, ed), ed);
    return vec.size();
  }
  size_t operator()(const T& x) const {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
  }
  T operator[](int i) const { return vec[i]; }
};/*}}}*/
struct range {
  int l, r, id;
} a[250010];
int n, m, nxt[500010], wh[500010];
int findnxt(int x) { return nxt[x] == x ? x : nxt[x] = findnxt(nxt[x]); }
flower<int> hua;
fenwick<500010, int> fen;
set<int> st;
namespace seg2 {
  constexpr int N = 2.5e5;
  int maxl[N << 2];
  void maintain(int p) { maxl[p] = max(maxl[p << 1], maxl[p << 1 | 1]); }
  void build(int p, int l, int r) {/*{{{*/
    if (l == r) {
      maxl[p] = -1e9;
      return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    maintain(p);
  }/*}}}*/
  void setValue(int x, int v, int p, int l, int r) {/*{{{*/
    if (l == r) {
      maxl[p] = v;
      return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) setValue(x, v, p << 1, l, mid);
    else setValue(x, v, p << 1 | 1, mid + 1, r);
    maintain(p);
  }/*}}}*/
  int binary(int L, int R, int v, int p, int l, int r) {
    if (L <= l && r <= R) {
      if (maxl[p] <= v) return n + 1;
      if (l == r) return l;
    }
    int mid = (l + r) >> 1;
    int ret = L <= mid ? binary(L, R, v, p << 1, l, mid) : n + 1;
    if (ret <= n) return ret;
    return mid < R ? binary(L, R, v, p << 1 | 1, mid + 1, r) : n + 1;
  }
  void enable(int id) { debug("seg2::enable(%d)\n", a[id].id); setValue(id, a[id].l, 1, 1, n); }
  void disable(int id) { debug("seg2::disable(%d)\n", a[id].id); setValue(id, -1e9, 1, 1, n); }
};
namespace seg1 {
  constexpr int N = 5e5;
  pair<int, int> ans[N << 2];
  int tag[N << 2], maxr[N << 2];
  void maintain(int p) {
    ans[p] = min(ans[p << 1], ans[p << 1 | 1]);
    maxr[p] = max(maxr[p << 1], maxr[p << 1 | 1]);
  }
  void spread(int p, int k) { ans[p].first -= k, tag[p] += k; }
  void pushdown(int p) { spread(p << 1, tag[p]), spread(p << 1 | 1, tag[p]), tag[p] = 0; }
  void build(int p, int l, int r) {/*{{{*/
    tag[p] = 0;
    if (l == r) {
      ans[p] = make_pair(1e9, -1);
      maxr[p] = -1e9;
      return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    maintain(p);
  }/*}}}*/
  void setValue(int x, int id, int p, int l, int r) {/*{{{*/
    if (l == r) {
      if (id > 0) {
        int len = hua[a[id].r - 1] - hua[a[id].l - 1];
        int lenp = fen.qry(a[id].r - 1) - fen.qry(a[id].l - 1);
        ans[p] = make_pair(len - lenp, a[id].id);
        maxr[p] = a[id].r;
      } else {
        ans[p] = make_pair(1e9, -1);
        maxr[p] = -1e9;
      }
      return ;
    }
    int mid = (l + r) >> 1;
    pushdown(p);
    if (x <= mid) setValue(x, id, p << 1, l, mid);
    else setValue(x, id, p << 1 | 1, mid + 1, r);
    maintain(p);
  }/*}}}*/
  void modify(int L, int R, int k, int p, int l, int r) {/*{{{*/
    if (L <= l && r <= R) return spread(p, k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if (L <= mid) modify(L, R, k, p << 1, l, mid);
    if (mid < R) modify(L, R, k, p << 1 | 1, mid + 1, r);
    maintain(p);
  }/*}}}*/
  void enable(int id) {
    debug("seg1::enable(%d) = [%d, %d]\n", a[id].id, a[id].l, a[id].r);
    st.insert(id);
    setValue(a[id].l, id, 1, 1, m);
  }
  void disable(int id) { 
    debug("seg1::disable(%d) = [%d, %d]\n", a[id].id, a[id].l, a[id].r);
    assert(st.find(id) != st.end());
    auto it = st.erase(st.find(id));
    int t = it == st.begin() ? 0 : a[*prev(it)].l;
    int q = it == st.end() ? n + 1 : *it;
    setValue(a[id].l, -1, 1, 1, m);
    int y = seg2::binary(id, n, t, 1, 1, n);
    while (y < q) {
      enable(y);
      seg2::disable(y);
      t = a[y].l;
      y = seg2::binary(id, n, t, 1, 1, n);
    }
  }
  int binary(int L, int R, int v, int p, int l, int r) {
    if (L <= l && r <= R) {
      if (maxr[p] <= v) return m + 1;
      if (l == r) return l;
    }
    int mid = (l + r) >> 1;
    pushdown(p);
    int ret = L <= mid ? binary(L, R, v, p << 1, l, mid) : m + 1;
    if (ret <= m) return ret;
    return mid < R ? binary(L, R, v, p << 1 | 1, mid + 1, r) : m + 1;
  }
  void plant(int pos) {
    debug("plant(pos = %d)\n", pos);
    // forall range, l <= pos < r
    int len = hua[pos] - hua[pos - 1]; // hua[], 0-indexed
    fen.add(pos, len);
    int res = binary(1, pos, pos, 1, 1, m);
    if (res <= pos) modify(res, pos, len, 1, 1, m);
  }
  int qrymax() { return wh[ans[1].second]; }
};
int main() {
#ifndef LOCAL
#ifndef NF
  freopen("ds.in", "r", stdin);
  freopen("ds.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r, a[i].id = i, hua << a[i].l << a[i].r;
  m = (int)hua.build();
  for (int i = 1; i <= n; i++) a[i].l = (int)hua(a[i].l) + 1;
  for (int i = 1; i <= n; i++) a[i].r = (int)hua(a[i].r) + 1;
  auto key = [](auto&& self) { return make_tuple(self.r, -self.l, self.id); };
  sort(a + 1, a + n + 1, [&](auto&& lhs, auto&& rhs) { return key(lhs) < key(rhs); }); // std::forward /lh
  for (int i = 1; i <= n; i++) wh[a[i].id] = i;
  for (int i = 1; i <= m; i++) nxt[i] = i;
  seg1::build(1, 1, m);
  seg2::build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    if (st.empty() || a[*st.rbegin()].l < a[i].l) seg1::enable(i);
    else seg2::enable(i);
  }
  for (int t = 1; t <= n; t++) {
    int pos = seg1::qrymax();
    cout << a[pos].id << " \n"[t == n];
    int now = findnxt(a[pos].l);
    while (now < a[pos].r) {
      seg1::plant(now);
      nxt[now] = now + 1;
      now = findnxt(now);
    }
    seg1::disable(pos);
#ifdef LOCAL
    for (int x : st) debug("%d ", a[x].id);
    debug("\n");
    for (int x : st) debug("[%d, %d] ", a[x].l, a[x].r);
    debug("\n");
#endif
  }
  return 0;
}

标签：return,QOJ2559,题解,SS241006D,int,vec,端点,区间,id
From： https://www.cnblogs.com/caijianhong/p/18450510/solution-SS241006D

相关文章

  • CF722F Cyclic Cipher 题解
    传送门给定\(n\)个数列，第\(i\)个数列包含\(k_i\)个不超过\(m\)的互不相同的正整数(从\(1\)开始标号)。每一秒将每个数列中的数左移一个位置(即将每个数的下标\(-1\),下标\(1\)的数下标变为\(k_i\)),并记录由每个数列的第一个数组成的序列。\(10^{100}\)秒过......
  • [NOIP2023] 双序列拓展 题解
    qaq首先我们考虑其实这个条件就是要满足\(f\)严格比\(g\)大或\(f\)严格比\(g\)小。在这里只讨论大于。然后考虑到对于一个\(i\)如果不满足，我们可以把对应数组向右移一位看是否满足，如果还是不满足就无解了。考虑对于现在满足的\(i\)，我们可以分别把两个指针向右移一......
  • EGOI2024 简单题解
    Day1T1InfiniteRace由于只有重复超过一个人才肯定是跑过一圈的，所以只用用一个数组做标记就可以了，每超过一次就打上标记，否则去掉标记。T2Bouquet定义\(dp[i]\)为，以第\(i\)种郁金香结尾的选法中最大可选的郁金香数量，易得状态转移方程为：\(dp[i]=max{dep[j]}+1(j<l_i\le......
  • mysql登录遇到ERROR 1045问题解决方法
    遇到MySQL登录时出现 ERROR1045（访问被拒绝，用户名或密码错误），可以通过以下步骤来解决：1.确认用户名和密码检查用户名和密码：确认在连接数据库时输入的用户名和密码是否正确。尝试在命令行中连接数据库，确认是否能成功登录：bash mysql-uyour_username-p2.重......
  • 题解：AT_abc374_c [ABC374C] Separated Lunch
    无耻的广告更好的阅读体验~最近在搞个人博客博客园的差点忘了更了。已经沦落到在写这种水题题解了。题目翻译有\(n\)队人，每个队人数不同，把他们分成2组（同一队的不能拆开），使两组人数差距尽量小。形式化题意：有\(n\)个数，把它们分成两组，使两组和的差尽量小。说句闲话：感觉这......
  • P3527 MET-Meteors 题解
    Solution单次二分：二分时间，做这个时间前的所有操作，然后线性统计。注意到可以整体二分，直接整体二分是\(O(n\log^2n)\)。考虑扫描序列，用线段树维护每个时间段内该位置的增加值，差分一下可以实现。将这棵线段树持久化一下，一个国家所有位置同时二分即可\(O(n\logn)\)，可惜空间太......
  • P3250 网络 题解
    Solution单次二分：问“重要度\(\gex\)的所有操作，且\(t\)时间点还存在的所有操作中，是否有不经过这个点的”整体二分：保持操作、询问按时间有序，即预先按时间排序，下传时保持有序；对于一次Solve，对于所有重要度\(\gemid+1\)的操作（加入、删除），考虑与询问按时间混合排序，然后依次......
  • P3215 括号修复 题解
    Statement维护一个括号序列，有以下操作：区间覆盖区间翻转区间反转（左括号变右括号，右括号变左括号）区间问最少改多少位能使括号序列合法，保证有解Solution单纯没想到答案怎么算。。。首先一段括号序，如果消除中间的所有匹配，最终一定形如))))(((，这个信息是可合并的设这时左括......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树，每个节点上有一个集合，每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问，每次问\(u\)点的集合内，\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • 火星商店问题 题解
    Solution线段树套trie，秒了！\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99