P3604 美好的每一天（莫队）

Description

State

Input

Output

Solution

Code

Description

如果一个区间可以重排为回文串，那么称其为妄想区间，多次询问 \([l,r]\) 有多少个妄想区间

State

\(n,m<=60000\)

Input

6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1

Output

16
4
2
2
3
1

Solution

如果一个区间为妄想区间，那么最多只有一个字符串过奇数次

一个字符所对应的贡献为其与他前面所有连续的字符所构成的连续区间，所以另 \(a[i]\) 为 \(1-i\) 的状态，\(0\) 表示该字符串出现过偶数次，这样每个字符都可以找到它所对应的贡献

\(hint:\) 总数不会超过 \(6e4\) 所以 \(unsigned \ short\) 用来存储数的个数可不超内存

Code

const int N = 6e4 + 5;
 
    int n, m;
    int a[N];
    struct Query
    {
        int l, r;
        int bel;
        int id;
        void read(){ sdd(l, r); }
        bool operator<(Query o){
            return bel ^ o.bel ? l < o.l: r < o.r;
        }
    }q[N];
    int ans[N], now, block;
    unsigned short vis[(1<<26) + 5];

void mo()
{
    block = 3 * sqrt(n);
    for(int i = 1; i <= m; i ++){
        q[i].l --;
        q[i].bel = q[i].l / block + 1;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
}

void add(int pos)
{
    int x = a[pos];
    now += vis[x];
    for(int i = 0; i < 26; i ++){
        now += vis[x ^ (1 << i)]; 
    }
    vis[x] ++;
}

void del(int pos)
{
    int x = a[pos];
    vis[x] --;
    now -= vis[x];
    for(int i = 0; i < 26; i ++){
        now -= vis[x ^ (1 << i)]; 
    }
}

signed main()
{
    while(~ sdd(n, m)){
        for(int i = 1; i <= n; i ++){
            char ch;
            sc(ch);
            a[i] = a[i - 1] ^ (1 << (ch - 'a'));
        }
        rep(i, 1, m){
            q[i].read();
        }
        mo();
        int l = 1, r = 0; 
        now = 0;
        for(int i = 1; i <= m; i ++){
            while(l > q[i].l) add(-- l);
            while(r < q[i].r) add(++ r);
            while(l < q[i].l) del(l ++);
            while(r > q[i].r) del(r --);
            ans[q[i].id] = now;
        }
        rep(i, 1, m) pd(ans[i]);
    }
    return 0;
}