85分求助

#include<iostream>
#include<algorithm>
#include<stdio.h> 
using namespace std;

int T;
int n;
int a[538];
int xor_[538][538];//每一个区间的值
struct g{
	int l,r;
}g1[538][538];//g1[l][k] 左端点大于等于 l，权值为 k，求最小右端点（必须是合法区间） 
struct h{
	int l1,r1;
	int l2,r2;
}h1[538][538];//h1[l][k] 左端点为 l， [l,a]、[b,c]异或值为k 且两端区间合法
struct f{
	int l1,r1;
	int l2,r2;
	int l3,r3;
}dp[538][538];
bool rev[538][538];
int p[538];
struct ans{
	int l1,r1;
	int l2,r2;
	int l3,r3;
}ans1[538];
int ptr=0;
void init(){
	ptr=0;
	for(int i=0;i<=530;i++){
		p[i]=i;
		for(int j=0;j<=530;j++){
			g1[i][j]=(g){-1,-1};
			h1[i][j]=(h){-1,-1,-1,-1};	
			dp[i][j]=(f){-1,-1,-1,-1,-1,-1}; 
			rev[i][j]=false;
		}
	}
} 
inline void dfs(int l,int r){
//	cout<<l<<' '<<r<<endl;
	if(l==r)	return;
	int l1=dp[l][r].l1;
	int l2=dp[l][r].l2;
	int l3=dp[l][r].l3;
	int r1=dp[l][r].r1;
	int r2=dp[l][r].r2;
	int r3=dp[l][r].r3;
	dfs(l1,r1);
	dfs(l2,r2);
	dfs(l3,r3);
	ans1[++ptr]=(ans){l1,r1,l2,r2,l3,r3};
}
void solve(){
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		xor_[i][i]=a[i];
		rev[i][i]=true;
		int xor1=xor_[i][i];
		g1[i][xor1]=(g){i,i};
//		cout<<i<<' '<<xor1<<' '<<g1[i][xor1].l<<' '<<g1[i][xor1].r<<endl;
	}
//	cout<<g1[5][5].r<<endl;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			xor_[i][j]=(xor_[i][j-1]^a[j]);
//			cout<<i<<' '<<j<<' '<<xor_[i][j]<<endl;
		} 
//		cout<<endl;
	}
	for(register int l=n;l>=1;l--){
		for(int xor6=0;xor6<=530;xor6++){
			if((g1[l][xor6].l==-1&&g1[l+1][xor6].l!=-1)||(g1[l][xor6].r>g1[l+1][xor6].r&&g1[l+1][xor6].r!=-1)){
				g1[l][xor6].l=g1[l+1][xor6].l;
				g1[l][xor6].r=g1[l+1][xor6].r;
//				cout<<l<<' '<<xor6<<' '<<g1[l][xor6].l<<' '<<g1[l][xor6].r<<endl;
			}
		}
		for(register int r=l;r<=n;r++){
			int xor4=xor_[l][r];
			for(register int k=l+1;k<=r;k++){
				int xor3=xor_[k+1][r];//第三个区间的异或和 
				int l1_=h1[l][xor3].l1;
				int l2_=h1[l][xor3].l2;
				int r1_=h1[l][xor3].r1;
				int r2_=h1[l][xor3].r2;
				int l3_=k+1;
				int r3_=r;
				if(r2_!=-1&&r2_<=k&&rev[l3_][r3_]==true&&rev[l1_][r1_]&&rev[l2_][r2_]){
					rev[l][r]=true;
					dp[l][r]=(f){l1_,r1_,l2_,r2_,l3_,r3_};
//					cout<<"a "<<l1_<<' '<<r1_<<' '<<l2_<<' '<<r2_<<' '<<l3_<<" "<<r3_<<endl;
					if(g1[l][xor4].l==-1||g1[l][xor4].r>r){
						g1[l][xor4]=(g){l,r};
//						cout<<"g1"<<' '<<l<<' '<<xor4<<' '<<l<<' '<<r<<endl;
					}
				}
//				if(rev[l][r])	break; 
			}
			if(rev[l][r]==true){
				for(int xor5=0;xor5<=515;xor5++){
					int l1=g1[r+1][xor5].l;
					int r1=g1[r+1][xor5].r;
					int k=(xor4^xor5);
					if((h1[l][k].l1==-1||h1[l][k].r2>r1)&&l1!=-1){
						h1[l][k]=(h){l,r,l1,r1};
//						cout<<"h1"<<' '<<l<<' '<<k<<' '<<l<<' '<<r<<' '<<l1<<' '<<r1<<endl;
					}
				}
			}
		}
		for(int xor6=0;xor6<=515;xor6++){
			if((g1[l][xor6].l==-1&&g1[l+1][xor6].l!=-1)||(g1[l][xor6].r>g1[l+1][xor6].r&&g1[l+1][xor6].r!=-1)){
				g1[l][xor6].l=g1[l+1][xor6].l;
				g1[l][xor6].r=g1[l+1][xor6].r;
//				cout<<l<<' '<<xor6<<' '<<g1[l][xor6].l<<' '<<g1[l][xor6].r<<endl;
			}
		}
	}
	if(!rev[1][n]){
		puts("Shuiniao");
	}
	else{
		puts("Huoyu");
		if(n>1)	dfs(1,n);
		cout<<ptr<<endl;
		for(int i=1;i<=ptr;i++){
			int l1=ans1[i].l1;
			int l2=ans1[i].l2;
			int l3=ans1[i].l3;
			int r1=ans1[i].r1;
			int r2=ans1[i].r2;
			int r3=ans1[i].r3;
			cout<<p[l1]<<' '<<p[l2]<<' '<<p[l3]<<endl; 
//			cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<' '<<l3<<' '<<r3<<endl;
			for(int j=l1;j<=r3;j++){
				p[j]=p[l1];
			}
			for(int j=r3+1;j<=n;j++){
				p[j]=p[j-1]+1;
			}
//			for(int j=1;j<=n;j++){
//				cout<<p[j]<<' ';
//			}
//			cout<<endl<<endl;
		}
	}
	return;
}
int main(){
//	freopen("merge.in","r",stdin);
//	freopen("merge.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		
		solve();
	}	
	return 0;
}