求助

1
15
5 3 7 2 4 13 11 6 5 5 3 5 12 8 13

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=2e5+5;
int dp[N],n,a[N],t,ans,op,u,len=0,b[N];

namespace WeightLineTree{
	#define lt (cur<<1)
	#define rt ((cur<<1)|1)
	#define mid ((R+L)>>1)
	const int M=N<<2;
	int maxn[M],lz[M],Pos[M];
	void sq(int cur,int w){
		maxn[cur]+=w;
		lz[cur]+=w;
	}
	void down(int cur){
		sq(lt,lz[cur]);
		sq(rt,lz[cur]);
		lz[cur]=0;
	}
	void up(int cur){
		if(maxn[lt]>=maxn[rt])
			Pos[cur]=Pos[lt];
		else 	
			Pos[cur]=Pos[rt];
		maxn[cur]=max(maxn[lt],maxn[rt]);
	}
	void add(int cur,int l,int r,int L,int R,int w){
		if(l<=L&&R<=r){
			sq(cur,w);
		}else if(!(l>R||L>r)){
			down(cur);
			add(lt,l,r,L,mid,w);
			add(rt,l,r,mid+1,R,w);
			up(cur);
		}
	}
	void gai_max(int cur,int L,int R,int x,int w){
		if(L==R){
			maxn[cur]=max(maxn[cur],w);
			return ;
		}
		if(x<=mid)
			gai_max(lt,L,mid,x,w);
		else 
			gai_max(rt,mid+1,R,x,w);
		up(cur);
	}
	void build(int cur,int L,int R){
		lz[cur]=0;
		if(L==R){
			Pos[cur]=L;
			maxn[cur]=(b[L]!=0)*-1e9;
			return ;
		}
		build(lt,L,mid);
		build(rt,mid+1,R);
		up(cur);
	}
	int Q(int x){
		int L=0,R=len+1;
		while(L+1<R){
			if(b[mid]<=x)
				L=mid;
			else
				R=mid;
		}
		return L;
	}
}
using namespace WeightLineTree;
/*
dp[j]定义为与i最近j不同
*/
void work(){
	len=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	b[n+1]=0;
	sort(b+1,b+2+n);
	for(int i=1;i<=n+1;i++){
		if(b[i]!=b[i+1])
			b[++len]=b[i];
	}
	build(1,1,len);
	for(int i=2;i<=n;i++){
		u=Q(a[i]);
		add(1,u,u,1,len,a[i]);
		dp[i-1]=maxn[1];
		cout<<b[Pos[1]]<<' '<<a[i]<<' '<<dp[i-1]<<'\n';
		add(1,u,u,1,len,-a[i]);			
		add(1,1,len,1,len,(a[i]==a[i-1])*a[i]);
		gai_max(1,1,len,Q(a[i-1]),dp[i-1]);
	}		
	cout<<maxn[1]<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		work();
	}
	return 0;
}