Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define nl "\n"
- #define ll long long
- #define mod 1'000'000'007
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define sz(v) (int) v.size()
- template<typename T = int>
- istream &operator>>(istream &in, vector<T> &v) {
- for (auto &x: v) in >> x;
- return in;
- }
- template<typename T = int>
- ostream &operator<<(ostream &out, const vector<T> &v) {
- for (const T &x: v) out << x << " ";
- return out;
- }
- void Sira() {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- struct node {
- pair < ll , char > maxi;
- vector < int > max_freq;
- vector < int > freq;
- vector < pair < int , int > > idx;
- node(){
- maxi = {0 , 'a'};
- freq.assign(26 , 0);
- max_freq.assign(26 , 0);
- idx.assign(26 , { 1e9 , -1});
- }
- node(char c , int i){
- idx[c - 'a'].first = min(idx[c - 'a'].first , i);
- idx[c - 'a'].second = max(idx[c - 'a'].second , i);
- freq[c - 'a']++;
- }
- };
- struct SegTree{
- int tree_size;
- vector < node > tree;
- SegTree(int n){
- tree_size = 1;
- while (tree_size < n) tree_size *= 2;
- tree.assign(2 * tree_size, node());
- }
- void build(string & s , int ni , int lx , int rx){
- if(rx - lx == 1){
- if(lx < sz(s)){
- tree[ni].idx[s[lx] - 'a'].first = min(tree[ni].idx[s[lx] - 'a'].first , lx);
- tree[ni].idx[s[lx] - 'a'].second = max(tree[ni].idx[s[lx] - 'a'].second , lx);
- tree[ni].freq[s[lx] - 'a']++;
- }
- return;
- }
- int mid = (lx + rx) / 2;
- build(s , 2 * ni + 1 , lx , mid);
- build(s , 2 * ni + 2 , mid , rx);
- tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
- }
- void build(string & s){
- build(s , 0 , 0 , tree_size);
- }
- node merge(node &l , node &r){
- node res;
- for(int i = 0 ; i < 26 ; i++){
- res.freq[i] = l.freq[i] + r.freq[i];
- res.max_freq[i] = max(res.max_freq[i] , res.freq[i]);
- res.idx[i].first = min(l.idx[i].first , r.idx[i].first);
- res.idx[i].second = max(l.idx[i].second , r.idx[i].second);
- res.maxi = max(res.maxi , {res.freq[i] , (char)(i + 'a')});
- }
- // res.maxi = max(l.maxi , r.maxi);
- // for(int i = 0; i < 26; i++){
- // res.freq[i] = l.freq[i] + r.freq[i];
- // res.maxi = max(res.maxi , {res.freq[i] , (char)(i + 'a')});
- // res.idx.
- // }
- return res;
- }
- void update(int idx , int val , int ni , int lx , int rx){
- if(rx - lx == 1){
- tree[ni].freq[val]++;
- return;
- }
- int mid = (lx + rx) / 2;
- if(idx < mid){
- update(idx , val , 2 * ni + 1 , lx , mid);
- }else{
- update(idx , val , 2 * ni + 2 , mid , rx);
- }
- tree[ni] = merge(tree[2 * ni + 1] , tree[2 * ni + 2]);
- }
- void update(int idx , int val){
- update(idx , val , 0 , 0 , tree_size);
- }
- node calc(int l , int r , int ni , int lx , int rx){
- if(lx >= r || l >= rx) return node();
- if(lx >= l && rx <= r) return tree[ni];
- int mid = (lx + rx) / 2;
- node left = calc(l , r , 2 * ni + 1 , lx , mid);
- node right = calc(l , r , 2 * ni + 2 , mid , rx);
- return merge(left , right);
- }
- node calc(int l , int r){
- return calc(l , r , 0 , 0 , tree_size);
- }
- };
- void solve(){
- int n;
- cin >> n;
- string s;
- cin >> s;
- SegTree st(n);
- st.build(s);
- int q;
- cin >> q;
- while(q--){
- int l , r;
- cin >> l >> r;
- l--;
- node curr = st.calc(l , r);
- bool ok = false;
- int c =-1 , fre=0;
- for(int i =0 ; i < 26 ; i++){
- if(curr.freq[i] > fre ) {
- fre = curr.freq[i];
- c = i;
- }
- }
- if(c == -1){
- cout << "NO\n";
- continue;
- }
- // cout << c << nl;
- for(int i = 0 ; i < 26 ; i++){
- if( !(curr.freq[i] and fre > curr.freq[i]) ) continue;
- if((curr.freq[i] == 1 and curr.idx[i].first != l)){
- ok = true;
- break;
- }
- if((curr.freq[i] > 1 and (curr.idx[i].first != l or curr.idx[i].first + curr.freq[i] != curr.idx[i].second))){
- ok = true;
- break;
- }
- }
- cout << (ok ? "YES" : "NO") << nl;
- }
- }
- int main() {
- // Sira();
- int t = 1;
- // cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement