如果我让你查回文你还爱我吗

C++(g++ 7.5.0) 解法, 执行用时: 1629ms, 内存消耗: 74732K, 提交时间: 2022-09-13 18:22:15

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400007;
char s[N];
struct node
{
	int l,r;
	int sum,lazyp;
}t[N<<2];
void pushup(int k)
{
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void f(int k,int v)
{
	t[k].sum+=(t[k].r-t[k].l+1)*v;
	t[k].lazyp+=v;
}
void pushdown(int k)
{
	f(k<<1,t[k].lazyp);
	f(k<<1|1,t[k].lazyp);
	t[k].lazyp=0;
}
void build(int k,int l,int r)
{
	t[k].l=l;
	t[k].r=r;
	t[k].lazyp=0;
	if(l==r)
	{
		t[k].sum=t[k].lazyp=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void modify(int k,int l,int r,int v)
{
	if(l<=t[k].l&&t[k].r<=r)
	{
		f(k,v);
		return ;
	}
	int mid=(t[k].l+t[k].r)>>1;
	pushdown(k);
	if(l<=mid)
		modify(k<<1,l,r,v);
	if(r>mid)
		modify(k<<1|1,l,r,v);
	pushup(k);
}
int query(int k,int l,int r)
{
	if(l<=t[k].l&&t[k].r<=r)
	{
		return t[k].sum;
	}
	int mid=(t[k].l+t[k].r)>>1;
	pushdown(k);
	if(r<=mid)
		return query(k<<1,l,r);
	else if(l>mid)
		return query(k<<1|1,l,r);
	else return query(k<<1,l,r)+query(k<<1|1,l,r);
}
int p[N];
int n;
void init(string &t)
{
	n=0;
	s[n++]='@';
	s[n++]='#';
	for(auto i:t)
	{
		s[n++]=i;
		s[n++]='#';
	}
	s[n++]='^';
}
void manacher()
{
	int mr=0,mid=0;
	for(int i=1;i<n;i++)
	{
		if(i<mr)
			p[i]=min(p[2*mid-i],mr-i);
		else 
			p[i]=1;
			
		while(s[i-p[i]]==s[i+p[i]])p[i]++;
		
		if(i+p[i]>mr)
		{
			mr=i+p[i];
			mid=i;
		}
	}
}
vector<pair<int,int> >L[N],R[N];
int ans[N];
int len[N];
int32_t main()
{
	int q;
	cin>>n>>q;
	string t1;
	cin>>t1;
	init(t1);
	manacher();
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		len[i]=r-l+1;
		int mid=(2*l-1+2*r+1)>>1;
		L[mid].push_back({2*l-1,i});
		R[mid+1].push_back({2*r+1,i});
	}
	build(1,0,n+2);
	for(int i=1;i<n;i++)
	{
		modify(1,i-p[i]+1,i,1);
		for(auto &[pos,id]:L[i])
		{
			ans[id]+=query(1,pos,n+1);
		}
	}
	build(1,0,n+2);
	for(int i=n-1;i>0;i--)
	{
		modify(1,i,i+p[i]-1,1);
		for(auto &[pos,id]:R[i])
		{
			ans[id]+=query(1,1,pos);
		}
	}
	for(int i=1;i<=q;i++)
	{
		cout<<((ans[i]>>1)-((len[i]+1)>>1))<<endl;
	}
}

C++ 解法, 执行用时: 457ms, 内存消耗: 96668K, 提交时间: 2022-02-11 20:43:52

#include<bits/stdc++.h>
using namespace std;
#define N 400020
#define LL long long
LL n,q,r[N],s[N],L,R,m,mx,id,ans[N],a[N],b[N],sl[N],sr[N];
vector<LL>dl[N],dr[N];
vector<pair<LL,LL>>ql[N],qr[N];
struct BIT
{
	LL t[2][N];
	LL lowbit(LL x){return x&(-x);}
	void cg(LL o,LL x,LL c){while(x<N)t[o][x]+=c,x+=lowbit(x);}
	LL ask(LL o,LL x){LL r=0;while(x)r+=t[o][x],x-=lowbit(x);return r;}
	LL ask(LL o,LL l,LL r){return ask(o,r)-ask(o,l-1);}
	LL query(LL k,LL l,LL r){return ask(0,l,r)+k*ask(1,l,r);}
}tl,tr;
int main()
{
	scanf("%lld%lld",&n,&q);
	for(LL i=1;i<=n;i++){
		char ch=getchar();
		while(ch<'a' || ch>'z')ch=getchar();
		s[i*2-1]=ch-'a'+1;
		s[i*2]=27;
	}
	n=n*2-1,s[0]=27;
	for(LL i=1;i<=n;i++){
		r[i]=1;
		if(mx>i)r[i]=min(r[2*id-i],mx-i+1);
		while(0<=i-r[i] && i+r[i]<=n+1 && s[i+r[i]]==s[i-r[i]])r[i]++;
		if(i+r[i]-1>mx)mx=i+r[i]-1,id=i;
	}
	for(LL i=1;i<=n;i++){
		r[i]=r[i]/2;
		if(i&1)a[i]=r[i]-i/2-1;else a[i]=r[i]-i/2;
		b[i]=r[i]+i/2-1;
		if(a[i]>=0)a[i]=0,tl.cg(1,i,1);
		else dl[-a[i]*2].push_back(i),tl.cg(0,i,a[i]);
		if(b[i]>=(n+1)/2)b[i]=(n+1)/2,tr.cg(1,i,1);
		else dr[b[i]*2].push_back(i),tr.cg(0,i,b[i]);
		sl[i]=sl[i-1]+(i&1?i/2+1:i/2);
		sr[i]=sr[i-1]+(1-i/2);
	}
	for(LL i=1;i<=q;i++){
		scanf("%lld%lld",&L,&R);
		m=L+R-1,L=L*2-1,R=R*2-1;
		ans[i]+=sl[m]-sl[L-1]+sr[R]-sr[m];
		ql[L].push_back(make_pair(i,m));
		qr[R].push_back(make_pair(i,m));
	}
	for(LL i=1;i<=n;i++){
		for(auto j:dl[i])tl.cg(0,j,-a[j]),tl.cg(1,j,1);
		for(auto pi:ql[i])ans[pi.first]+=tl.query(-i/2,i,pi.second);
	}
	for(LL i=n;i>=1;i--){
		for(auto j:dr[i])tr.cg(0,j,-b[j]),tr.cg(1,j,1);
		for(auto pi:qr[i])ans[pi.first]+=tr.query(i/2,pi.second+1,i);
	}
	for(LL i=1;i<=q;i++)printf("%lld\n",ans[i]);
}

详情