对最优解储存数组p的操作是区间修改单点查询，所以想用线段树，但是：TLE x8，WA x2。本人理解此算法理论复杂度$O(N(logN)^2)$。

#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define il inline
const long long out=1e18;
int a,b,c,d,e[200002],ful[200002];
long long pre[200002],dp[200002];
string in[200002];
struct node
{
	int left,right,num,lazy;
}str[800008];
il int lft(int x)
{
	return x<<1;
}
il int iht(int x)
{
	return x<<1|1;
}
il void pd(int x)
{
	if(str[x].lazy>0)
	{
		int lz=str[x].lazy;
		str[x].lazy=0;
		str[lft(x)].num=lz;
		str[lft(x)].lazy=lz;
		str[iht(x)].num=lz;
		str[iht(x)].lazy=lz;
	}
	return;
}
il long long got(int x,int y)
{
	long long rn=1,tc=abs(c-(pre[x]-pre[y]+(x-y-1))),al=d;//tc^d
	while(al>0)
	{
		if(al&1)
		{
			rn*=tc;
		}
		al>>=1;
		tc*=tc;
	}
	rn+=dp[y];
	return rn;
}
void makstr(int x,int lt,int rt)
{
	str[x].left=lt;
	str[x].right=rt;
	if(lt==rt)
	{
		return;
	}
	int me=(lt+rt)>>1;
	makstr(lft(x),lt,me);
	makstr(iht(x),me+1,rt);
	return;
}
void adstr(int x,int lt,int rt,int y)
{
	if(lt<=str[x].left&&str[x].right<=rt)
	{
		str[x].num=y;
		str[x].lazy=y;
		return;
	}
	pd(x);
	int me=(str[x].left+str[x].right)>>1;
	if(lt<=me)
	{
		adstr(lft(x),lt,rt,y);
	}
	if(rt>me)
	{
		adstr(iht(x),lt,rt,y);
	}
	return;
}
int foudstr(int x,int pl)
{
	if(str[x].left==str[x].right)
	{
		return str[x].num;
	}
	pd(x);
	int me=(str[x].left+str[x].right)>>1;
	if(pl<=me)
	{
		return foudstr(lft(x),pl);
	}
	else
	{
		return foudstr(iht(x),pl);
	}
}
il int twice(int x)
{
	int l,m=1,n=b;
	while(n-m>1)
	{
		l=(m+n)>>1;
		if(got(l,foudstr(1,l))<got(l,x))
		{
			m=l;
		}
		else
		{
			n=l;
		}
	}
	if(got(m,foudstr(1,m))>=got(m,x))
	{
		return m;
	}
	if(got(n,foudstr(1,n))>=got(n,x))
	{
		return n;
	}
	return n+1;
}
int main()
{
//	freopen("A.in","r",stdin);
	scanf("%d",&a);
	while(a--)
	{
		memset(dp,0x7f,sizeof(dp));
//		memset(str,0,sizeof(str));
		pre[0]=0;
		scanf("%d%d%d",&b,&c,&d);
		makstr(1,1,b);
		for(ri i=1;i<=b;i++)
		{
			cin>>in[i];
			e[i]=in[i].size();
			pre[i]=pre[i-1]+e[i];
		}
		dp[0]=0;
		for(ri i=1;i<=b;i++)
		{
			dp[i]=got(i,foudstr(1,i));
//			if(dp[i]<0||dp[i]>out)
//			{
//				dp[b]=dp[i];
//				break;
//			}
//			printf("i=%d  foud=%d\n",i,foudstr(1,i));
			int qwer=twice(i);
			if(qwer<=b)
			{
//				printf("i=%d  qwer=%d\n",i,qwer);
				adstr(1,qwer,b,i);
			}
		}
		if(dp[b]>out||dp[b]<0)
		{
			puts("Too hard to arrange");
			puts("--------------------");
		}
		else
		{
			printf("%lld\n",dp[b]);
			puts("--------------------");
		}
	}
	return 0;
}

希望可以知道自己错在了哪里。