两个解法：
解法1：提前预处理，用空间换时间
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);if(!in.hasNextInt())return;intn=in.nextInt();long[]reds=newlong[n];// 元素可能很大，用 long 防止溢出longtotalSum=0;for(inti=0;i<n;i++){reds[i]=in.nextLong();totalSum+=reds[i];}// 1. 不能被3整除，绝对无法平分if(totalSum%3!=0){System.out.println(0);return;}longtarget=totalSum/3;// 2. 预处理 nextPos 数组：nextPos[i] 表示从索引 i 开始，右侧第一个正数的位置int[]nextPos=newint[n];intlastPositiveIndex=n;// 用 n 代表无穷大（没找到）for(inti=n-1;i>=0;i--){if(reds[i]>0){lastPositiveIndex=i;}nextPos[i]=lastPositiveIndex;}// 3. 预处理 suffixCount 数组：统计合法的第三段数量// suffixCount[j] 表示以 j 作为第三段的起点，有多少种合法方案int[]suffixCount=newint[n+1];longcurrentSuffixSum=0;booleansuffixHasPos=false;// 从右向左遍历，j 最小到 2（给第一段和第二段各留至少1个位置）for(intj=n-1;j>=2;j--){currentSuffixSum+=reds[j];if(reds[j]>0)suffixHasPos=true;// 继承后面的数量suffixCount[j]=suffixCount[j+1];// 如果当前后缀满足条件（和为 target 且有正数），数量 +1if(currentSuffixSum==target&&suffixHasPos){suffixCount[j]++;}}// 4. 从左向右寻找第一段，并累加答案longans=0;longcurrentPrefixSum=0;booleanprefixHasPos=false;// 第一段终点 i 最大到 n-3for(inti=0;i<=n-3;i++){currentPrefixSum+=reds[i];if(reds[i]>0)prefixHasPos=true;// 如果找到合法的第一段if(currentPrefixSum==target&&prefixHasPos){// 中间段从 i+1 开始，找它里面的第一个正数位置 pintp=nextPos[i+1];// 如果中间段能找到正数，且不是数组最后一个元素（要给第三段留位置）if(p<n-1){// 第三段的起点 j 必须在 p 之后 (即 j >= p + 1)// 这样才能保证索引为 p 的那个正数，稳稳地落在了中间段里！ans+=suffixCount[p+1];}}}System.out.println(ans);}}
解法2：暴力验证法
importjava.util.*;classSolution{publicvoidredCutToTreeParts(int[]reds,intnum){if(reds==null||num<3){System.out.print(0);return;}longsum=0;for(intred:reds){sum+=red;}if(sum%3!=0){System.out.print(0);return;}longtarget=sum/3;// 前缀和与前缀正数计数long[]prefixSum=newlong[num+1];int[]prefixPositiveCount=newint[num+1];for(inti=0;i<num;i++){prefixSum[i+1]=prefixSum[i]+reds[i];prefixPositiveCount[i+1]=prefixPositiveCount[i]+(reds[i]>0?1:0);}// 获取包含正数的有效左切点ArrayList<int[]>leftCuts=newArrayList<>();// [index, positive_count_in_segment]for(inti=0;i<num-2;i++){if(prefixSum[i+1]==target){intposCount=prefixPositiveCount[i+1];if((target==0&&posCount>0)||(target!=0&&posCount>0)){leftCuts.add(newint[]{i,posCount});}}}// 获取包含正数的有效右切点ArrayList<int[]>rightCuts=newArrayList<>();// [index, positive_count_from_right]for(inti=num-1;i>1;i--){if(prefixSum[num]-prefixSum[i]==target){intposCount=prefixPositiveCount[num]-prefixPositiveCount[i];if((target==0&&posCount>0)||(target!=0&&posCount>0)){rightCuts.add(newint[]{i,posCount});}}}Collections.reverse(rightCuts);longcount=0;for(int[]leftData:leftCuts){intleftId=leftData[0];intleftPosCount=leftData[1];// 二分查找满足 rightId > leftId + 1 的起始位置intl_idx=0,r_idx=rightCuts.size();while(l_idx<r_idx){intmid=(l_idx+r_idx)/2;if(rightCuts.get(mid)[0]>leftId+1){r_idx=mid;}else{l_idx=mid+1;}}// 检查从 l_idx 开始的每个 rightId，验证中间段是否包含正数for(intk=l_idx;k<rightCuts.size();k++){intrightId=rightCuts.get(k)[0];// 中间段 [leftId + 1, rightId - 1] 的正数计数intmiddlePosCount=prefixPositiveCount[rightId]-prefixPositiveCount[leftId+1];if(middlePosCount>0){count++;}}}System.out.print(count);}}publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt();int[]reds=newint[n];for(inti=0;i<n;i++){reds[i]=in.nextInt();}Solutionsolution=newSolution();solution.redCutToTreeParts(reds,n);in.close();}}
