提交时间:2024-03-31 09:49:57

运行 ID: 27828

#include<bits/stdc++.h> using namespace std; const int N = 1e6+10; int n,a[N],m,ANS; struct T{ int l; int r; int minn; int maxn; }t[N*4]; void pushup(int i){ t[i].minn=min(t[i*2].minn,t[i*2+1].minn); t[i].maxn=max(t[i*2].maxn,t[i*2+1].maxn); } void build(int i,int l,int r){ t[i].l=l; t[i].r=r; if(l==r){ t[i].maxn=a[l]; t[i].minn=a[l]; return; } int mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); pushup(i); } int query(int i,int l,int r){ if(t[i].l>=l&&t[i].r<=r){ return t[i].maxn; } int ans=0; if(t[i*2].r>=l){ ans=max(ans,query(i*2,l,r)); } if(t[i*2+1].l<=r){ ans=max(ans,query(i*2+1,l,r)); } return ans; } int query2(int i,int l,int r){ if(t[i].l>=l&&t[i].r<=r){ return t[i].minn; } int ans=1e9; if(t[i*2].r>=l){ ans=min(ans,query2(i*2,l,r)); } if(t[i*2+1].l<=r){ ans=min(ans,query2(i*2+1,l,r)); } return ans; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ int z=query(1,i,j)+query2(1,i,j); if(z==m){ ANS++; } } } cout<<ANS<<endl; return 0; }