Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // jrke's special
- // Codeforces - 2025 ICPC Nanchang Invitational and Jiangxi Provincial Collegiate Programming Contest/E_Gods_String_on_This_Wonderful_World.cpp
- // Codeforces
- #include <bits/stdc++.h>
- using namespace std;
- #define ll int
- //definition
- void solveTest();
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- //judgeio();
- // int t;
- // cin >> t; cin.ignore();
- //
- // for (int i = 0; i < t; i++) solveTest();
- solveTest();
- return 0;
- }
- //solving a test case
- void solveTest() {
- ll n, k, q;
- cin >> n >> k >> q; cin.ignore();
- ll blockSize = sqrt(n);
- string s;
- cin >> s;
- vector<pair<ll, pair<ll, ll>>> v;
- for (ll i = 0; i < q; i++) {
- ll a, b;
- cin >> a >> b;
- a--, b--;
- v.push_back({a, {b, i}});
- }
- sort(v.begin(), v.end());
- vector<ll> state(n + 1);
- map<vector<ll>, ll> tt;
- vector<ll> freq(26);
- ll st = 1;
- for (ll i = 0; i <= n; i++) {
- if (tt[freq] == 0) tt[freq] = st++;
- state[i] = tt[freq];
- if (i == n) break;
- freq[s[i] - 'a']++;
- freq[s[i] - 'a'] %= k;
- }
- vector<ll> ans(q);
- ll idx = 0;
- ll block = 0;
- vector<ll> cnt(st);
- while (idx < v.size()) {
- ll start = block * blockSize;
- vector<pair<ll, pair<ll, ll>>> b;
- for (ll i = start; i < start + blockSize; i++) {
- while (idx < v.size() && v[idx].first == i) {
- b.push_back({v[idx].second.first, {v[idx].first, v[idx].second.second}});
- idx++;
- }
- }
- sort(b.begin(), b.end());
- vector<ll> rem;
- ll currl = start;
- ll currr = start;
- ll currAns = 0;
- for (ll i = 0; i < b.size(); i++) {
- ll l = b[i].second.first;
- ll r = b[i].first;
- while (currr <= r + 1) {
- currAns += cnt[state[currr]];
- rem.push_back(state[currr]);
- cnt[state[currr++]]++;
- }
- if (currl > l) {
- while (currl != l) {
- currl--;
- currAns += cnt[state[currl]];
- cnt[state[currl]]++;
- }
- } else {
- while (currl != l) {
- cnt[state[currl]]--;
- currAns -= cnt[state[currl]];
- currl++;
- }
- }
- ans[b[i].second.second] = currAns;
- }
- block++;
- for (ll x : rem) cnt[x] = 0;
- }
- for (int i = 0; i < q; i++) cout << ans[i] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
