关于四边形不等式DP

#include<bits/stdc++.h>
#define ll long long
#define too 1e18
using namespace std;
const int N=1e5+10;
struct Node{
	int l,r,p;
}q[10*N];
int T,n,l,p,h,t,d[N];
ll f[N],s[N];
string a[N];
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
ll val(int x,int y){
	if(y<x) swap(x,y);
	return qpow(abs(s[y]-s[x]+y-x-1-l),p);
}
bool check(int x){
	return f[q[t].p]+val(q[t].p,q[t].r)<f[x]+val(x,q[t].r);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&l,&p);
		for(int i=1;i<=n;i++){
			cin>>a[i];
			s[i]=s[i-1]+a[i].size();
		}
		h=1;t=1;
		q[1].l=1;
		q[1].r=n;
		q[1].p=0;
		bool flag=0;
		for(int i=1;i<=n;i++){
			while(h<t&&q[h].r<=i-1) h++;
			q[h].l=i;
			f[i]=f[q[h].p]+val(i,q[h].p);
			d[i]=q[h].p;
			if(f[i]>too){
				printf("Too hard to arrange\n--------------------\n");
				flag=1;
				break; 
			}
			int pos=q[t].l;
			while(h<t&&(f[i]+val(i,q[t].l)<=f[q[t].p]+val(q[t].p,q[t].l))){
				pos=q[t].l;
				t--;
			}
			if(f[q[t].p]+val(q[t].p,q[t].r)<=f[i]+val(i,q[t].r)){
				q[t].r=pos-1;
				++t;
				q[t].l=pos;
				q[t].r=n;
				q[t].p=i;
			}
			else{
				int ls=q[t].l,rs=q[t].r;
				while(rs-ls>1){
					int mid=(ls+rs)/2;
					if(check(mid)) ls=mid;
					else rs=mid;
				}
				q[t].r=ls-1;
				++t;
				q[t].l=ls;
				q[t].r=n;
				q[t].p=i;
			}
			/*cout<<h<<" "<<t;
			for(int i=h;i<=t;i++) cout<<"**"<<q[i].l<<" "<<q[i].r<<" "<<q[i].p<<"**"<<endl;
			cout<<"OK"<<endl;*/
		}
		if(flag) continue;
		printf("%lld\n",f[n]);
		cout<<a[1];
		for(int i=2;i<=n;i++){
			//cout<<"**"<<d[i]<<"**";
			if(d[i]!=d[i-1]) cout<<endl<<a[i];
			else cout<<" "<<a[i];
		}
		printf("\n--------------------\n");
	}
	return 0;
}