Gyanbaba's Admission Test 2

This problem can be solved with Mo's Algorithm. Before reading the rest of the editorial, I'd like to suggest you to go through this tutorial of Mo's algorithm.

Let's learn a technique to represent a string with bitmask, where each bit will represent a character from 'a' to 'z'. ith bit is on if the ith character appears in the string odd times, and it's off otherwise. So, a string can be permuted to create a palindrome if all the bits are off or only one of the bits are on.

Now, let's keep a cumulative xor array. Here we'll turn the corresponding bit of ith character on and xor it with the cumulative xor of index i-1. Also keep a reverse version of this array (i.e. from right to left). We'll also maintain two frequency arrays, one for the forward part, and another for the reverse one. While adding an index in Mo's algorithm we'll increase the frequency of the cumulative xor from left of that index.

We can say the number of new sub-strings, that can be permuted to create palindromes, after adding ith index by checking the frequency array. For even palindromes, we'll have to check the frequency of the cumulative xor till ith index. And for odd palindromes, we'll have to iterate over the characters and toggle the corresponding bit of that character, and look for the frequency of that mask.

While adding indices in right, we're dealing with the forward cumulative xor array and frequency array. For adding in left, we'll use the reverse ones. For removing indices, we'll have to do the opposite of what we've done for adding.

C++ Solution by problem author (Sourav Sen Tonmoy)

#include <bits/stdc++.h>

#define rep(i,n) for(i=0; i<n; i++)
#define repl(i,n) for(i=1; i<=n; i++)

#define sz(x) (int) x.size()
#define pb push_back
#define all(x) x.begin(),x.end()
#define uu first
#define vv second
#define mem(x, y) memset(x, y, sizeof(x))
#define un(x) x.erase(unique(all(x)), x.end())

#define sdi(x) scanf("%d", &x)
#define sdii(x, y) scanf("%d %d", &x, &y)
#define sdiii(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define sdl(x) scanf("%lld", &x)
#define sdll(x, y) scanf("%lld %lld", &x, &y)
#define sdlll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
#define sds(x) scanf("%s", x)
#define pfi(x) printf("%d\n", x)
#define pfii(x, y) printf("%d %d\n", x, y)
#define pfiii(x, y, z) printf("%d %d %d\n", x, y, z)
#define pfl(x) printf("%lld\n", x)
#define pfll(x, y) printf("%lld %lld\n", x, y)
#define pflll(x, y, z) printf("%lld %lld %lld\n", x, y, z)

#define eps 1e-9
#define OK cerr << "ok\n"
#define DB(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> pii;

inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

//int kx[] = {+2, +1, -1, -2, -2, -1, +1, +2};
//int ky[] = {+1, +2, +2, +1, -1, -2, -2, -1}; //Knight Direction
//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction


const int MAXN=50005, MAXQ=50005, ALPHA=26;
unsigned n, q, bucket;
char str[MAXN];
int Left=-1, Right=-1;
unsigned cum[2][MAXN], freq[2][(1<<ALPHA)+3], ans, out[MAXQ];
bool flag;
struct data {
    unsigned l, r, idx, ld;

    bool operator < (const data &p) const {
        if(ld < p.ld) return true;
        else if(ld == p.ld) {
            if(ld&1) {
                if(r < p.r) return true;
                else return false;
            }
            else {
                if(r > p.r) return true;
                else return false;
            }
        }
        else return false;
    }
} query[MAXQ];

inline unsigned f(unsigned type, unsigned mask) {
    unsigned ret = 0;
    int i;
    int now = cum[0][Right];
    if(Left) now ^= cum[0][Left-1];
    if(__builtin_popcount(now) <= 1) ret++;
    ret += freq[type][mask];
    rep(i, ALPHA) {
        unsigned cur = mask ^ (1<<i);
        ret += freq[type][cur];
    }
    return ret;
}

inline void add(unsigned idx, bool isLeft) {
    if(Left == -1 && Right == -1) {
        Left = 0, Right = 0;
    }
    if(idx == Left-1) Left--;
    else if(idx == Right+1) Right++;
    if(isLeft) ans += f(1, cum[1][idx]);
    else ans += f(0, cum[0][idx]);
    freq[0][ cum[0][idx] ]++;
    freq[1][ cum[1][idx] ]++;
}

