Advertisement
Zeinab_Hamdy

Untitled

Jul 4th, 2024
903
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.86 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 > max_freq;
  32.     vector < int > freq;
  33.     vector < pair < int , int >  > idx;
  34.  
  35.     node(){
  36.         maxi = {0 , 'a'};
  37.         freq.assign(26 , 0);
  38.         max_freq.assign(26 , 0);
  39.         idx.assign(26 , { 1e9 , -1});
  40.     }
  41.  
  42.     node(char c , int i){
  43.         idx[c - 'a'].first = min(idx[c - 'a'].first , i);
  44.         idx[c - 'a'].second = max(idx[c - 'a'].second , i);
  45.         freq[c - 'a']++;
  46.     }
  47. };
  48.  
  49. struct SegTree{
  50.     int tree_size;
  51.     vector < node > tree;
  52.  
  53.     SegTree(int n){
  54.         tree_size = 1;
  55.         while (tree_size < n) tree_size *= 2;
  56.         tree.assign(2 * tree_size, node());
  57.     }
  58.  
  59.     void build(string & s , int ni , int lx , int rx){
  60.         if(rx - lx == 1){
  61.             if(lx < sz(s)){
  62.                 tree[ni].idx[s[lx] - 'a'].first = min(tree[ni].idx[s[lx] - 'a'].first , lx);
  63.                 tree[ni].idx[s[lx] - 'a'].second = max(tree[ni].idx[s[lx] - 'a'].second , lx);
  64.                 tree[ni].freq[s[lx] - 'a']++;
  65.             }
  66.             return;
  67.         }
  68.  
  69.         int mid = (lx + rx) / 2;
  70.         build(s , 2 * ni + 1 , lx , mid);
  71.         build(s , 2 * ni + 2 , mid , rx);
  72.  
  73.         tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
  74.     }
  75.  
  76.     void build(string & s){
  77.         build(s , 0 , 0 , tree_size);
  78.     }
  79.  
  80.     node merge(node &l , node &r){
  81.         node res;
  82.  
  83.         for(int i = 0 ; i < 26 ; i++){
  84.             res.freq[i] = l.freq[i] + r.freq[i];
  85.             res.max_freq[i] = max(res.max_freq[i] , res.freq[i]);
  86.             res.idx[i].first = min(l.idx[i].first , r.idx[i].first);
  87.             res.idx[i].second = max(l.idx[i].second , r.idx[i].second);
  88.             res.maxi = max(res.maxi , {res.freq[i] , (char)(i + 'a')});
  89.         }
  90. //        res.maxi = max(l.maxi , r.maxi);
  91. //        for(int i = 0; i < 26; i++){
  92. //            res.freq[i] = l.freq[i] + r.freq[i];
  93. //            res.maxi = max(res.maxi , {res.freq[i] , (char)(i + 'a')});
  94. //            res.idx.
  95. //        }
  96.         return res;
  97.     }
  98.  
  99.     void update(int idx , int val , int ni , int lx , int rx){
  100.         if(rx - lx == 1){
  101.             tree[ni].freq[val]++;
  102.             return;
  103.         }
  104.  
  105.         int mid = (lx + rx) / 2;
  106.         if(idx < mid){
  107.             update(idx , val , 2 * ni + 1 , lx , mid);
  108.         }else{
  109.             update(idx , val , 2 * ni + 2 , mid , rx);
  110.         }
  111.  
  112.         tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
  113.     }
  114.  
  115.     void update(int idx , int val){
  116.         update(idx , val , 0 , 0 , tree_size);
  117.     }
  118.  
  119.     node calc(int l , int r , int ni , int lx , int rx){
  120.         if(lx >= r || l >= rx) return node();
  121.         if(lx >= l && rx <= r) return tree[ni];
  122.  
  123.         int mid = (lx + rx) / 2;
  124.         node left = calc(l , r , 2 * ni + 1 , lx , mid);
  125.         node right = calc(l , r , 2 * ni + 2 , mid , rx);
  126.  
  127.         return merge(left , right);
  128.     }
  129.  
  130.     node calc(int l , int r){
  131.         return calc(l , r , 0 , 0 , tree_size);
  132.     }
  133. };
  134.  
  135. void solve(){
  136.     int n;
  137.     cin >> n;
  138.  
  139.     string s;
  140.     cin >> s;
  141.  
  142.     SegTree st(n);
  143.     st.build(s);
  144.  
  145.  
  146.     int q;
  147.     cin >> q;
  148.  
  149.     while(q--){
  150.         int l , r;
  151.         cin >> l >> r;
  152.         l--;
  153.  
  154.         node curr = st.calc(l , r);
  155.         bool ok = false;
  156.         int c =-1 , fre=0;
  157.         for(int i =0 ; i < 26 ; i++){
  158.             if(curr.freq[i] > fre ) {
  159.                 fre = curr.freq[i];
  160.                 c = i;
  161.             }
  162.         }
  163.         if(c == -1){
  164.             cout << "NO\n";
  165.             continue;
  166.         }
  167.         // cout << c << nl;
  168.  
  169.         for(int i = 0 ; i < 26 ; i++){
  170.             if( !(curr.freq[i] and fre > curr.freq[i]) ) continue;
  171.  
  172.             if((curr.freq[i] == 1 and curr.idx[i].first != l)){
  173.                 ok = true;
  174.                 break;
  175.             }
  176.             if((curr.freq[i] > 1 and (curr.idx[i].first != l or curr.idx[i].first + curr.freq[i] != curr.idx[i].second))){
  177.                 ok = true;
  178.                 break;
  179.             }
  180.         }
  181.  
  182.         cout << (ok ? "YES" :  "NO") << nl;
  183.     }
  184.  
  185. }
  186.  
  187. int main() {
  188.     // Sira();
  189.     int t = 1;
  190. //    cin >> t;
  191.     while(t--){
  192.         solve();
  193.     }
  194.     return 0;
  195. }
  196.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement