NYOJ-568/1012//UVA-12299RMQ with Shifts，线段树单点更新+区间查询

RMQ with Shifts

时间限制：1000 ms | 内存限制：65535 KB

难度：3

-> Link1 <-

->
Link2 <-

以上两题题意是一样的，只不过数据范围有所改动，代码改一下数组大小直接水过；

思路：典型的线段数单点更新+区间查询，只不过题目改动了一下，没有直接给出更新数据和查询区间，而是用字符串输入，所以只能将数据提取出来再进行操作，这道题线段数能做那么用RMQ肯定也能做，而且可能还更简洁；过的人并不多，大神们快点去A了它吧；

#include<bits/stdc++.h>

using namespace std;

const int N=100000+10;

struct node

{

    int l,r,mi;

} a[N<<2];

int s[N],n,m;

void build(int l,int r,int k)

{

    a[k].l=l,a[k].r=r,a[k].mi=0;

    if(l==r)

    {

        a[k].mi=s[l];

        return ;

    }

    int mid=(l+r)/2;

    build(l,mid,2*k);

    build(mid+1,r,2*k+1);

    a[k].mi=min(a[k*2].mi,a[k*2+1].mi);

}

void update(int x,int n,int k)

{

    if(a[k].l==a[k].r&&a[k].l==x)

    {

        a[k].mi=n;

        return ;

    }

    int mid=(a[k].l+a[k].r)/2;

    if(x<=mid) update(x,n,2*k);

    else update(x,n,2*k+1);

    a[k].mi=min(a[k*2].mi,a[k*2+1].mi);

}

int query(int l,int r,int k)

{

    if(a[k].l==l&&a[k].r==r)

        return a[k].mi;

    int mid=(a[k].l+a[k].r)/2;

    a[k].mi=min(a[k*2].mi,a[k*2+1].mi);

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

    else if(l>mid) return query(l,r,2*k+1);

    return min(query(l,mid,2*k),query(mid+1,r,2*k+1));

}

int main()

{

    int i;

    scanf("%d%d",&n,&m);

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

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

    build(1,n,1);

    char sb[120];

    while(m--)

    {

        scanf("%s",sb);

        int len=strlen(sb);

        if(sb[0]=='q')

        {

            int x=0,y=0;

            for(i=6; sb[i]!=','; i++)

                x=x*10+(sb[i]-'0');//区间左端点；

            for(i++; sb[i]!=')'; i++)

                y=y*10+(sb[i]-'0');//右端点；

            printf("%d\n",query(x,y,1));

        }

        else

        {

            int x=0,y=0,k=6,pos=0;

            for(i=k; sb[i]!=','; i++)

                x=x*10+(sb[i]-'0');//第一个x；

                pos=s[x];

            while(k!=len-1)

            {

                for(i++; sb[i]>='0'&&sb[i]<='9'; i++)//跳出的条件是sb[i]要么是','要么是')';

                    y=y*10+(sb[i]-'0');

                update(x,s[y],1);

                s[x]=s[y];//注意这里也要进行更新；

                k=i;

                x=y,y=0;

            }

            update(x,pos,1);

            s[x]=pos;//小细节，注意；

        }

    }

    return 0;

}

RMQ还是停留在模板水平，如果有更多应用的话还会在学的；

巴特西

NYOJ-568/1012//UVA-12299RMQ with Shifts，线段树单点更新+区间查询

RMQ with Shifts

最新文章

热门文章