题意
给一个长度为 \(n\) 的 \(01\) 串串，定义 \(\text{date}(l,r)\) 为起始位置在 \([L,R]\) 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。
给 \(q\) 次询问 \((L,R)\)，表示求 \(ans=\sum_{L\le i<R}\text{data(i,R)}\)。
思路
先考虑对于制定的 \(L,R\)，如何求 \(\text{data}(L,R)\)。
由于字符串随机生成，所以两个相同的字串不会太长。设 \(max\_len=32\)，即最长的公共前缀不会超过 \(max\_len\)
对于每个位置 \(i\)，求出祂向后 \(j(1\le j\le max\_len)\) 个字符的哈希值，记位 \(h_{i,j}\)，求出最小的 \(nt_{i,j}\)，满足 \(h_{nt_{i,j},j}=h_{i,j},nt_{i,j}>i\)，如果没有，设为 \(n+1\)。
在求 \(\text{date}(L,R)\) 时，找到最大的长度 \(l\)，满足 \(\min_{L\le i\le R}(nt_{i,l})<=R\)，那么 \(\text{data}(L,R)=l\)。
对于一次询问 \((L,R)\)，从小到大枚举一个长度 \(l\)，求出最大的 \(i\)，满足 \(nt_{i,l}\le R\)，令 \(i'\) 是最大的满足 \(nt_{i',l-1}\le R\) 的位置，那么所有 \(j\in(i,i']\) 的贡献都是 \(l-1\)。
这个东西可以用线段树做。
时间复杂度 \(\mathcal O(n\log^2n)\)
代码
存哈希值是用 map 被卡常了，换了 unordered_map。
拿下最劣解。
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define ull unsigned long long
const int maxn=100010,maxlen=50;
int n,q,nt[maxn][maxlen];
string s;
class Hash{
private:ull h[maxn],mi[maxn];const ull base=131;
public:void build(string s){mi[0]=1;for(int i=1;i<=100000;i++) mi[i]=mi[i-1]*base;for(int i=0;i<s.size();i++) h[i+1]=h[i]*base+s[i]-'0';}ull query(int l,int r){return h[r]-h[l-1]*mi[r-l+1];}
}h;
unordered_map<ull,int>mp[maxlen];
class Segment_Tree{
private:int t[maxn*4];void insert(int u,int l,int r,int d,int z){if(l>d||r<d) return ;if(l==r){t[u]=z;return ;}int mid=l+r>>1;if(mid>=d) insert(u<<1,l,mid,d,z);else insert(u<<1|1,mid+1,r,d,z);t[u]=min(t[u<<1],t[u<<1|1]);}int query(int u,int l,int r,int ll,int rr,int x){if(l>rr||r<ll) return -1;if(l==r) return l;int mid=l+r>>1;if(t[u<<1|1]<=x) return query(u<<1|1,mid+1,r,ll,rr,x);if(t[u<<1]<=x) return query(u<<1,l,mid,ll,rr,x);return -1;}
public:void init(){memset(t,0x3f,sizeof(t));}void insert(int d,int z){insert(1,1,n,d,z);}int query(int l,int r,int x){return query(1,1,n,l,r,x);}
}t[maxlen];
signed main(){for(int i=1;i<=32;i++) t[i].init();read(n,q,s);h.build(s);for(int i=n;i>=1;i--){nt[i][0]=i;for(int j=1;j<=32;j++) nt[i][j]=n+1;for(int j=1;j<=32;j++){if(i+j-1>n) break;ull ha=h.query(i,i+j-1);if(mp[j][ha]) nt[i][j]=mp[j][ha];mp[j][ha]=i;}}for(int i=1;i<=n;i++) for(int j=1;j<=32;j++) t[j].insert(i,nt[i][j]);for(int i=1;i<=q;i++){int L,R;read(L,R);int ans=0;for(int l=1;l<=32;l++){int w=t[l].query(L,R-1,R);if(w!=-1) ans+=w-L+1;}write(ans),write("\n");}return 0;
}