QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226560#7439. 铃原露露nhuang6850 1ms3464kbC++209.6kb2023-10-26 06:58:352023-10-26 06:58:36

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 06:58:36]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3464kb
  • [2023-10-26 06:58:35]
  • 提交

answer

/**
 * @file
 * @author n685
 * @brief
 * @date 2023-10-24
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
  if (false) \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class Node>
struct LSeg
{
  using T = typename Node::ValueType;
  using RT = typename Node::RT;
  int h, sz;
  std::vector<Node> val;

  void push(int l, int r)
  {
    l += sz, r += sz;
    for (int s = h - 1, k = (1 << (h - 1)); s >= 1; --s, k /= 2)
      for (int i = (l >> s); i <= (r >> s); ++i)
        val[i].push(val[2 * i], val[2 * i + 1], k);
  }
  void build(int l, int r)
  {
    l += sz, r += sz;
    l /= 2, r /= 2;
    for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2)
      for (int i = l; i <= r; ++i)
        val[i].pull(val[2 * i], val[2 * i + 1]);
  }

  LSeg() {}
  LSeg(int _sz)
  {
    if (_sz == 1)
    {
      h = 1;
      sz = 1;
    }
    else
    {
      h = std::__lg(_sz - 1) + 2;
      sz = (1 << (h - 1));
    }
    val.resize(2 * sz);
  }
  LSeg(const std::vector<T> &v) : LSeg(static_cast<int>(v.size()))
  {
    for (int i = 0; i < static_cast<int>(v.size()); ++i)
      val[i + sz] = v[i];
    build(0, sz - 1);
  }

  void upd(int l, int r, const std::function<void(Node &, int)> &f)
  {
    if (l > r)
    {
      return;
    }
    push(l, l), push(r, r);

    bool cl = false, cr = false;
    int k = 1;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2, k *= 2)
    {
      if (cl)
        val[l - 1].pull(val[2 * l - 2], val[2 * l - 1]);
      if (cr)
        val[r + 1].pull(val[2 * r + 2], val[2 * r + 3]);
      if (l % 2 == 1)
        f(val[l++], k), cl = true;
      if (r % 2 == 0)
        f(val[r--], k), cr = true;
    }
    for (--l, ++r; r >= 1; l /= 2, r /= 2)
    {
      if (cl)
        val[l].pull(val[2 * l], val[2 * l + 1]);
      if (cr && (!cl || l != r))
        val[r].pull(val[2 * r], val[2 * r + 1]);
    }
  }
  void set(int l, int r, T v)
  {
    upd(l, r, [&v](Node &n, int k)
        { n.set(v, k); });
  }
  void upd(int l, int r)
  {
    upd(l, r, [](Node &n, int k)
        { n.upd(k); });
  }
  RT query(int l, int r)
  {
    if (l > r)
      return Node::ID;
    push(l, l), push(r, r);

    RT ll = Node::ID, rr = Node::ID;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2)
    {
      if (l % 2 == 1)
        ll = Node::comb(val[l++], ll);
      if (r % 2 == 0)
        rr = Node::comb(rr, val[r--]);
    }
    return Node::comb(ll, rr);
  }

  int walkL(int l, int r, const std::function<bool(int64_t)> &c)
  {
    if (l > r)
      return -1;
    push(l, l);
    l += sz;
    if (c(val[l]))
      return l - sz;

    int ind = -1;
    int s = 1;
    for (; l > 1; l /= 2, s *= 2)
    {
      if (l % 2 == 0 && c(val[l + 1]))
      {
        ind = l + 1;
        break;
      }
    }
    if (ind == -1)
      return -1;

    while (ind < sz)
    {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind]))
        ind = 2 * ind;
      else if (c(val[2 * ind + 1]))
        ind = 2 * ind + 1;
      else
        return -1;
      s /= 2;
    }
    if (c(val[ind]) && ind - sz <= r)
    {
      return ind - sz;
    }
    else
    {
      return -1;
    }
  }
  int walkR(int l, int r, const std::function<bool(int64_t)> &c)
  {
    if (l > r)
      return -1;
    push(r, r);
    r += sz;
    if (c(val[r]))
      return r - sz;

    int ind = -1;
    int s = 1;
    for (; r > 1; r /= 2, s *= 2)
    {
      if (r % 2 == 1 && c(val[r - 1]))
      {
        ind = r - 1;
        break;
      }
    }
    if (ind == -1)
      return -1;

    while (ind < sz)
    {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind + 1]))
        ind = 2 * ind + 1;
      else if (c(val[2 * ind]))
        ind = 2 * ind;
      else
        return -1;
      s /= 2;
    }
    if (c(val[ind]) && ind - sz >= l)
      return ind - sz;
    else
      return -1;
  }
};
template <class T>
struct NodeMax
{
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = (RT)-1e9;
  static constexpr T ID2 = (T)-1e9;
  T val = 0;
  T ls = ID2;
  NodeMax() {}
  NodeMax(T v) : val(v) {}
  operator RT() { return val; }
  static RT comb(RT a, RT b) { return std::max(a, b); }
  void set(T v, [[maybe_unused]] int k)
  {
    val = std::max(val, v);
    ls = std::max(ls, v);
  }
  void pull(NodeMax &ll, NodeMax &rr)
  {
    if (ls != ID2)
      return;
    val = std::max(ll.val, rr.val);
  }
  void push(NodeMax &ll, NodeMax &rr, int k)
  {
    if (ls == ID2)
      return;
    else
    {
      ll.set(ls, k / 2);
      rr.set(ls, k / 2);
    }
    ls = ID2;
  }
};
template <class T>
struct NodeMin
{
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = (RT)1e9;
  static constexpr T ID2 = (T)1e9;
  T val = 0;
  T ls = ID2;
  NodeMin() {}
  NodeMin(T v) : val(v) {}
  operator RT() { return val; }
  static RT comb(RT a, RT b) { return std::min(a, b); }
  void set(T v, [[maybe_unused]] int k)
  {
    val = std::min(val, v);
    ls = std::min(ls, v);
  }
  void pull(NodeMin &ll, NodeMin &rr)
  {
    if (ls != ID2)
      return;
    val = std::min(ll.val, rr.val);
  }
  void push(NodeMin &ll, NodeMin &rr, int k)
  {
    if (ls == ID2)
      return;
    else
    {
      ll.set(ls, k / 2);
      rr.set(ls, k / 2);
    }
    ls = ID2;
  }
};
using Vec = std::array<int64_t, 2>;
using Mat = std::array<Vec, 2>;
const Mat I = {Vec{1, 0}, {0, 1}};
Vec operator+(Vec a, Vec b)
{
  return Vec{a[0] + b[0], a[1] + b[1]};
}
Mat operator*(Mat a, Mat b)
{
  Mat ans{};
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        ans[i][j] += a[i][k] * b[k][j];
  return ans;
}
Vec operator*(Mat a, Vec b)
{
  Vec ans{};
  for (int i = 0; i < 2; ++i)
    for (int k = 0; k < 2; ++k)
      ans[i] += a[i][k] * b[k];
  return ans;
}
template <class T>
struct Node2
{
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = 0;
  // T val = 0;
  Vec val{};
  Mat l = I;
  Node2() {}
  Node2(T v) : val{v, 0} {}
  operator RT() { return val[1]; }
  static RT comb(RT a, RT b) { return a + b; }
  void updM(Mat m, int k)
  {
    val = m * val;
    l = m * l;
  }
  void upd(int k)
  {
    updM(Mat{Vec{1, 0}, {1, 1}}, k);
  }
  void set(T v, int k)
  {
    // k is here for debugging purposes
    assert(k == 1);
    val[0] = v;
  }
  void pull(Node2 &ll, Node2 &rr)
  {
    if (l != I)
      return;
    val = ll.val + rr.val;
  }
  void push(Node2 &ll, Node2 &rr, int k)
  {
    if (l == I)
      return;
    else
    {
      ll.updM(l, k / 2);
      rr.updM(l, k / 2);
    }
    l = I;
  }
};

int main()
{
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int n, m;
  cin >> n >> m;

  std::vector<int> a(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> a[i];
    a[i]--;
  }
  int rt = a[0];
  std::vector<std::vector<int>> adj(n);
  for (int i = 1; i < n; ++i)
  {
    int f;
    cin >> f;
    --f;
    adj[a[f]].push_back(a[i]);
  }

  LSeg<NodeMax<int>> ll(n);
  LSeg<NodeMin<int>> rr(n);
  for (int i = 0; i < n; ++i)
  {
    ll.val[i + ll.sz] = NodeMax<int>(i);
    rr.val[i + rr.sz] = NodeMin<int>(n - 1);
  }
  ll.build(0, n - 1);
  rr.build(0, n - 1);

  auto dfs = [&](auto &self, int node) -> std::set<int> *
  {
    if ((int)adj[node].size() == 0)
      return new std::set<int>{node};
    std::set<int> *mx = nullptr;
    std::vector<std::set<int> *> rest;
    for (int i : adj[node])
    {
      std::set<int> *p = self(self, i);
      if (!mx || (int)p->size() > (int)mx->size())
      {
        if (mx)
          rest.push_back(mx);
        mx = p;
      }
      else
        rest.push_back(p);
    }

    for (auto &s : rest)
      for (int u : *s)
      {
        auto it = s->upper_bound(u);
        if (it != s->end())
        {
          int v = *std::next(it);
          if (node < u)
          {
            // rectangle: (node, u], [v, n]
            rr.set(node + 1, u, v - 1);
          }
          else if (v < node)
          {
            // rectangle: [1, u], [v, node)
            ll.set(v, node - 1, u + 1);
          }
        }
      }

    return mx;
  };
  dfs(dfs, rt);
  ll.push(0, n - 1);
  rr.push(0, n - 1);
  std::vector<std::vector<int>> mx(n + 1), mi(n);
  for (int i = 0; i < n; ++i)
  {
    // ans += std::max(0, (int)rr.val[i + rr.sz] - (int)ll.val[i + ll.sz] + 1);
    if ((int)rr.val[i + rr.sz] < (int)ll.val[i + ll.sz])
      continue;
    mx[(int)rr.val[i + rr.sz] + 1].push_back(i);
    mi[(int)ll.val[i + ll.sz]].push_back(i);
  }
  std::vector<int64_t> ans(m);
  std::vector<std::vector<std::pair<int, int>>> q(n);
  for (int i = 0; i < n; ++i)
  {
    int l, r;
    cin >> l >> r;
    l--, r--;
    q[r].emplace_back(l, i);
  }

  LSeg<Node2<int64_t>> seg(n);
  for (int i = 0; i < n; ++i)
  {
    for (int j : mx[i])
    {
      seg.set(j, j, 0);
    }
    for (int j : mi[i])
    {
      seg.set(j, j, 1);
    }
    seg.upd(0, n - 1);
    for (auto [l, ind] : q[i])
    {
      ans[ind] = seg.query(l, i);
    }
  }
  for (auto &v : ans)
    cout << v << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3464kb

input:

100 100
5 29 12 16 25 36 18 37 27 47 34 40 20 3 1 42 26 19 33 41 6 22 8 58 32 62 24 15 35 17 59 30 50 61 43 49 39 67 44 21 13 31 68 69 65 64 10 28 38 54 70 63 9 46 66 52 23 7 48 60 55 56 51 2 57 11 53 14 45 4 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

45
2701
561
10
91
78
946
120
2080
300
861
351
1540
666
210
210
595
2278
465
435
496
496
2556
210
28
1326
496
1596
1
741
3828
10
595
630
10
861
15
105
2556
120
1275
528
2080
21
861
1830
2485
136
10
861
1770
4186
2211
171
21
946
351
6
2415
28
190
435
36
4560
2080
1596
1953
1540
820
105
3
91
15
741
241...

result:

wrong answer 1st numbers differ - expected: '9', found: '45'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

200000 1
73119 155820 110077 139724 136809 18709 57745 43535 89117 43647 20295 60551 108184 188031 180437 52363 72969 130559 179796 75852 53879 96998 63387 76458 193661 142318 28260 40465 80050 188507 143795 141018 94880 71333 7644 109237 105208 109509 9779 159914 135096 47638 175577 182927 173100 1...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%