萌新求助

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

struct Tree{
	int maxn,lazytag;
}tree[MAXN*4];
struct data{
	int num,id;
}a[MAXN];
int dp[MAXN],n;
void build(int id,int l,int r){
	tree[id].lazytag=0;
	if(l==r){
		tree[id].maxn=dp[l];
		return;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid),build(id*2+1,mid+1,r);
	tree[id].maxn=max(tree[id*2].maxn,tree[id*2+1].maxn);
	return;
}
void pushdown(int id){
	if(tree[id].lazytag==0)return;
	tree[id*2].lazytag+=tree[id].lazytag;
	tree[id*2+1].lazytag+=tree[id].lazytag;
	if(tree[id*2].maxn!=LLONG_MAX)tree[id*2].maxn+=tree[id].lazytag;
	if(tree[id*2+1].maxn!=LLONG_MAX)tree[id*2+1].maxn+=tree[id].lazytag;
	tree[id].lazytag=0; 
}
void add(int ql,int qr,int k,int id,int l,int r){
	if(l>qr||r<ql)return;
	if(l>=ql&&r<=qr){
		if(tree[id].maxn!=LLONG_MAX)tree[id].maxn+=k;
		tree[id].lazytag+=k;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(id);
	add(ql,qr,k,id*2,l,mid),add(ql,qr,k,id*2+1,mid+1,r);
	tree[id].maxn=max(tree[id*2].maxn,tree[id*2+1].maxn);
	return;
}
void update(int qx,int k,int id,int l,int r){
	if(l>qx||r<qx)return;
	if(l==qx&&r==qx){
		tree[id].maxn=k;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(id);
	update(qx,k,id*2,l,mid),update(qx,k,id*2+1,mid+1,r);
	tree[id].maxn=max(tree[id*2].maxn,tree[id*2+1].maxn);
	return;
}
inline bool cmp(data a,data b){
	if(a.num!=b.num)return a.num<b.num;
	return a.id<b.id;
}
inline bool cmp2(data a,data b){
	return a.id<b.id;
}
int T;
int new_id[MAXN],new_c[MAXN],cid[MAXN],sz,l[MAXN],r[MAXN];
signed main(){
	//freopen("color.in","r",stdin);
	//freopen("color.out","w",stdout);
	cin>>T;
	while(T--){
		n=read();
		n++;
		for(int i=2;i<=n;i++){
			a[i].num=read();
			a[i].id=i;
			dp[i]=LLONG_MIN;
		}
		dp[1]=0;	
		sort(a+2,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			if(a[i].id==2){
				dp[i]=0;
				break;
			}
		}
		build(1,1,n); 
		sz=1;
		l[1]=r[1]=1;
		new_id[1]=1;
		for(int i=2;i<=n;i++){
			new_id[a[i].id]=i;
			if(a[i].num!=a[i-1].num){
				sz++;
				l[sz]=i;
			}
			if(i==n||a[i].num!=a[i+1].num)r[sz]=i;
			new_c[a[i].id]=sz;
		}
		sort(a+2,a+n+1,cmp2); 
	//	for(int i=2;i<=n;i++)cout<<new_id[i]<<" ";
	//	cout<<endl;
		for(int i=3;i<=n;i++){
		//	print_tree();
		//	cout<<new_c[a[i].id]<<" "<<l[new_c[a[i].id]]<<" "<<r[new_c[a[i].id]]<<endl;
			add(l[new_c[a[i].id]],r[new_c[a[i].id]],a[i].num,1,1,n);
			int tmp=tree[1].maxn;
			add(l[new_c[a[i].id]],r[new_c[a[i].id]],-a[i].num,1,1,n);
			if(a[i].num==a[i-1].num)add(1,n,a[i].num,1,1,n); 
			update(new_id[a[i-1].id],tmp,1,1,n);
		//	cout<<tmp<<endl;
		}
		//print_tree();
		int ans=0;
		printf("%lld\n",tree[1].maxn);
	}
	return 0;
}