首页 > 其他 > 详细

【TYVJ】P1038 忠诚

时间:2016-08-17 08:59:27      阅读:324      评论:0      收藏:0      [点我收藏+]

【算法】线段树

技术分享
#include<cstdio>
#include<algorithm>
using namespace std;
struct treess{int l,r,ms;}t[400010];
const int maxn=200010,inf=0x3f3f3f3f;
int a[maxn],n,m;
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    if(l==r){t[k].ms=a[l];return;}
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    t[k].ms=min(t[k<<1].ms,t[k<<1|1].ms);
//    printf("[%d] l=%d r=%d ms=%d",k,t[k].l,t[k].r,t[k].ms);
}
int ask(int k,int l,int r)
{
    int left=t[k].l,right=t[k].r,ans=inf;
    if(l<=left&&r>=right)return t[k].ms;
     else
      {
        int mid=(left+right)>>1;
        if(l<=mid)ans=min(ans,ask(k<<1,l,r));
        if(r>mid)ans=min(ans,ask(k<<1|1,l,r));
      }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    int nowl,nowr;
    for(int i=1;i<m;i++)
     {
         scanf("%d%d",&nowl,&nowr);
         printf("%d ",ask(1,nowl,nowr));
     }
    scanf("%d%d",&nowl,&nowr);
    printf("%d",ask(1,nowl,nowr));
    return 0;
}
View Code

 

【TYVJ】P1038 忠诚

原文:http://www.cnblogs.com/onioncyc/p/5778546.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!