Educational Codeforces Round 64 (Rated for Div. 2) (线段树二分)

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

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

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

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

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

#include<bits/stdc++.h>

#define maxn 200005

#define mod 1000000007

using namespace std;

typedef long long ll;

struct sss

{

    int l,r;

    int val;

}tree[maxn*];

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)/;

    build(cnt*,l,mid);

    build(cnt*+,mid+,r);

    tree[cnt].val=max(tree[cnt*].val,tree[cnt*+].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)/;

    if(r<=mid)  return query(cnt*,l,r);

    else if(l>mid) return query(cnt*+,l,r);

    else{

        return max(query(cnt*,l,mid),query(cnt*+,mid+,r));

    } 

}

int dl(int x)

{

    int val=a[x];

    int l=;

    int r=x;

    while(r-l>){

        int mid=(l+r)/;

        int max_val=query(,mid,x); //如果满足这个区间的最大值是这个数就继续扩张

        if(max_val==val)

        {

            r=mid;

        }

        else{

            l=mid;

        }

    }

    int max_val=query(,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>){

        int mid=(l+r)/;

        int max_val=query(,x,mid);

        if(max_val==val)

        {

            l=mid;

        }

        else{

            r=mid;

        }

    }

    int max_val=query(,x,r);

    if(max_val==val) return r;

    else return l;

}

int main()

{

    cin>>n;

    for(int i=;i<=n;i++)

    {

       scanf("%d",&a[i]);

       pos[a[i]]=i;

    }

    build(,,n);

    int ans=;

    for(int i=;i<=n;i++){

        int l=dl(i);//找出左边界

        int r=dr(i);//找出右边界

        if(i-l<r-i){//枚举短的那一边

            for(int j=l;j<i;j++){

                int other=a[i]-a[j];

                if (other<=||other>n)continue;

                ans+=pos[other]>i&&pos[other]<=r;//确定令一边是否在这个区间里面

            }

        }

        else{

            for(int j=i+;j<=r;j++){

                int other=a[i]-a[j];

                if (other<=||other>n)continue;

                ans+=pos[other]<i&&pos[other]>=l;

            }

        }

    }

    printf("%d",ans);

}

巴特西

Educational Codeforces Round 64 (Rated for Div. 2) (线段树二分)

最新文章

热门文章