//给定一数列和$x$，求有多少个区间的最大值与最小值之和$=x$ //max\{a_i\}+min\{a_i\}=x\\ //max\{a_i\}=x-min\{a_i\}=x+max\{-a_i\}=max\{x-a_i\} //即找到$max\{a_i\}$与$max\{x-a_i\}$相等的区间；枚举右端点，将当前位置对应的两种值标成不同颜色放到同一个单调栈里面维护到某个左端点的最大值，如果当前值比原栈顶大，说明原来那一套max值一定不能再贡献，直接踢掉，如果值相同，弹掉那些和当前加入值颜色也一样的点，因为可能和颜色不一样的点组成合法区间；单调栈中每两个相邻的且值相同颜色不同的点都能和右端点构成合法区间，只要左端点位于较早点的左边且max值不变，所以可以在每次加入/删除栈顶的时候更新整个栈对新进点的贡献 #include <iostream> #include <cstdio> #define int long long using namespace std; const int MAX=1e6+5; struct node{ int value,pos,color; //0 ai 1 x-ai }sta[MAX<<1]; int tp; int a[MAX]; int n,x,sum,ans; signed main(){ scanf("%lld %lld",&n,&x); sta[0].color=-1; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); // while(tp>0 && sta[tp].value<a[i]){ if(tp>1 && sta[tp].value==sta[tp-1].value)sum-=(sta[tp-1].pos-sta[tp-2].pos); tp--; } while(tp>0 && sta[tp].value==a[i] && sta[tp].color==0){ if(tp>1 && sta[tp].value==sta[tp-1].value)sum-=(sta[tp-1].pos-sta[tp-2].pos); //sta[tp-1]=sta[tp]; tp--; } sta[++tp]=node{a[i],i,0}; if(tp>1 && sta[tp].value==sta[tp-1].value)sum+=(sta[tp-1].pos-sta[tp-2].pos); //且颜色不同 // while(tp>0 && sta[tp].value<x-a[i]){ if(tp>1 && sta[tp].value==sta[tp-1].value)sum-=(sta[tp-1].pos-sta[tp-2].pos); tp--; } while(tp>0 && sta[tp].value==x-a[i] && sta[tp].color==1){ if(tp>1 && sta[tp].value==sta[tp-1].value)sum-=(sta[tp-1].pos-sta[tp-2].pos); //sta[tp-1]=sta[tp]; tp--; } sta[++tp]=node{x-a[i],i,1}; if(tp>1 && sta[tp].value==sta[tp-1].value)sum+=(sta[tp-1].pos-sta[tp-2].pos); ans+=sum; //if(i==4){ for(int j=1;j<=tp;j++){ printf("%lld %lld %lld\n",sta[j].value,sta[j].pos,sta[j].color); } cout<<sum<<endl; //} } printf("%lld",ans); return 0; }