括号序列肯定想到要转化成折线考虑，这个是经典操作就不解释了，想学的看 这里 有解释
（当然如果是比较短的括号序列求子合法序列可以用栈配合 dp 算，比如某道使我提前退役的题目）
这一题因为序列是压缩的，没法用一般的 dp 算
对于折线下降的某个位置，要算左边包含同高度的上升段数（且之间没有更低的折线段）
如图说明的一样：
注意到段数 $n<=1000$ ，所以容易想到可以对每一下降段作为右端点，枚举前面的所有上升段作为左端点然后计算
要注意一种情况的处理：
具体看代码吧，实现起来挺恶心的，记得$long$ $long$
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; const int N=2e5+7; 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<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } int n; ll r[N];//维护每一段的右端点 ll ans; ll cal(ll x,ll y,ll p,ll q)//求区间 [x,y] 和区间 [p,q] 的交集大小 { if(p>q||x>y) return 0; if(x>q||y<p||p>y||q<x) return 0; if(x<=p&&y<=q) return y-p+1; if(p<=x&&q<=y) return q-x+1; if(x>=p&&y<=q) return y-x+1; if(x<=p&&y>=q) return q-p+1; } int main() { n=read(); int c; for(int i=1;i<=n;i++) { c=read(); if(i&1) r[i]=r[i-1]+c; else r[i]=r[i-1]-c;//判断段是上升还是下降 if(i&1) continue;//只以下降段位右端点 ll x=r[i],y=r[i-1];//确定下降段的区间 ll p=r[i-2],q=r[i-1];//对左边第一个上升段特判，因为左边第一段的右端点和当前下降段左端点重合 ans+=cal(x,y,p,q)-1;//注意-1 for(int j=i-3;j>0;j-=2)//找更前面的上升段 { //p,q维护当前上升段的合法区间 if(r[j-1]>p) continue;//这个特判很关键,自己画图理解qwq q=min(q,p); p=min(p,r[j-1]);//这个p,q的更新可以参考我的图 ans+=cal(x,y,p,q);//累加答案 } } printf("%lld ",ans); return 0; }