rt，线段树常数太大了

#include <bits/stdc++.h>
using namespace std;
struct node
{
	long long mx;
}tr[8200000];
long long n,trie[4200000][2],siz[4200000],dfc[4200000],f[30000][600],h[30000][600],w[30000][600],lc[8200000],rc[8200000],rt=0,rs=0,ct=0,cc=0,cs=0,ans=0;
const long long bas=1421;
char s[30000];
unordered_map<unsigned long long,long long>p;
long long insert(long long p,long long d)
{
	if(!trie[p][d])trie[p][d]=++ct;
	return trie[p][d];
}

void dfs(long long x)
{
	dfc[x]=++cc,siz[x]=1;
	for(long long i=0;i<=1;i++)
	    if(trie[x][i])
	       {
	       	dfs(trie[x][i]);
	       	siz[x]+=siz[trie[x][i]];
		   }
}

void pushup(long long x)
{
	tr[x].mx=max(tr[lc[x]].mx,tr[rc[x]].mx);
}

void build(long long &now,long long l,long long r)
{
	now=++cs;
	if(l==r)return;
	long long mid=(l+r)>>1;
	build(lc[now],l,mid),build(rc[now],mid+1,r);
}

void update(long long now,long long l,long long r,long long p,long long k)
{
	if(l==r)
	   {
	   	tr[now].mx=max(tr[now].mx,k);
	   	return;
	   }
	long long mid=(l+r)>>1;
	if(p<=mid)update(lc[now],l,mid,p,k);
	else update(rc[now],mid+1,r,p,k);
	pushup(now);
}

long long query(long long now,long long l,long long r,long long lx,long long rx)
{
	long long ans=0;
	if(l>=lx&&r<=rx)return tr[now].mx;
	long long mid=(l+r)>>1;
	if(lx<=mid)ans=max(ans,query(lc[now],l,mid,lx,rx));
	if(rx>=mid+1)ans=max(ans,query(rc[now],mid+1,r,lx,rx));
	return ans;
}

int main()
{
	scanf("%lld%s",&n,s+1);
	p[0]=rt;
	for(int i=1;i<=n;i++)
	    {
	    	unsigned long long has=0,po=1;
	    	for(int j=1;j<=sqrt(2*i);j++)
	    	    {
	    	    	has=has+po*(s[i-j+1]-'0'+1),po=po*bas;
	    	    	h[i][j]=has,p[has]=insert(p[h[i-1][j-1]],s[i]-'0');
				}
		}
	dfs(rt);
	build(rs,1,cc);
	for(int i=0;i<=n;i++)
	    {
	    for(int j=1;j<=sqrt(2*i);j++)update(rs,1,cc,dfc[p[h[i][j]]],f[i][j]);
	    for(int j=i+1;j<=n;j++)
			{
				if(j-i>sqrt(2*j))break;
				int x=j,l=j-i;
	    	    if(s[x]=='1'&&trie[p[h[x-1][l-1]]][0])f[x][l]=max(w[x-1][l-1],query(rs,1,cc,dfc[trie[p[h[x-1][l-1]]][0]],dfc[trie[p[h[x-1][l-1]]][0]]+siz[trie[p[h[x-1][l-1]]][0]]-1));
	    	    else f[x][l]=w[x-1][l-1];
	    	    w[x][l]=f[x][l],f[x][l]++;
	    	    w[x][l]=max(w[x][l],query(rs,1,cc,dfc[p[h[x][l]]],dfc[p[h[x][l]]]));
			}
		}
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=sqrt(2*i);j++)
	        ans=max(ans,f[i][j]);
	printf("%lld\n",ans);
	return 0;
}