Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

水水水水水水水水水水

Posted by ty21 at 2018-08-03 18:03:11 on Problem 3264
//线段树大大大大水题

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn =5e4;
const int inf =1e7;

struct
{
    int l,r;
    int ma,mi;
}tree[maxn*4+10];

void update(int x)
{
    if(tree[x].l==tree[x].r)
        return;
    tree[x].ma=max(tree[x*2].ma,tree[x*2+1].ma);
    tree[x].mi=min(tree[x*2].mi,tree[x*2+1].mi);
}

void build(int x,int l,int r)
{
    tree[x].l=l;
    tree[x].r=r;
    if(l==r)
    {
        int w;
        scanf("%d",&w);
        tree[x].ma=tree[x].mi=w;
    }
    else
    {
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        update(x);
    }
}

int getmax(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r)
        return tree[x].ma;
    else
    {
        int res=0;
        int mid=(tree[x].l+tree[x].r)/2;
        if(l<=mid)
            res=max(res,getmax(x*2,l,r));
        if(r>mid)
            res=max(res,getmax(x*2+1,l,r));
        return res;
    }
}

int getmin(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r)
        return tree[x].mi;
    else
    {
        int res=inf;
        int mid=(tree[x].l+tree[x].r)/2;
        if(l<=mid)
            res=min(res,getmin(x*2,l,r));
        if(r>mid)
            res=min(res,getmin(x*2+1,l,r));
        return res;
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int ll,rr;
        scanf("%d%d",&ll,&rr);
        //printf("%d %d\n",getmax(1,ll,rr),getmin(1,ll,rr));
        printf("%d\n",getmax(1,ll,rr)-getmin(1,ll,rr));
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator