题目：http://codeforces.com/contest/1156/problem/E

题意：给你1-n  n个数，然后求有多少个区间[l,r] 满足    a[l]+a[r]=max([l,r])

思路：首先我们去枚举区间肯定不现实，我们只能取把能用的区间去用，我们可以想下每个数当最大值的时候所做的贡献

我们既然要保证这个数为区间里的最大值，我们就要从两边扩展，找到左右边界能扩展在哪里，这里你直接去枚举肯定不行

这里我们使用了线段树二分去枚举左右区间最远能走到哪里，然后很暴力的去枚举短的那一边找出右边是否有满足条件的边界

#include
     
      #define maxn 200005#define mod 1000000007using namespace std;typedef long long ll;struct sss{    int l,r;    int val;}tree[maxn*4];int n;int a[maxn];int pos[maxn];void build(int cnt,int l,int r){    if(l==r){        tree[cnt].l=l;        tree[cnt].r=r;        tree[cnt].val=a[l];        return;    }    tree[cnt].l=l;    tree[cnt].r=r;    int mid=(l+r)/2;     build(cnt*2,l,mid);    build(cnt*2+1,mid+1,r);    tree[cnt].val=max(tree[cnt*2].val,tree[cnt*2+1].val); } int query(int cnt,int l,int r){    if(l<=tree[cnt].l&&r>=tree[cnt].r) return tree[cnt].val;    int mid=(tree[cnt].l+tree[cnt].r)/2;    if(r<=mid)  return query(cnt*2,l,r);    else if(l>mid) return query(cnt*2+1,l,r);    else{        return max(query(cnt*2,l,mid),query(cnt*2+1,mid+1,r));    }     }int dl(int x){    int val=a[x];    int l=1;    int r=x;    while(r-l>1){        int mid=(l+r)/2;        int max_val=query(1,mid,x); //如果满足这个区间的最大值是这个数就继续扩张        if(max_val==val)        {            r=mid;        }        else{            l=mid;        }    }    int max_val=query(1,l,x);    if(max_val==val) return l;    else return r; }int dr(int x){    int val=a[x];    int l=x;    int r=n;    while(r-l>1){        int mid=(l+r)/2;        int max_val=query(1,x,mid);         if(max_val==val)        {            l=mid;        }        else{            r=mid;        }    }    int max_val=query(1,x,r);     if(max_val==val) return r;    else return l;}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {       scanf("%d",&a[i]);        pos[a[i]]=i;    }    build(1,1,n);    int ans=0;    for(int i=1;i<=n;i++){        int l=dl(i);//找出左边界        int r=dr(i);//找出右边界        if(i-l
      
       n)continue;                ans+=pos[other]>i&&pos[other]<=r;//确定令一边是否在这个区间里面            }        }        else{            for(int j=i+1;j<=r;j++){                int other=a[i]-a[j];                if (other<=0||other>n)continue;                ans+=pos[other]
       
        =l;            }        }    }     printf("%d",ans);}