[CodeVS 2173]忠诚

解题报告

原题见CodeVS 分析:这道题一看时间、数据范围、查询方式就能知道肯定是线段树。而且是裸线段树//雾。。。 顺带吐槽一下题面,这个主人能把账记得那么详细还要管家干什么。。。

#include 
#include 
#include 
using namespace std;
int n, m;
int c[100005];
struct node{
    int mini, le, ri;
}tree[300015];
inline int leftt(int x)
{
    return x<<1;
}
inline int rightt(int x)
{
    return (x<<1)^1;
}
inline int mid(int x,int y)
{
    return (x+y)>>1;
}
inline void biu(int cur,int l,int r)
{
    if(l==r)
    {
        tree[cur].le=tree[cur].ri=l;
        tree[cur].mini=c[l];
        return;
    }
    else
    {
        biu(leftt(cur),l,mid(l,r));
        biu(rightt(cur),mid(l,r)+1,r);
        tree[cur].mini=min(tree[leftt(cur)].mini,tree[rightt(cur)].mini);
        tree[cur].le=l;
        tree[cur].ri=r;
    }
    return;
}
int ask(int cur,int l,int r)
{
    if(tree[cur].le==l&&tree[cur].ri==r)
        return tree[cur].mini;
    else
    {
        if(r<=tree[leftt(cur)].ri)
            return ask(leftt(cur),l,r);
        else if(l>=tree[rightt(cur)].le)
            return ask(rightt(cur),l,r);
        else
            return min(ask(leftt(cur),l,tree[leftt(cur)].ri),ask(rightt(cur),tree[rightt(cur)].le,r));
    }
}
inline int get_num()
{
    int ans=0;
    char tmp;
    tmp=getchar();
    while(tmp<'0'||tmp>'9')   tmp=getchar();
    while(tmp>='0'&&tmp<='9')
    {
        ans=ans*10+tmp-48;
        tmp=getchar();
    }
    return ans;
}
int main()
{
    m=get_num();n=get_num();
    for(int i=1;i<=m;i++)
    {
        c[i]=get_num();
    }
    biu(1,1,m);
    for(int i=1;i<=n;i++)
    {
        int x, y;
        x=get_num();
        y=get_num();
        cout<

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理