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. void sol() {
  31.     string s; cin >> s;
  32.     int n = s.size(), q; cin >> q;
  33.     vector<ordered_set<int>> val(26);
  34.     for (int i = 0; i < n; ++i) {
  35.         val[s[i] - 'a'].insert(i);
  36.     }
  37.     vector<queries> qt;
  38.     vector<update> upd;
  39.     for (int i = 0; i < q; ++i) {
  40.         int t; cin >> t;
  41.         if(t == 1){
  42.             int j; char k; cin >> j >> k;
  43.             upd.push_back({j - 1, k, i});
  44.         } else{
  45.             int v, l, r, k; cin >> v >> l >> r >> k; --l, --r;
  46.             char c, d; cin >> c >> d;
  47.             qt.push_back({v,l,r, k, c,d, i});
  48.         }
  49.     }
  50.     sort(all(qt));
  51.     vector<int> res(q, -1);
  52.     function<void(update)> go_upd = [&] (update curr){
  53.         val[s[curr.i] - 'a'].erase(curr.i);
  54.         s[curr.i] = curr.x;
  55.         val[s[curr.i] - 'a'].insert(curr.i);
  56.     };
  57.     function<pair<int, int>(int, int, int, char)> go_left = [&] (int l, int r, int k, char c){
  58.         if(val[c - 'a'].size() < k) return make_pair(-1, -1);
  59.         auto left = val[c - 'a'].lower_bound(l);
  60.         if(left == val[c - 'a'].end() || *left > r){
  61.             return make_pair(-1, -1);
  62.         }
  63.         int out_range = val[c - 'a'].order_of_key(*left);
  64.         auto right = val[c - 'a'].upper_bound(r);
  65.         int in_range = val[c - 'a'].order_of_key(*right) - out_range;
  66.         if(in_range < k) return make_pair(-1, -1);
  67.         right = val[c - 'a'].find_by_order(k + out_range - 1);
  68.         pair<int, int> ans;
  69.         ans.first = *right;
  70.         ans.second = *(++right) - 1;
  71.         return ans;
  72.     };
  73.     function<int(int, int, int, char)> go_right = [&] (int l, int r, int k, char c){
  74.         if(val[c - 'a'].size() < k) return -1;
  75.         auto right = val[c - 'a'].upper_bound(r);
  76.         auto left = val[c - 'a'].lower_bound(l);
  77.         if(left == val[c - 'a'].end() || *left > r){
  78.             return -1;
  79.         }
  80.         int w = val[c - 'a'].order_of_key(*right);
  81.         int in_range = w - val[c - 'a'].order_of_key(*left);
  82.         if(in_range < k) return -1;
  83.         --right;
  84.         --w;
  85.         auto right1 = val[c - 'a'].find_by_order(w + 1 - k);
  86.         return *right1;
  87.     };
  88.     for (int i = 0, j = 0; i < qt.size(); ++i) {
  89.         while(j < upd.size() && qt[i].v - 1 >= j){
  90.             go_upd(upd[j]);
  91.             ++j;
  92.         }
  93.         auto [v, l, r, k, c,d, idx] = qt[i];
  94.         pair<int, int> left = go_left(l, r, k, c);
  95.         int right = go_right(l, r, k, d);
  96.         if(left.first == -1 || right == -1 || right <= left.first){
  97.             res[idx] = 0;
  98.         } else{
  99.             res[idx] =  min(left.second - left.first + 1, right - left.first);
  100.         }
  101.     }
  102.  
  103.     for (int i = 0; i < q; ++i) {
  104.         if(res[i] == -1) continue;
  105.         cout << res[i] << '\n';
  106.     }
  107.  
  108. }
  109. signed main() {
  110.  
  111.     ios::sync_with_stdio(0);
  112.     cin.tie(0);
  113.     int t = 1;
  114. //    cin >> t;
  115.     while (t--) {
  116.         sol();
  117.     }
  118.  
  119. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Et7Mi0
language:
C++14 (gcc 8.3)
created:
18 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!