inline void rmv(unsigned idx, bool isLeft) {
    freq[0][ cum[0][idx] ]--;
    freq[1][ cum[1][idx] ]--;
    if(isLeft) ans -= f(1, cum[1][idx]);
    else ans -= f(0, cum[0][idx]);
    if(idx == Left) Left++;
    else if(idx == Right) Right--;
}

void MO() {
    unsigned i, l=0, r=0;
    rep(i, q) {
        if(query[i].l == 3 && query[i].r == 5) flag = true;
        while(l > query[i].l) {
            add(l-1, true);
            l--;
        }
        while(r <= query[i].r) {
            add(r, false);
            r++;
        }
        while(l < query[i].l) {
            rmv(l, true);
            l++;
        }
        while(r > query[i].r+1) {
            rmv(r-1, false);
            r--;
        }
        out[query[i].idx] = ans;
        flag = false;
    }

    rep(i, q) printf("%u\n", out[i]);
}

int main() {
//    freopen("4.in","r",stdin);
//    freopen("4.out","w",stdout);

    clock_t st = clock();

    int i;

    scanf("%u %u", &n, &q);
    assert(1<=n && n<=50000);
    assert(1<=q && q<=50000);
    sds(str);
    assert(n == strlen(str));
    rep(i, n) assert('a'<=str[i] && str[i]<='z');
    bucket = sqrt(n);

    rep(i, n) {
        cum[0][i] = 1 << (str[i]-'a');
        if(i) cum[0][i] ^= cum[0][i-1];
    }
    for(i=n-1; i>=0; i--) {
        cum[1][i] = 1 << (str[i]-'a');
        if(i!=n-1) cum[1][i] ^= cum[1][i+1];
    }

    rep(i, q) {
        scanf("%u %u", &query[i].l, &query[i].r);
        assert(0<=query[i].l && query[i].l<=n-1);
        assert(0<=query[i].r && query[i].r<=n-1);
        assert(query[i].l <= query[i].r);
        query[i].idx = i;
        query[i].ld = query[i].l / bucket;
    }
    sort(query, query+q);
    MO();

    clock_t en = clock();
    fprintf(stderr, "%.3f sec\n", (double)(en-st) / (double)CLOCKS_PER_SEC);

    return 0;
}

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define MOD(x,y) (((x)*(y))%mod)
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,cur) N=(N|(1<<cur))
#define Reset(N,cur) N=(N&(~(1<<cur)))
#define Check(N,cur) (!((N&(1<<cur))==0))
#define dbgA(A,i) debug("At pos: ",i," = ",A[i])
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)

#ifdef forthright48
#include
clock_t tStart = clock();
#define debug(args...) {dbg,args; cerr<<endl;}
#define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#define bug printf("%d\n",LINE);

#else
#define debug(args...) // Just strip off all debug tokens
#define timeStamp
#endif

struct debugger{
template debugger& operator , (const T& v){
cerr<<v<<" ";
return *this;
}
}dbg;

#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;

inline vlong gcd ( vlong a, vlong b ) {
a = ABS ( a ); b = ABS ( b );
while ( b ) { a = a % b; swap ( a, b ); } return a;
}

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
x2 = 1; y2 = 0; x1 = 0; y1 = 1;
for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
q = r2 / r1; r = r2 % r1;
x = x2 - (q * x1); y = y2 - (q * y1);
}
*X = x2; *Y = y2;
return r2;
}

inline vlong modInv ( vlong a, vlong m ) {
vlong x, y;
ext_gcd( a, m, &x, &y );
x %= m;
if ( x < 0 ) x += m;
return x;
}

inline vlong power ( vlong a, vlong p ) {
vlong res = 1, x = a;
while ( p ) {
if ( p & 1 ) res = ( res * x );
x = ( x * x ); p >>= 1;
}
return res;
}

inline vlong bigmod ( vlong a, vlong p, vlong m ) {
vlong res = 1 % m, x = a % m;
while ( p ) {
if ( p & 1 ) res = ( res * x ) % m;
x = ( x * x ) % m; p >>= 1;
}
return res;
}

inline int STRLEN(char *s){
int p = 0; while(s[p]) p++; return p;
}

inline LL SQRT(LL a){
LL v = sqrt(a);
if(SQ(v) == a) return v;
else if(SQ(v+1) == a) return v+1;
else if(SQ(v+2) == a) return v+2;
else return -1; /// a can no be written as p^2
}

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};

