NC14687. 重排的回文串
描述
给一个长为 n 的只含小写字母的字符串
每次查询一个区间 [l,r] 内，有多少子区间可以重排为一个回文串
一个区间可以重排为一个回文串：
就是说我们可以以一定顺序排列这个区间内的所有数使得排列后为一个回文串
输入描述
第一行两个正整数n,m
第二行一个长为 n 的字符串
之后 m 行每行两个数 l 和 r
输出描述
对于每个询问，输出一个整数表示答案
示例1
输入:
6 5 zzqzzq 2 4 3 4 2 3 4 5 1 1
输出:
4 2 2 3 1
说明:
[2,4]为zqz,其中[2,2],[3,3],[4,4],[2,4]都可以重排为一个回文串C++14(g++5.4) 解法, 执行用时: 278ms, 内存消耗: 7912K, 提交时间: 2019-03-28 21:22:57
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=60005;
struct node{
int l,r,id;
}q[N];
int n,m,len,b[N],c[N],d[N],pos[N],num[N];
char s[N];
vector<int>f[N];
ll res,ans[N];
int cmp(node a,node b)
{
return (a.l/len!=b.l/len)?a.l<b.l:((a.l/len)&1)?a.r<b.r:a.r>b.r;
}
void add(int x)
{
res+=num[d[x]];
for(int i=0;i<f[x].size();i++)res+=num[f[x][i]];
num[d[x]]++;
}
void del(int x)
{
num[d[x]]--;
res-=num[d[x]];
for(int i=0;i<f[x].size();i++)res-=num[f[x][i]];
}
int main()
{
scanf("%d%d",&n,&m);
len=sqrt(n);
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
s[i]-='a';
c[i]=c[i-1]^(1<<s[i]);
b[i]=c[i];
}
b[0]=0;
sort(b,b+n+1);
int Len=unique(b,b+n+1)-b;
for(int i=1;i<=n;i++)d[i]=lower_bound(b,b+Len,c[i])-b;
for(int i=0;i<=n;i++)
for(int j=0;j<26;j++)
{
int pos=lower_bound(b,b+Len,c[i]^(1<<j))-b;
if(pos<Len&&b[pos]==(c[i]^(1<<j)))f[i].push_back(pos);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].l--;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
res=0;
int l=1,r=0;
for(int i=1;i<=m;i++)
{
while(l<q[i].l)del(l++);
while(l>q[i].l)add(--l);
while(r<q[i].r)add(++r);
while(r>q[i].r)del(r--);
ans[q[i].id]=res;
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 298ms, 内存消耗: 6632K, 提交时间: 2017-12-17 22:00:17
#include<bits/stdc++.h>
using namespace std;
#define N 60006
char str[N];
struct node{int l,r,id;}s[N];
int ans[N],S,A[N],n,m,Res,cnt[N];
vector<int>bits[N];
bool cmp(node A,node B){
if(A.l/S!=B.l/S)return A.l<B.l;
if((A.l/S)&1)return A.r>B.r;
return A.r<B.r;
}
void Add(int i){
for(int j=0;j<bits[i].size();++j)Res+=cnt[bits[i][j]];
cnt[A[i]]++;
}
void Del(int i){
cnt[A[i]]--;
for(int j=0;j<bits[i].size();++j)Res-=cnt[bits[i][j]];
}
void solve(){
int L=0,R=-1;Res=0;
for(int i=0;i<m;++i){
while(R<s[i].r)Add(++R);
while(R>s[i].r)Del(R--);
while(L<s[i].l)Del(L++);
while(L>s[i].l)Add(--L);
ans[s[i].id]=Res;
}
}
int B[N];
int main(){
scanf("%d %d",&n,&m);
S=sqrt(n);
scanf("%s",str+1); B[0]=0;
for(int i=1;i<=n;++i){
A[i]=A[i-1]^(1<<(str[i]-'a'));
B[i]=A[i];
}
sort(B,B+n+1);
int p=unique(B,B+n+1)-B;
for(int i=0;i<=n;i++){
for(int j=0;j<26;j++){
int k=lower_bound(B,B+p,A[i]^(1<<j))-B;
if(B[k]==(A[i]^(1<<j)))
bits[i].push_back(k);// ^ = 1<<j
}
bits[i].push_back(A[i]=lower_bound(B,B+p,A[i])-B);// ^ = 0
}
for(int i=0;i<m;++i){
scanf("%d %d",&s[i].l,&s[i].r);
s[i].l--; s[i].id=i;
}
sort(s,s+m,cmp);
solve();
for(int i=0;i<m;++i)printf("%d\n",ans[i]);
return 0;
}