Advertisement
ismaeil

D. Irreducible Anagrams

Aug 4th, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 5e2;
  5. #define rg (p << 1) | 1
  6. #define lf (p << 1)
  7.  
  8. string s;
  9. int n ,q;
  10.  
  11. string Read(){
  12.     static char Buff[N];
  13.     scanf("%s" ,Buff);
  14.     return Buff;
  15. }
  16.  
  17. class SegTree{
  18.     private:
  19.         vector< set< char > > Seg;
  20.  
  21.         void Compain(set< char > &Res ,set< char > &a ,set< char > &b) {
  22.             for(auto i : a) Res.insert(i);
  23.             for(auto i : b) Res.insert(i);
  24.         }
  25.  
  26.         void BLD(int p ,int L ,int R) {
  27.             if( L == R ){
  28.                 Seg[p].insert( s[L] );
  29.                 return;
  30.             }
  31.  
  32.             int Mid = (L + R) >> 1;
  33.             BLD(lf ,L ,Mid);
  34.             BLD(rg ,Mid + 1 , R);
  35.             Compain(Seg[p] ,Seg[lf] ,Seg[rg]);
  36.         }
  37.  
  38.         set< char > QRY(int i ,int j ,int p ,int L ,int R){
  39.             if( R <  i || j <  L ) return set< char >();
  40.             if( i <= L && R <= j ) return Seg[p];
  41.  
  42.             int Mid = (L + R) >> 1;
  43.             set< char > LF  = QRY(i ,j ,lf ,L ,Mid);
  44.             set< char > RG  = QRY(i ,j ,rg ,Mid + 1 ,R);
  45.             set< char > Res; Compain(Res ,LF ,RG);
  46.             return Res;
  47.         }
  48.  
  49.     public:
  50.         SegTree(){}
  51.  
  52.         void BLD(int Sz){
  53.             Seg.assign(Sz * 4 ,set< char >());
  54.             BLD(1 ,0 ,n - 1);
  55.         }
  56.  
  57.         int QRY(int L ,int R){
  58.             set< char > Q = QRY(L ,R ,1 ,0 ,n - 1);
  59.             return (int)Q.size();
  60.         }
  61. } ST ;
  62.  
  63. inline void Solve(){
  64.     int L ,R; scanf("%d%d" ,&L ,&R);
  65.     int Q = ST.QRY(L - 1 ,R - 1);
  66.    
  67.     bool flag  = (R == L || Q > 1);
  68.     puts( flag ? "Yes" : "No" );
  69. }
  70.  
  71. int main() {
  72.     s = Read();
  73.     n = s.size();
  74.  
  75.     ST.BLD(n);
  76.  
  77.     scanf("%d" ,&q);
  78.     while( q-- ) Solve();
  79.     return 0;
  80. }
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement