fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define int ll
  5. #define db long double
  6. #define sz(s) (int)s.size()
  7. #define all(v) v.begin(),v.end()
  8. #define rall(v) v.rbegin(),v.rend()
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define vi vector<int>
  13. #define vvi vector<vector<int>>
  14. #define vvd vector<vector<db>>
  15. #define vpi vector<pair<int,int>>
  16. #define ii pair<ll,ll>
  17. #define fix(n, num) fixed<<setprecision(num)<<n
  18. using namespace std;
  19. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  20. const int N = 20 + 5, mod = 1e9 + 7;
  21. const ll inf = 1e18;
  22.  
  23. struct node {
  24.     int val[26] = {};
  25.  
  26.     node(int x = 26) {
  27.         if (x < 26)
  28.             val[x]++;
  29.     }
  30.  
  31.     void change(int x) {
  32.         for (int i = 0; i < 26; ++i) {
  33.             val[i] = 0;
  34.         }
  35.         val[x]++;
  36.     }
  37. };
  38.  
  39. struct segtree {
  40.     int tree_size;
  41.     vector<node> seg_data;
  42.  
  43.     segtree(int n) {
  44.         tree_size = 1;
  45.         while (tree_size < n) tree_size *= 2;
  46.         seg_data.assign(2 * tree_size, node());
  47.     }
  48.  
  49.     void merge(node &ret, const node &lf, const node &ri) {
  50.         for (int i = 0; i < 26; ++i) {
  51.             ret.val[i] = lf.val[i] + ri.val[i];
  52.         }
  53.     }
  54.  
  55.     int sum(int l, int r, int c, int ni, int lx, int rx) {
  56.         if (lx >= r || rx <= l)
  57.             return 0;
  58.         if (lx >= l && rx <= r)
  59.             return seg_data[ni].val[c];
  60.         int mid = (lx + rx) / 2;
  61.         return sum(l, r, c, 2 * ni + 1, lx, mid) + sum(l, r, c, 2 * ni + 2, mid, rx);
  62.     }
  63.  
  64.     int sum(int l, int r, int c) {
  65.         if (r < l) return 0;
  66.         return sum(l, r + 1, c, 0, 0, tree_size);
  67.     }
  68.  
  69.     int pre(int l, int r, int k, int c, int ni, int lx, int rx) {
  70.         if (rx - lx == 1) return lx;
  71.  
  72.         int lf = seg_data[2 * ni + 1].val[c] - sum(lx, l - 1, c);
  73.         int mid = (lx + rx) / 2;
  74.         if (lf >= k)
  75.             return pre(l, r, k, c, 2 * ni + 1, lx, mid);
  76.         return pre(l, r, k - max(lf, 0ll), c, 2 * ni + 2, mid, rx);
  77.     }
  78.  
  79.     int pre(int l, int r, int k, int c) {
  80.         return pre(l, r + 1, k, c, 0, 0, tree_size);
  81.     }
  82.  
  83.     int suf(int l, int r, int k, int c, int ni, int lx, int rx) {
  84.         if (rx - lx == 1) return lx;
  85.  
  86.         int ri = seg_data[2 * ni + 2].val[c] - sum(r + 1, rx - 1, c);
  87.         int mid = (lx + rx) / 2;
  88.         if (ri >= k)
  89.             return suf(l, r, k, c, 2 * ni + 2, mid, rx);
  90.         return suf(l, r, k - max(ri, 0ll), c, 2 * ni + 1, lx, mid);
  91.     }
  92.  
  93.     int suf(int l, int r, int k, int c) {
  94.         return suf(l, r + 1, k, c, 0, 0, tree_size);
  95.     }
  96.  
  97.     void change(int idx, int val, int ni, int lx, int rx) {
  98.         if (rx - lx == 1) {
  99.             seg_data[ni].change(val);
  100.             return;
  101.         }
  102.         ll mid = (lx + rx) / 2;
  103.  
  104.         if (idx < mid)
  105.             change(idx, val, 2 * ni + 1, lx, mid);
  106.         else
  107.             change(idx, val, 2 * ni + 2, mid, rx);
  108.  
  109.         merge(seg_data[ni], seg_data[2 * ni + 1], seg_data[2 * ni + 2]);
  110.     }
  111.  
  112.     void change(int idx, int val) {
  113.         change(idx, val, 0, 0, tree_size);
  114.     }
  115.  
  116. };
  117.  
  118. struct query {
  119.     int l, r, k, c, d, idx;
  120. };
  121.  
  122. void here_we_go_again() {
  123.     string s;
  124.     cin >> s;
  125.  
  126.     int n = sz(s);
  127.     s = ' ' + s;
  128.     segtree t(n + 1);
  129.     for (int i = 1; i <= n; ++i) {
  130.         t.change(i, s[i] - 'a');
  131.     }
  132.  
  133.     int id = 0, up = 0, num;
  134.     cin >> num;
  135.     vector<query> q[num];
  136.     ii ver[num];
  137.     while (num--) {
  138.         int t;
  139.         cin >> t;
  140.         if (t == 1) {
  141.             int i;
  142.             char x;
  143.             cin >> i >> x;
  144.             ver[++up] = {i, x - 'a'};
  145.         } else {
  146.             int v, l, r, k;
  147.             char c, d;
  148.             cin >> v >> l >> r >> k >> c >> d;
  149.             q[v].pb({l, r, k, c - 'a', d - 'a', id++});
  150.         }
  151.     }
  152.  
  153.     vi ans(id);
  154.  
  155.     for (int v = 0; v <= up; ++v) {
  156.         if (v)
  157.             t.change(ver[v].fi, ver[v].se);
  158.  
  159.         // l1 -> pre Kth c   r1 -> pre (k+1)th c
  160.         // l2 -> start       r2 -> suf kth d
  161.  
  162.         for (auto &[l, r, k, c, d, idx]: q[v]) {
  163.             int pre = t.sum(l, r, c);
  164.             if (pre < k || t.sum(l, r, d) < k)
  165.                 continue;
  166.             int l1 = t.pre(l, r, k, c);
  167.             int r1 = (pre > k ? t.pre(l, r, k + 1, c) : r);
  168.             int l2 = l, r2 = t.suf(l, r, k, d);
  169.             ans[idx] = max(0ll, min(r1, r2) - max(l1, l2));
  170.         }
  171.  
  172.     }
  173.  
  174.     for (auto &i: ans)
  175.         cout << i << '\n';
  176.  
  177.  
  178. }
  179.  
  180. int32_t main() {
  181. //    freopen("points.in", "r", stdin);
  182. //    freopen("output.txt", "w", stdout);
  183.     ios_base::sync_with_stdio(false);
  184.     cin.tie(0), cout.tie(0);
  185.  
  186.     int t = 1;
  187. //    cin >> t;
  188.     for (int i = 1; i <= t; ++i) {
  189.         //  cout<<"Case #"<<i<<": ";
  190.         here_we_go_again();
  191.     }
  192.  
  193.     return 0;
  194. }
  195.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iYE28z
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!