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.         int out_range = val[c - 'a'].order_of_key(*left);
  61.         auto right = val[c - 'a'].upper_bound(r);
  62.         int in_range = val[c - 'a'].order_of_key(*right) - out_range;
  63.         if(in_range < k) return make_pair(-1, -1);
  64.         right = val[c - 'a'].find_by_order(k + out_range - 1);
  65.         pair<int, int> ans;
  66.         ans.first = *right;
  67.         ans.second = *(++right) - 1;
  68.         return ans;
  69.     };
  70.     function<int(int, int, int, char)> go_right = [&] (int l, int r, int k, char c){
  71.         if(val[c - 'a'].size() < k) return -1;
  72.         auto right = val[c - 'a'].upper_bound(r);
  73.         auto left = val[c - 'a'].lower_bound(l);
  74.         int w = val[c - 'a'].order_of_key(*right);
  75.         int in_range = w - val[c - 'a'].order_of_key(*left);
  76.         if(in_range < k) return -1;
  77.         --right;
  78.         --w;
  79.         auto right1 = val[c - 'a'].find_by_order(w + 1 - k);
  80.         return *right;
  81.     };
  82.     for (int i = 0, j = 0; i < qt.size(); ++i) {
  83.         while(j < upd.size() && qt[i].v >= j - 1){
  84.             go_upd(upd[j]);
  85.             ++j;
  86.         }
  87.         auto [v, l, r, k, c,d, idx] = qt[i];
  88.         pair<int, int> left = go_left(l, r, k, c);
  89.         int right = go_right(l, r, k, d);
  90.         if(left.first == -1 || right == -1 || right <= left.first){
  91.             res[idx] = 0;
  92.         } else{
  93.             res[idx] =  max(left.second - left.first + 1, right - left.first);
  94.         }
  95.     } 
  96.     for (int i = 0; i < q; ++i) {
  97.         if(res[i] == -1) continue;
  98.         cout << res[i] << '\n';
  99.     }
  100. }
  101. signed main() {
  102.  
  103.     ios::sync_with_stdio(0);
  104.     cin.tie(0);
  105.     int t = 1;
  106. //    cin >> t;
  107.     while (t--) {
  108.         sol();
  109.     }
  110.  
  111. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wsRzYA
language:
C++14 (gcc 8.3)
created:
7 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!