当前位置:编程学习 > C/C++ >>

wustoj 1260 RMQ with Shifts

线段树单点更新,注意cin会超时,记得每次update后还要更新相应数组a的值。
 
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<vector>  
using namespace std;  
#define MAXN 100010  
struct node  
{  
    int l,r,mid;  
    int sum;  
}tree[MAXN*4];  
int ans;  
int top;  
int a[MAXN];  
int num[MAXN];  
void build(int l,int r,int id)  
{  
    tree[id].l=l;  
    tree[id].r=r;  
    tree[id].mid=(l+r)>>1;  
    if(l==r)  
    {  
        scanf("%d",&tree[id].sum);  
        a[top++]=tree[id].sum;  
        return;  
    }  
    build(l,tree[id].mid,id<<1);  
    build(tree[id].mid+1,r,id<<1|1);  
    tree[id].sum=min(tree[id<<1].sum,tree[id<<1|1].sum);  
}  
void query(int l,int r,int id)  
{  
    if(tree[id].l==l&&tree[id].r==r)  
    {  
        ans=min(ans,tree[id].sum);  
        return;  
    }  
    if(r<=tree[id].mid) query(l,r,id<<1);  
    else if(l>tree[id].mid) query(l,r,id<<1|1);  
    else  
    {  
        query(l,tree[id].mid,id<<1);  
        query(tree[id].mid+1,r,id<<1|1);  
    }  
}  
void up(int id,int num,int val)  
{  
    if(tree[id].l==num&&tree[id].r==num)  
    {  
        tree[id].sum=val;  
        a[num]=val;  
        return;  
    }  
    if(num<=tree[id].mid) up(id<<1,num,val);  
    else up(id<<1|1,num,val);  
    tree[id].sum=min(tree[id<<1].sum,tree[id<<1|1].sum);  
}  
  
int main()  
{  
    char str[100];  
    int n,m;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        top=1;  
        build(1,n,1);  
        while(m--)  
        {  
            int len=0;  
            scanf("%s",str);  
            int s=0;  
            for(int i=6;str[i];i++)  
            {  
                if(str[i]==','||str[i]==')')  
                {  
                    num[len++]=s;  
                    s=0;  
                }  
                else  
                {  
                    s=s*10+str[i]-'0';  
                }  
            }  
            if(str[0]=='q')  
            {  
                ans=0x7fffffff;  
                int l=num[0];  
                int r=num[1];  
                query(l,r,1);  
                printf("%d\n",ans);  
            }  
            else if(str[0]=='s')  
            {  
                int tmp=a[num[0]];  
                for(int i=0;i<len;i++)  
                {  
                    if(i==len-1) up(1,num[i],tmp);  
                    else up(1,num[i],a[num[i+1]]);  
                }  
            }  
        }  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,