好题!
首先说这道题的时间复杂度:\(O(26n\sqrt n)\)。因为转移是的常数是 \(O(26)\) 并非 \(O(1)\),这启示我们,看数据范围,不要被O(1)给限制了,O(1)是一般情况,有些题不一般
首先,回文串能出现的条件是所有的字符都出现偶数次 \(or\) 仅有一个字符出现奇数次,所以我们并不关心每个字符出现多少次,只关注他们的奇偶。
因为只有 \(26\) 个字符,所以考虑状压,对于每个字符:\(1\) 表示出现奇数次,\(0\) 表示出现偶数次,对于新加入的字符,使用异或就好了。
考虑前缀和,令 \(a_i\) 表示 \([1,i]\) 这个区间内每个字符的奇偶次数,那么就有区间 \([l,r]\) 每个字符出现的奇偶次数为 \(a_r \oplus a_{l-1}\)
最后,对于这道题,我们考虑使用莫队,假设我们已经知道了 \([l,r]\) 的答案,那么求 \([l,r+1]\) 的答案时候就可以只加入 \(a_{r+1}\) ,然后判断区间 \([l,r]\) 中与 \(a_{r+1}\)异或为 \(0\) 的 \(a_x\) 个数和与其异或为 \(2^i\) 的 \(a_x\) 个数。
上代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=60050;
ll n,m,a[N],b[N],sq;
char sr[N];
struct jgt
{
ll l,r,id;
}q[N];
ll ans[N];
bool cmp(jgt t1,jgt t2)
{
return (b[t1.l]^b[t2.l])?b[t1.l]<b[t2.l]:((b[t1.l]&1)?t1.r<t2.r:t1.r>t2.r);
}
ll now;
ll cnt[(1<<26)+50];
void add(ll wz)
{
now+=cnt[a[wz]];
cnt[a[wz]]++;
for(ll i=0;i<26;i++)
now+=cnt[a[wz]^(1<<i)];
}
void del(ll wz)
{
cnt[a[wz]]--;
now-=cnt[a[wz]];
for(ll i=0;i<26;i++)
now-=cnt[a[wz]^(1<<i)];
}
int main()
{
scanf("%lld %lld",&n,&m);
scanf("%s",sr+1);
sq=sqrt(n);
for(ll i=1;i<=n;i++)
{
a[i]=1<<(sr[i]-'a');
a[i]^=a[i-1];
}
for(ll i=0;i<=n;i++)
b[i]=i/sq+1;
for(ll i=1;i<=m;i++)
{
scanf("%lld %lld",&q[i].l,&q[i].r);
q[i].l--;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
ll le=0,ri=0;
cnt[0]++;
for(ll i=1;i<=m;i++)
{
while(ri<q[i].r) add(++ri);
while(le>q[i].l) add(--le);
while(ri>q[i].r) del(ri--);
while(le<q[i].l) del(le++);
ans[q[i].id]=now;
}
for(ll i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
标签:奇偶,字符,题解,ll,t2,t1,异或,美好,P3604
From: https://www.cnblogs.com/pengchujie/p/17674663.html