Test/Algorithms/Mo.test.cpp

• View this file on GitHub
• Last update: 2024-12-27 17:07:26+09:00
• Problem: https://yukicoder.me/problems/no/1471

Depends on

• Library/Algorithms/Mo.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1471"

#include "./../../Library/Algorithms/Mo.hpp"


#include <iostream>

#include <map>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  int n, q;
  cin >> n >> q;
  std::string s;
  cin >> s;

  std::vector<int> lq;
  lq.reserve(q);
  std::vector<int> rq;
  rq.reserve(q);
  std::vector<int> xv;
  xv.reserve(q);
  for (int _ = 0; _ < q; ++_) {
    int l, r, x;
    cin >> l >> r >> x;
    --l;
    --r;
    lq.emplace_back(l);
    rq.emplace_back(r);
    xv.emplace_back(x);
  }

  auto mo = mtd::Mo(q, lq, rq);

  std::map<char, int> mp;
  std::vector<char> ans(q);
  for (int _ = 0; _ < q; ++_) {
    auto i = mo.process([&](int i) { mp[s[i]]++; }, [&](int i) { mp[s[i]]--; });

    int cnt = 0;
    for (const auto& [c, x] : mp) {
      cnt += x;
      if (cnt >= xv[i]) {
        ans[i] = c;
        break;
      }
    }
  }

  for (const auto& c : ans) { cout << c << endl; }
}

#line 1 "Test/Algorithms/Mo.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1471"

#line 2 "Library/Algorithms/Mo.hpp"
#include <algorithm>

#include <cmath>

#include <numeric>

#include <vector>


namespace mtd {

  class Mo {
    const int q;
    const std::vector<int> lq;
    const std::vector<int> rq;
    const std::vector<int> order;
    int ni, nl, nr;

    auto sort_query() const {
      std::vector<int> _order(q);
      std::iota(_order.begin(), _order.end(), 0);
      int w = static_cast<int>(std::sqrt(q));
      std::sort(_order.begin(), _order.end(), [&](int a, int b) {
        if (lq[a] / w != lq[b] / w) return lq[a] < lq[b];
        if (rq[a] == rq[b]) { return false; }
        bool less = (rq[a] < rq[b]);
        bool flg = (lq[a] / w) & 1;
        return static_cast<bool>(less ^ flg);
      });
      return _order;
    }

  public:
    Mo(int _q, const std::vector<int>& _lq, const std::vector<int>& _rq)
        : q(_q), lq(_lq), rq(_rq), order(sort_query()), ni(0), nl(0), nr(-1) {}

    template <class Lambda1, class Lambda2>
    auto process(const Lambda1& add, const Lambda2& del) {
      const auto l = lq[order[ni]];
      const auto r = rq[order[ni]];
      while (nl > l) { add(--nl); }
      while (nr < r) { add(++nr); }
      while (nl < l) { del(nl++); }
      while (nr > r) { del(nr--); }
      return order[ni++];
    }
  };

}  // namespace mtd

#line 4 "Test/Algorithms/Mo.test.cpp"

#include <iostream>

#include <map>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  int n, q;
  cin >> n >> q;
  std::string s;
  cin >> s;

  std::vector<int> lq;
  lq.reserve(q);
  std::vector<int> rq;
  rq.reserve(q);
  std::vector<int> xv;
  xv.reserve(q);
  for (int _ = 0; _ < q; ++_) {
    int l, r, x;
    cin >> l >> r >> x;
    --l;
    --r;
    lq.emplace_back(l);
    rq.emplace_back(r);
    xv.emplace_back(x);
  }

  auto mo = mtd::Mo(q, lq, rq);

  std::map<char, int> mp;
  std::vector<char> ans(q);
  for (int _ = 0; _ < q; ++_) {
    auto i = mo.process([&](int i) { mp[s[i]]++; }, [&](int i) { mp[s[i]]--; });

    int cnt = 0;
    for (const auto& [c, x] : mp) {
      cnt += x;
      if (cnt >= xv[i]) {
        ans[i] = c;
        break;
      }
    }
  }

  for (const auto& c : ans) { cout << c << endl; }
}

Back to top page