test/ds/pssgt1.test.cpp

View this file on GitHub
Last update: 2025-10-04 16:08:12+08:00
Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_queue
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using ll = long long;

#include "../../src/ds/pssgt.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read();
  vector<int> head(n + 1), tail(n + 1);
  SegTree<Info> sgt(n);
  for (int i = 1; i <= n; i++) {
    int op = read(), t = read();
    t++;
    if (op == 0) {
      int x = read();
      sgt.set(sgt.root[t], tail[t], Info{x});
      head[i] = head[t], tail[i] = tail[t] + 1;
    } else {
      auto qry = sgt.sum(sgt.root[0], sgt.root[t], head[t], head[t] + 1);
      cout << qry.data << "\n";
      sgt.set(sgt.root[t], head[t], Info{});
      head[i] = head[t] + 1, tail[i] = tail[t];
    }
  }
  return 0;
}

#line 1 "test/ds/pssgt1.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_queue
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using ll = long long;

#line 1 "src/ds/pssgt.hpp"
template <typename Info>
struct SegTree {
  struct Node {
    Info info = {};
    int ls = -1, rs = -1;
  };
  int n, _pos, _l, _r;
  Info _v, _acc;
  vector<int> root;
  vector<Node> tree;
  SegTree(int n) : SegTree(vector<Info>(n)) {}
  SegTree(const vector<Info>& a) : n(a.size()) { root.PUSHB(build(0, n, a)); }
  void set(int p, int pos, Info f) {
    _pos = pos, _v = f, root.PUSHB(set_(p, 0, n));
  }
  Info sum(int p1, int p2, int l, int r) {
    return _l = l, _r = r, sum_(p1, p2, 0, n);
  }
  template <typename P>
  int bsearch(int p1, int p2, P pred) {
    return _acc = {}, bsearch_(p1, p2, 0, n, pred);
  }

 private:
#define MID (pl + (pr - pl) / 2)
  int new_(Node node) { return tree.PUSHB(move(node)), tree.size() - 1; }
  int pushup(int ls, int rs) {
    return new_(Node{tree[ls].info + tree[rs].info, ls, rs});
  }
  int build(int pl, int pr, const vector<Info>& a) {
    if (pr - pl == 1) return new_({a[pl], -1, -1});
    return pushup(build(pl, MID, a), build(MID, pr, a));
  }
  int set_(int p, int pl, int pr) {
    if (_pos < pl || pr <= _pos) return p;
    if (pr - pl == 1) return new_(Node{_v, -1, -1});
    return pushup(set_(tree[p].ls, pl, MID), set_(tree[p].rs, MID, pr));
  }
  Info sum_(int p1, int p2, int pl, int pr) {
    if (_r <= pl || pr <= _l) return {};
    if (_l <= pl && pr <= _r) return tree[p2].info - tree[p1].info;
    return sum_(tree[p1].ls, tree[p2].ls, pl, MID) +
           sum_(tree[p1].rs, tree[p2].rs, MID, pr);
  }
  template <typename P>
  int bsearch_(int p1, int p2, int pl, int pr, P pred) {
    if (pr - pl == 1)
      return pred(_acc + (tree[p2].info - tree[p1].info)) ? pr : pl;
    Info diff = tree[tree[p2].ls].info - tree[tree[p1].ls].info;
    if (pred(_acc + diff)) {
      _acc = _acc + diff;
      return bsearch_(tree[p1].rs, tree[p2].rs, MID, pr, pred);
    } else {
      return bsearch_(tree[p1].ls, tree[p2].ls, pl, MID, pred);
    }
  }
#undef MID
};
struct Info {
  int data = 0;
  friend Info operator+(const Info& lhs, const Info& rhs) {
    return {lhs.data + rhs.data};
  }
  friend Info operator-(const Info& lhs, const Info& rhs) {
    return {lhs.data - rhs.data};
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 9 "test/ds/pssgt1.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read();
  vector<int> head(n + 1), tail(n + 1);
  SegTree<Info> sgt(n);
  for (int i = 1; i <= n; i++) {
    int op = read(), t = read();
    t++;
    if (op == 0) {
      int x = read();
      sgt.set(sgt.root[t], tail[t], Info{x});
      head[i] = head[t], tail[i] = tail[t] + 1;
    } else {
      auto qry = sgt.sum(sgt.root[0], sgt.root[t], head[t], head[t] + 1);
      cout << qry.data << "\n";
      sgt.set(sgt.root[t], head[t], Info{});
      head[i] = head[t] + 1, tail[i] = tail[t];
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	ephemeral_00	AC	172 ms	108 MB
g++	example_00	AC	5 ms	4 MB
g++	half_rot_killer2_00	AC	114 ms	108 MB
g++	half_rot_killer_00	AC	217 ms	209 MB
g++	random_00	AC	224 ms	208 MB
g++	random_01	AC	274 ms	208 MB
g++	random_02	AC	28 ms	18 MB
g++	random_2_00	AC	219 ms	208 MB
g++	random_2_01	AC	265 ms	208 MB
g++	random_2_02	AC	27 ms	18 MB
g++	random_3_00	AC	169 ms	208 MB
g++	random_3_01	AC	194 ms	208 MB
g++	random_3_02	AC	26 ms	18 MB
g++	two_stacks_killer_00	AC	204 ms	208 MB