Advertisement
esraa_syam

Untitled

Jul 4th, 2024
982
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.79 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define nl "\n"
  5. #define ll long long
  6. #define mod  1'000'000'007
  7. #define all(v) v.begin(), v.end()
  8. #define rall(v) v.rbegin(), v.rend()
  9. #define sz(v) (int) v.size()
  10.  
  11. template<typename T = int>
  12. istream &operator>>(istream &in, vector<T> &v) {
  13.     for (auto &x: v) in >> x;
  14.     return in;
  15. }
  16.  
  17. template<typename T = int>
  18. ostream &operator<<(ostream &out, const vector<T> &v) {
  19.     for (const T &x: v) out << x << " ";
  20.     return out;
  21. }
  22.  
  23. void Sira() {
  24.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  25. #ifndef ONLINE_JUDGE
  26.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  27. #endif
  28. }
  29. struct node {
  30.     pair < ll , char > maxi;
  31.     vector < int > freq;
  32.  
  33.     node(){
  34.         maxi = {0 , 'a'};
  35.         freq.assign(26 , 0);
  36.     }
  37. };
  38.  
  39. struct SegTree{
  40.     int tree_size;
  41.     vector < node > tree;
  42.  
  43.     SegTree(int n){
  44.         tree_size = 1;
  45.         while (tree_size < n) tree_size *= 2;
  46.         tree.assign(2 * tree_size, node());
  47.     }
  48.  
  49.     void build(string & s , int ni , int lx , int rx){
  50.         if(rx - lx == 1){
  51.             if(lx < sz(s)){
  52.                 tree[ni].freq[s[lx] - 'a']++;
  53.             }
  54.             return;
  55.         }
  56.  
  57.         int mid = (lx + rx) / 2;
  58.         build(s , 2 * ni + 1 , lx , mid);
  59.         build(s , 2 * ni + 2 , mid , rx);
  60.  
  61.         tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
  62.     }
  63.  
  64.     void build(string & s){
  65.         build(s , 0 , 0 , tree_size);
  66.     }
  67.  
  68.     node merge(node & l , node & r){
  69.         node res;
  70.         res.maxi = max(l.maxi , r.maxi);
  71.         for(int i = 0; i < 26; i++){
  72.             res.freq[i] = l.freq[i] + r.freq[i];
  73.             res.maxi = max(res.maxi , {res.freq[i] , (char)(i + 'a')});
  74.         }
  75.         return res;
  76.     }
  77.  
  78.     void update(int idx , int val , int ni , int lx , int rx){
  79.         if(rx - lx == 1){
  80.             tree[ni].freq[val]++;
  81.             return;
  82.         }
  83.  
  84.         int mid = (lx + rx) / 2;
  85.         if(idx < mid){
  86.             update(idx , val , 2 * ni + 1 , lx , mid);
  87.         }else{
  88.             update(idx , val , 2 * ni + 2 , mid , rx);
  89.         }
  90.  
  91.         tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
  92.     }
  93.  
  94.     void update(int idx , int val){
  95.         update(idx , val , 0 , 0 , tree_size);
  96.     }
  97.  
  98.     node calc(int l , int r , int ni , int lx , int rx){
  99.         if(lx >= r || l >= rx) return node();
  100.         if(lx >= l && rx <= r) return tree[ni];
  101.  
  102.         int mid = (lx + rx) / 2;
  103.         node left = calc(l , r , 2 * ni + 1 , lx , mid);
  104.         node right = calc(l , r , 2 * ni + 2 , mid , rx);
  105.  
  106.         return merge(left , right);
  107.     }
  108.  
  109.     pair < ll  , char > calc(int l , int r){
  110.         return calc(l , r , 0 , 0 , tree_size).maxi;
  111.     }
  112. };
  113.  
  114. void solve(){
  115.     int n;
  116.     cin >> n;
  117.  
  118.     string s;
  119.     cin >> s;
  120.  
  121.     SegTree st(n);
  122.     st.build(s);
  123.  
  124.     map < char , vector < int > > mp;
  125.  
  126.     for(int i = 0; i < n; i++){
  127.         mp[s[i]].push_back(i);
  128.     }
  129.  
  130.  
  131.     int q;
  132.     cin >> q;
  133.  
  134.     while(q--){
  135.         int l , r;
  136.         cin >> l >> r;
  137.         l--;
  138.         auto up = upper_bound(all(mp[st.calc(l , r).second]) , r - 1);
  139.         auto low = lower_bound(all(mp[st.calc(l , r).second]) , l);
  140. //        cout << up - low << nl;
  141.         if(abs(low - up) == abs(r - l) or st.calc(l , r).first == 1){
  142.             cout << "NO" << nl;
  143.         }else{
  144.             int up2 = *up;
  145.             int low2 = *low;
  146.  
  147.             if(up2 < n - 1 and (up2 - low2 + 1) != (low - up)) cout << "NO" << nl;
  148.             else cout << "YES" << nl;
  149.         }
  150.  
  151.         cout << st.calc(l , r).first << " " << st.calc(l , r).second << nl;
  152.     }
  153.  
  154. }
  155.  
  156. int main() {
  157.     Sira();
  158.     int t = 1;
  159. //    cin >> t;
  160.     while(t--){
  161.         solve();
  162.     }
  163.     return 0;
  164. }
  165.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement