/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 532.0 KiB
#2 Accepted 75ms 2.266 MiB
#3 Accepted 38ms 636.0 KiB
#4 Accepted 61ms 984.0 KiB
#5 Accepted 75ms 2.391 MiB
#6 Accepted 108ms 7.102 MiB
#7 Accepted 263ms 47.461 MiB
#8 Accepted 276ms 47.445 MiB
#9 Accepted 278ms 47.352 MiB
#10 Accepted 284ms 47.5 MiB
#11 Accepted 295ms 47.48 MiB
#12 Accepted 290ms 47.496 MiB
#13 Accepted 86ms 51.738 MiB
#14 Accepted 123ms 51.797 MiB
#15 Accepted 125ms 51.812 MiB
#16 Accepted 119ms 51.805 MiB

Code

#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using ll = long long;

template<typename T, typename U = T>
struct SegmentTree {
  int n;
  vector<T> tree;

  // ----------

  template<typename VAL_T>
  T get_tree_val(VAL_T& val) {
    return val;
  }

  T data_pull(T val_curr, U val_new) {
    return (val_curr + val_new);
  }

  T merge(T a, T b) {
    return (a + b);
  }

  // ----------

  SegmentTree(int n = 0) : n(n) {
    tree.resize(n<<2);
  }

  template<typename VAL_T>
  SegmentTree(vector<VAL_T>& data) : SegmentTree((int)data.size()) {
    __build(0, 0, n-1, data);
  }

  template<typename VAL_T>
  void __build(int ti, int left, int right, vector<VAL_T>& data) {
    if (left == right) {
      tree[ti] = get_tree_val(data[left]);
      return;
    }

    int tl, tr, tm;
    tl = (ti<<1)+1;
    tr = (ti<<1)+2;
    tm = (left+right)>>1;

    __build(tl, left, tm, data);
    __build(tr, tm+1, right, data);
    tree[ti] = merge(tree[tl], tree[tr]);
  }

  void __update(int ti, int left, int right, int ind, U val) {
    if (left == right) {
      tree[ti] = data_pull(tree[ti], val);
      return;
    }

    int tl, tr, tm;
    tl = (ti<<1)+1;
    tr = (ti<<1)+2;
    tm = (left+right)>>1;

    if (ind <= tm) __update(tl, left, tm, ind, val);
      else __update(tr, tm+1, right, ind, val);
    tree[ti] = merge(tree[tl], tree[tr]);
  }

  T __query(int ti, int left, int right, int l, int r) {
    if ((l <= left) && (right <= r)) return tree[ti];

    int tl, tr, tm;
    tl = (ti<<1)+1;
    tr = (ti<<1)+2;
    tm = (left+right)>>1;

    if (l > tm) return __query(tr, tm+1, right, l, r);
    if (r <= tm) return __query(tl, left, tm, l, r);
    return merge(
      __query(tl, left, tm, l, r),
      __query(tr, tm+1, right, l, r)
    );
  }

  void update(int i, U val) { __update(0, 0, n-1, i, val); }
  T query(int l, int r) { return __query(0, 0, n-1, l, r); }
};

const int MX = 100005;
vector<int> g[MX];
int in[MX], out[MX], Timer;
SegmentTree<int> seg[26];

void fdfs(int u, int p = -1) {
  in[u] = Timer++;
  for (int v : g[u]) {
    if (v == p) continue;
    fdfs(v, u);
  }
  out[u] = Timer-1;
}

void init(int n) {
  for (int i = 0; i <= n; ++i) {
    g[i].clear();
  }
  Timer = 0;
}

int main() {
  FAST;

  int n, q, i, j, u, v, t, x, mx;
  char c;
  cin >> n;
  init(n);

  vector<int> a(n);
  for (i = 0; i < n; ++i) {
    cin >> c;
    x = c - 'a';
    a[i] = x;
  }

  for (i = 1; i < n; ++i) {
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  fdfs(0);

  for (j = 0; j < 26; ++j) {
    vector<int> b(n);
    for (i = 0; i < n; ++i) {
      if (a[i] == j) b[in[i]] = 1;
    }
    seg[j] = SegmentTree<int>(b);
  }

  cin >> q; while (q--) {
    cin >> t;

    if (t == 1) {
      cin >> u >> c; --u;
      x = c - 'a';

      seg[a[u]].update(in[u], -1);
      a[u] = x;
      seg[a[u]].update(in[u], 1);
    } else {
      cin >> u; --u;

      mx = 0;
      c = 'a';
      for (j = 0; j < 26; ++j) {
        x = seg[j].query(in[u], out[u]);
        if (x > mx) {
          mx = x;
          c = (char)j + 'a';
        }
      }

      cout << c << "\n";
    }
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1091 Alphabetical Kingdom
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:03:00
Judged At
2024-10-03 13:09:23
Judged By
Score
100
Total Time
295ms
Peak Memory
51.812 MiB