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 > freq;
- node(){
- maxi = {0 , 'a'};
- freq.assign(26 , 0);
- }
- };
- 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].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;
- 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')});
- }
- 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);
- }
- pair < ll , char > calc(int l , int r){
- return calc(l , r , 0 , 0 , tree_size).maxi;
- }
- };
- void solve(){
- int n;
- cin >> n;
- string s;
- cin >> s;
- SegTree st(n);
- st.build(s);
- map < char , vector < int > > mp;
- for(int i = 0; i < n; i++){
- mp[s[i]].push_back(i);
- }
- int q;
- cin >> q;
- while(q--){
- int l , r;
- cin >> l >> r;
- l--;
- auto up = upper_bound(all(mp[st.calc(l , r).second]) , r - 1);
- auto low = lower_bound(all(mp[st.calc(l , r).second]) , l);
- // cout << up - low << nl;
- if(abs(low - up) == abs(r - l) or st.calc(l , r).first == 1){
- cout << "NO" << nl;
- }else{
- int up2 = *up;
- int low2 = *low;
- if(up2 < n - 1 and (up2 - low2 + 1) != (low - up)) cout << "NO" << nl;
- else cout << "YES" << nl;
- }
- cout << st.calc(l , r).first << " " << st.calc(l , r).second << nl;
- }
- }
- int main() {
- Sira();
- int t = 1;
- // cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement