In this HackerEarth Shil and Palindrome Research problem solution Shil got interested in palindrome research. For that he needs some research data for a particular string S. To obtain this data he has some queries of following type:
  1. L x - update Lth character of string to x
  2. L R - find if all the character of string from index L to R can be rearranged such that they can form a palindrome. If they can print "yes", else print "no".
Since you decided to help Shil with his research, its your responsibililty to make this data available as soon as possible.


HackerEarth Shil and Palindrome Research problem solution


HackerEarth Shil and Palindrome Research problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e8

#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define mp make_pair
#define pb push_back
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
int bt[100011][26];
int N,Q;
void update(int ind ,int val,int pos){
    while(ind<=N){
        bt[ind][pos]+=val;
        ind+=(ind&-ind);
    }
}
int query(int ind,int pos){
    int ans=0;
    while(ind>0){
        ans+=bt[ind][pos];
        ind-=(ind&-ind);
    }
    return ans;
}
int main(){
    freopen("input-12.txt","r",stdin);
    freopen("output-12.txt","w",stdout);
    cin >> N >> Q;
    string S;
    cin >> S;
    rep(i,N){
        update(i+1,1,S[i]-'a');
    }
    int t,L,R;
    char x;
    while(Q--){
        cin >> t;
        if(t==1){
            cin >> L >> x;
            update(L,1,x-'a');
            update(L,-1,S[L-1]-'a');
            S[L-1]=x;
        }
        else{
            cin >> L >> R;
            int odd=0;
            int cur;
            rep(i,26){
                cur=query(R,i)-query(L-1,i);
                if(cur%2){
                    odd++;
                }
            }
            if(odd<=1){
                cout<<"yes\n";
            }
            else{
                cout<<"no\n";
            }
        }
    }
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define max 100002
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
ll tree[max][27];
 
ll read(ll idx, ll i) {
    ll sum = 0;
    while (idx > 0) {
        sum += tree[idx][i];
        idx -= (idx & -idx);
    }
    return sum;
}
void update(ll idx ,ll val, ll i) {
    while (idx <= max) {
        tree[idx][i] += val;
        idx += (idx & -idx);
    }
}
int main() 
{
    int n,q,x,l,r;
    cin>>n>>q;
    string str;
    char c;
    cin>>str;
    memset(tree,0,sizeof(tree));
    for(int i = 0; i < n; i++) {
        update(i+1,1,str[i]-97+1);
    }
    while(q--) {
        cin>>x;
        if(x == 1) {
            cin>>l>>c;
            update(l,-1,str[l-1]-97+1);
            str[l-1] = c;
            update(l,1,str[l-1]-97+1);
        }
        else {
            cin>>l>>r;
            int c = 0;
            for(int i = 1; i <= 26; i++) {
                if(l == 1) {
                    if(read(r,i)%2 == 1) {
                        c++;
                    }
                }
                else {
                    if((read(r,i)-read(l-1,i))%2 == 1) {
                        c++;
                    }
                }
            }
            puts(c <= 1?"yes":"no");
        }
    }
    return 0;
}