如题,开的是动态数组,删了TLE,不删MLE。。。。咋办啊
#include<bits/stdc++.h>
using namespace std;
const int mod=(1<<30);
int top,n,now,type,x,y,z,m,h,t,p[100005],l[100005],r[100005],pre[4000005];
__int128 s[40000005];
char out[50];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>type;int *q=new int[n+2];
if(type){
int *b=new int[n+2];
cin>>x>>y>>z>>b[1]>>b[2]>>m;
for(register int i=1;i<=m;i++)cin>>p[i]>>l[i]>>r[i];
for(register int i=3;i<=n;i++)b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
for(register int i=1;i<=m;i++)
for(register int j=p[i-1]+1;j<=p[i];j++)s[j]=s[j-1]+(b[j]%(r[i]-l[i]+1))+l[i];
delete[] b;
}else{
int *a=new int[n+2];
for(register int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}
delete[] a;
}
for(register int i=1;i<=n;i++){
while(h<t&&(s[q[h+1]]<<1)-s[pre[q[h+1]]]<=s[i])h++;
pre[i]=q[h];
while(h<t&&(s[q[t]]<<1)-s[pre[q[t]]]>=s[i]-s[pre[i]]+s[i])t--;
q[++t]=i;
}
// delete[] q;
now=n;
__int128 ans=0,tmp;
while(now)tmp=s[now]-s[pre[now]],ans+=tmp*tmp,now=pre[now];
while(ans)out[++top]=ans%10+'0',ans/=10;
while(top)cout<<out[top--];
return 0;
}