求时间复杂度证明

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,c[1000005],v[1000005],f[1000005],cw[1000005],q[1000005],x,y,ans=1e9;
int l[22][1000005],r[22][1000005],i,j;
int maxl(int x,int y)
{
	int k=__lg(y-x+1);
	return min(l[k][x],l[k][y-(1<<k)+1]);
}
int maxr(int x,int y)
{
	int k=__lg(y-x+1);
	return max(r[k][x],r[k][y-(1<<k)+1]);
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++) cin>>c[i];
	for(i=1;i<=n;i++) cin>>v[i];
	for(i=1;i<=n;i++) cin>>f[i];
	for(i=1;i<=n;i++)
	{
		if(cw[c[i]]==0) cw[c[i]]=i;
		l[0][i]=cw[c[i]];
		q[i]=1e9;
	}
	for(i=1;i<=n;i++) cw[i]=0;
	for(i=n;i>0;i--)
	{
		if(cw[c[i]]==0) cw[c[i]]=i;
		r[0][i]=cw[c[i]];
	}
	for(i=1;(1<<i)<=n;i++) for(j=1;j+(1<<i)-1<=n;j++)
	{
		l[i][j]=min(l[i-1][j],l[i-1][j+(1<<i-1)]);
		r[i][j]=max(r[i-1][j],r[i-1][j+(1<<i-1)]);
	}
	for(i=1;i<=n;i++)
	{
		x=i;
		while(maxr(i,x)!=x&&maxl(i,x)==i) x=maxr(i,x);
		if(maxl(i,x)==i) q[i]=x;
	}
	x=n+1;
	for(i=n;i>0;i--)
	{
		if(q[i]>=x) continue;
		x=q[i]; y=0;
		for(j=i;j<=q[i];j++) y=y+v[j]*f[j-i+1];
		ans=min(ans,y);
	}
	cout<<ans;
    return 0;
}