const vlong inf = 10000000000000000;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

///========================= TEMPLATE ENDS HERE ========================///
///=======================================================================///

#define Size 100055
const int blockSize = 230;

int N,Q;
char s[Size];
int res[Size];
int ans = 0;

struct qry {
int l, r, id;
};

bool cmp(qry A, qry B) {
if (A.l / blockSize == B.l / blockSize) return A.r < B.r;
return A.l / blockSize < B.l / blockSize;
}

qry QRY[Size+10];
int curL = 0,curR = 0;

int cumLeft[Size];
int cumRight[Size];
int mapLeft[(1<<27)+10];
int mapRight[(1<<27)+10];

void add(int pos,int f) {
int mask,rngMask;
if(f == 0){ /// Insert at left
mask = cumRight[pos];
ans += mapRight[mask];
rngMask = cumRight[pos] ^ cumRight[curR+1];
}else{ /// Insert at right
mask = cumLeft[pos];
ans += mapLeft[mask];
rngMask = cumLeft[pos] ^ cumLeft[curL-1];
}

if(POPCOUNT(rngMask) <= 1) ans++;

for(int d = 0;d<26;d++){
    int prv = ans;
    int nMask = (mask ^ (1<<d));
    if(f == 0)  ans += mapRight[nMask];
    else ans += mapLeft[nMask];
}
mapRight[cumRight[pos]]++;
mapLeft[cumLeft[pos]]++;

}

void rem(int pos,int f) {
int mask,rngMask;
mapRight[cumRight[pos]]--;
mapLeft[cumLeft[pos]]--;
if(f == 0){ /// Remove at left
mask = cumRight[pos];
ans -= mapRight[mask];
rngMask = cumRight[pos] ^ cumRight[curR+1];
}else{ /// Remove at right
mask = cumLeft[pos];
ans -= mapLeft[mask];
rngMask = cumLeft[pos] ^ cumLeft[curL-1];
}

if(POPCOUNT(rngMask) <= 1) ans--;

for(int d = 0;d<26;d++){
    int prv = ans;
    int nMask = (mask ^ (1<<d));
    if(f == 0)  ans -= mapRight[nMask];
    else ans -= mapLeft[nMask];
}

}

int main () {

#ifdef forthright48
freopen ( "input.txt", "r", stdin );
freopen ( "output2.txt", "w", stdout );
#endif // forthright48

scanf("%d %d %s",&N,&Q,s);

int Len = strlen(s);
assert(N>=1 && N<=50000);   ///ASSERT
assert(Q>=1 && Q<=50000);   ///ASSERT
assert(Len>=1 && Len<=N);   ///ASSERT

for (int i = 1; i <= Q; i++) {
	scanf("%d %d", &QRY[i].l, &QRY[i].r);
    assert(QRY[i].l>=0 && QRY[i].l<N);   ///ASSERT
    assert(QRY[i].r>=0 && QRY[i].r<N);   ///ASSERT
    assert(QRY[i].r>=QRY[i].l);   ///ASSERT
	QRY[i].l++;
	QRY[i].r++;
	QRY[i].id = i;
}

sort(QRY+1, QRY+Q+1, cmp);

CLR(cumLeft,0);CLR(cumRight,0);
CLR(mapLeft,0);CLR(mapRight,0);

for(int i = 1;i<=N;i++){
    int d = s[i-1] - 'a';
    assert(d>=0 && d<26);   ///ASSERT
    cumLeft[i] = (cumLeft[i-1] ^ (1<<d));
}

for(int i = N;i>=1;i--){
    int d = s[i-1] - 'a';
    cumRight[i] = (cumRight[i+1] ^ (1<<d));
}

for (int i = 1; i <= Q; i++) {
	int L = QRY[i].l, R = QRY[i].r;
	while (curL < L) {
        if (curL != 0) rem(curL,0);
        curL++;
	}
	while (curL > L) {
        curL--;
        add(curL,0);
	}
	while (curR < R) {
        curR++;
        add(curR,1);
	}
	while (curR > R) {
        rem(curR,1);
        curR--;
	}
	res[QRY[i].id] = ans;
}

for (int i = 1; i <= Q; i++) {
	printf("%d\n", res[i]);
}

return 0;

}