题意
白兔有一个长度为?的字符串。
白云有?个询问，每个询问会询问一段区间的本质不同回文子串个数。
题解
挺好玩的题
先说一个暴力的做法，就是建立PAM
然后离线，rrr端点一个一个加，维护l的答案
然后每一次，就暴力找到以rrr结尾的所有回文串，再找到上一次出现的位置，这个可以在PAM的fail树上用线段树维护，然后用树状数组资瓷区间加即可
那么复杂度就是O(n2logn)O(n^2logn)O(n2logn)的
考虑优化，每一次加入所有字符串太慢了
有一个结论是
以rrr结尾的回文串，可以被分成logloglog段等差数列
具体思想来自：金策_字符串算法选讲
但是我个人感觉这题最主要的结论不是这个
我们可以用同样的思想
对于每一个回文串分组,也是按照2i2^i2i来分组
每一组里面，你会发现，他们的区间加可以合在一起，并成一段连续的区间
那么我们只需要暴力遍历每log组，每次修改就可以了
至于为什么可以合在一起，因为他们上一次出现的位置恰好就是同一组里面的上一个
因为他们的长度都不相差一倍
于是对于每一组，暴力做就OK了
于是复杂度就是的nlog2nnlog^2nnlog2n了
em…学习了2i2^i2i分组的思想以及PAM的姿势
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
const int N=300005;
const int M=1000005;
const int MOD=1e9+7;
int add (int x,int y) {
x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y) {
return (LL)x*y%MOD;}
int dec (int x,int y) {
x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
if (y==1) return x;int lalal=Pow(x,y>>1);lalal=mul(lalal,lalal);if (y&1) lalal=mul(lalal,x);return lalal;
}
int n,m;
char ss[N];
struct qq
{
int son[N][26];int fail[N];int len[N];int s[N],num,n,last;int d[N],f[N];void Init () {
num=1;fail[0]=1;len[1]=-1;len[0]=0;s[0]=-1;}int find (int x,int xx){
while (s[xx-len[x]-1]!=s[xx]) x=fail[x];return x;}void Ins (int x){
s[++n]=x;int now=find(last,n);//printf("YES:%d %d %d %d\n",now,x,s[n],n-len[now]-1);if (son[now][x]==0){
num++; fail[num]=son[find(fail[now],n)][x];son[now][x]=num;len[num]=len[now]+2;//printf("NO:%d %d\n",now,num);d[num]=len[num]-len[fail[num]];if (d[num]==d[fail[num]]) f[num]=f[fail[num]];else f[num]=num;}//printf("YES:%d\n",fail[num]);last=son[now][x];}vector<int> vec[N];void link (){
for (int u=0;u<=num;u++)if (u!=1)vec[fail[u]].push_back(u);}int L[N],R[N],id;void dfs (int x){
L[x]=++id;int siz=vec[x].size();for (int u=0;u<siz;u++) dfs(vec[x][u]);R[x]=id;}
}PAM;
struct qt
{
int l,r;int s1,s2;int mx;
}tr[N*2];int num;
void update (int now)
{
int s1=tr[now].s1,s2=tr[now].s2;tr[now].mx=max(tr[s1].mx,tr[s2].mx);
}
void bt (int l,int r)
{
int now=++num;tr[now].l=l;tr[now].r=r;if (l==r) return ;int mid=(l+r)>>1;tr[now].s1=num+1;bt(l,mid);tr[now].s2=num+1;bt(mid+1,r);update(now);
}
int query (int now,int l,int r)
{
if (tr[now].l==l&&tr[now].r==r) return tr[now].mx;int mid=(tr[now].l+tr[now].r)>>1;int s1=tr[now].s1,s2=tr[now].s2;if (r<=mid) return query(s1,l,r);else if (l>mid) return query(s2,l,r);else return max(query(s1,l,mid),query(s2,mid+1,r));
}
void change (int now,int x,int id)
{
if (tr[now].l==tr[now].r) {
tr[now].mx=id;return ;}int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (x<=mid) change(s1,x,id);else change(s2,x,id);update(now);
}
int f[N];
int lb (int x) {
return x&(-x);}
void modify (int x,int c) {
while (x<=n){
f[x]+=c;x+=lb(x);}}
int get (int x) {
int lalal=0;while (x>0){
lalal=lalal+f[x];x-=lb(x);}return lalal;}
vector<PI> Q[N];
int main()
{
PAM.Init();scanf("%d%d",&n,&m);scanf("%s",ss+1);for (int u=1;u<=n;u++) PAM.Ins(ss[u]-'a');/*for (int u=1;u<=PAM.num;u++)printf("%d %d\n",PAM.len[u],PAM.fail[u]);*/PAM.link();PAM.dfs(1);bt(1,PAM.id);for (int u=1;u<=m;u++){
int l,r;scanf("%d%d",&l,&r);Q[r].push_back({
u,l});}int now=1;int ans=0;for (int u=1;u<=n;u++){
now=PAM.son[PAM.find(now,u)][ss[u]-'a'];//printf("%d\n",now);for (int i=now;i!=0;i=PAM.fail[PAM.f[i]]){
int t=query(1,PAM.L[i],PAM.R[i]);modify(max(1,t-PAM.len[i]+2),1);modify(u-PAM.len[PAM.f[i]]+2,-1);}change(1,PAM.L[now],u);int siz=Q[u].size();for (int i=0;i<siz;i++) {
//printf("%d %d %d\n",Q[u][i].first,Q[u][i].second,get(Q[u][i].second));ans=add(ans,mul(get(Q[u][i].second),Q[u][i].first));}}printf("%d\n",ans);return 0;
}