fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. //#define  int long long
  4. #define  all(v) v.begin(),v.end()
  5. using namespace std;
  6. #define ll long long
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. using namespace __gnu_pbds;
  11. template<class T>
  12. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  13.  
  14. const int N = 1e6 + 10;
  15. const long long md = 1e9 + 7;
  16.  
  17. const int Inf = 1e9;
  18. struct queries{
  19.     int v, l, r, k;
  20.     char c, d;
  21.     int idx;
  22.     bool operator <(const queries& other){
  23.         return this->v < other.v;
  24.     }
  25. };
  26. struct update{
  27.     int i;
  28.     char x; int idx;
  29. };
  30. vector<ordered_set<int>> val(26);
  31. pair<int, int> go_left (int l, int r, int k, char c){
  32.     if(val[c - 'a'].size() < k) return make_pair(-1, -1);
  33.     //cout << val[c - 'a'].size() << ' ' << k << endl;
  34.     auto left = val[c - 'a'].lower_bound(l);
  35.     if(left == val[c - 'a'].end() || *left > r){
  36.  
  37.         return make_pair(-1, -1);
  38.     }
  39.  
  40.     int out_range = val[c - 'a'].order_of_key(*left);
  41.     auto right = val[c - 'a'].upper_bound(r);
  42.     right--;
  43.     int in_range = val[c - 'a'].order_of_key(*right) + 1 - out_range;
  44.     // cout << *left << ' ' << *right << " " << r<< endl;
  45.     if(in_range < k) return make_pair(-1, -1);
  46.  
  47.     right = val[c - 'a'].find_by_order(k + out_range - 1);
  48.     pair<int, int> ans;
  49.     ans.first = *right;
  50.     ans.second = *(++right) - 1;
  51.     return ans;
  52. };
  53. int go_right(int l, int r, int k, char c){
  54.     if(val[c - 'a'].size() < k) return -1;
  55.     auto right = val[c - 'a'].upper_bound(r);
  56.     auto left = val[c - 'a'].lower_bound(l);
  57.     if(left == val[c - 'a'].end() || *left > r){
  58.         return -1;
  59.     }
  60.     --right;
  61.     int w = val[c - 'a'].order_of_key(*right) + 1;
  62.     int in_range = w - val[c - 'a'].order_of_key(*left);
  63.     if(in_range < k) return -1;
  64.     --w;
  65.     auto right1 = val[c - 'a'].find_by_order(w + 1 - k);
  66.     return *right1;
  67. };
  68. void sol() {
  69.     string s; cin >> s;
  70.     int n = s.size(), q; cin >> q;
  71.  
  72.     for (int i = 0; i < n; ++i) {
  73.         val[s[i] - 'a'].insert(i);
  74.     }
  75.     vector<queries> qt;
  76.     vector<update> upd;
  77.     for (int i = 0; i < q; ++i) {
  78.         int t; cin >> t;
  79.         if(t == 1){
  80.             int j; char k; cin >> j >> k;
  81.             upd.push_back({j - 1, k, i});
  82.         } else{
  83.             int v, l, r, k; cin >> v >> l >> r >> k; --l, --r;
  84.             char c, d; cin >> c >> d;
  85.             qt.push_back({v,l,r, k, c,d, i});
  86.         }
  87.     }
  88.     sort(all(qt));
  89.     vector<int> res(q, -1);
  90.     function<void(update)> go_upd = [&] (update curr){
  91.         val[s[curr.i] - 'a'].erase(curr.i);
  92.         s[curr.i] = curr.x;
  93.         val[s[curr.i] - 'a'].insert(curr.i);
  94.     };
  95.  
  96.  
  97.     for (int i = 0, j = 0; i < qt.size(); ++i) {
  98.         while(j < upd.size() && qt[i].v - 1 >= j){
  99.             go_upd(upd[j]);
  100.             ++j;
  101.         }
  102.         auto [v, l, r, k, c,d, idx] = qt[i];
  103.         pair<int, int> left = go_left(l, r, k, c);
  104.         int right = go_right(l, r, k, d);
  105.         if(left.first == -1 || right == -1 || right <= left.first){
  106.             res[idx] = 0;
  107.         } else{
  108.             res[idx] =  min(left.second - left.first + 1, right - left.first);
  109.         }
  110.     }
  111.  
  112.     for (int i = 0; i < q; ++i) {
  113.         if(res[i] == -1) continue;
  114.         cout << res[i] << '\n';
  115.     }
  116.  
  117. }
  118. signed main() {
  119.  
  120.     ios::sync_with_stdio(0);
  121.     cin.tie(0);
  122.     int t = 1;
  123. //    cin >> t;
  124.     while (t--) {
  125.         sol();
  126.     }
  127.  
  128. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dMfgPK
language:
C++14 (gcc 8.3)
created:
2 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!