C20220725T3 回文

给定字符串 \(s\) ，求 \(s_{l,r}\) 中回文串个数。多组询问， \(|s|\leq 5000\) , \(T\leq10^5\) 。

首先介绍 \(O(n\times T)\) 的离谱做法（竟然没卡掉），先跑 \(Manachar\) ，然后暴力查询 \([l,r]\) 的回文串数量，最后用一个数组记录下来（防1 5000数据）即可。

然后是正解，首先处理出 \(g[i][j]\) 表示 \(s_{i,j}\) 是否为回文串，然后推出 \(s_{i,j}\) 中回文串总个数 \(f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+g[i][j]\) ，最后处理一下边界。（还是只有错误复杂度的代码）。

#include<bits/stdc++.h>
using namespace std;
struct IO{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline IO & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
    inline void push(const char &c) {
    	putchar(c);
	}
	template <class T>
	inline void write(T x){
		if (x < 0) x = -x, push('-');
		static T sta[35];
		T top = 0;
		do {
			sta[top++] = x % 10, x /= 10;
		} while (x);
		while (top) push(sta[--top] + '0');
	}
	template <class T>
	inline void write(T x, char lastChar){
		write(x),push(lastChar);
	}
}io;

int t,slen;
int p[200005];
char s[100005];
char ss[200005];
pair<int,int> Q;
int anss[5005][5005];

int main(){
	scanf("%s",s+1);
	slen=strlen(s+1);
	ss[0]='!',ss[2*slen+1]='#',ss[2*slen+2]='?';
	for(int i=1;i<=slen;++i){
		ss[2*i-1]='#';
		ss[2*i]=s[i];
	}
	int mx=0,id=0;
	for(int i=1;i<=2*slen+1;++i){
		p[i]=((i>=mx)?0:min(p[2*id-i],mx-i));
		while(ss[i-p[i]]==ss[i+p[i]])
			++p[i];
		if(i+p[i]-1>mx){
			mx=i+p[i]-1;
			id=i;
		}
	}
	io>>t;
	while(t--){
		int ans=0;
		int l,r;
		io>>l>>r;
		if(anss[l][r]!=0){
			printf("%d\n",anss[l][r]);
			continue;
		}
		for(int i=2*l;i<=2*r;++i){
			ans+=(min(p[i],min(i-2*l+2,2*r-i+2))/2);
		}
		anss[l][r]=ans;
		printf("%d\n",ans);
	}
}