충성 선분 수

tyvj:1038 충성
Time Limit: 1 Sec  Memory Limit: 131072KiBSubmit: 9619  Solved: 3287
제목 연결
http://www.tyvj.cn/p/1038
Description
늙 은 집사 는 총명 하고 유능 한 사람 이다.그 는 10 년 동안 재 주 를 위해 일 했 고, 재 주 는 자신의 장 부 를 더욱 명확 하 게 하기 위해 서 였 다.집사 에 게 매일 k 번 의 장 부 를 기록 하 라 고 요구 하 는데 집사 가 똑똑 하고 유능 하기 때문에 관 리 는 항상 부자 들 을 매우 만족 시 켰 다.그러나 일각 의 이간질 로 재력 가 들 은 집사 에 대한 의구심 을 갖 게 됐다.그래서 그 는 특별한 방법 으로 집사 의 충성 을 판단 하기 로 결정 했다. 그 는 매번 의 장 부 를 1, 2, 3. 번호 로 누 른 다음 에 비정 기적 으로 집사 에 게 문 제 를 물 었 다. 문 제 는 다음 과 같다. a 에서 b 번 장부 에서 가장 적은 금액 은 얼마 입 니까?집사 가 가식 을 부 릴 시간 이 없 도록 그 는 항상 한 번 에 여러 가지 질문 을 한다.
Input
입력 중 첫 번 째 줄 은 두 개의 수 m 가 있 고 n 은 m (m < = 100000) 의 장부 가 있 음 을 나타 내 며 n 은 n 개의 문제 가 있 음 을 나타 낸다. n < = 100000.
두 번 째 행위 m 개 수 는 각각 장부 의 돈 수 이다.
뒤에 n 줄 은 각각 n 개의 문제 이 고 줄 마다 2 개의 숫자 가 끝 난 장부 번 호 를 설명 합 니 다.
Output
출력 파일 에 있 는 모든 문제 의 답 입 니 다.구체 적 으로 샘플 을 살펴보다.
Sample Input
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
Sample Output
2 3 1
HINT
문제 풀이:
선분 나무 누 드 문제 ~
코드:
 

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 400001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //   

const int inf=0x3f3f3f3f;

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

*/

//**************************************************************************************



int n,q,a[maxn];

struct data

{

    int l,r,mn;

}tr[maxn];

void build(int k,int s,int t)

{

    tr[k].l=s;tr[k].r=t;

    if(s==t)

    {

        tr[k].mn=a[s];

        return;

    }

    int mid=(s+t)>>1;

    build(k<<1,s,mid);

    build(k<<1|1,mid+1,t);

    tr[k].mn=min(tr[k<<1].mn,tr[k<<1|1].mn);

}

int ask(int k,int s,int t)

{

    int l=tr[k].l,r=tr[k].r;

    if(s==l&&t==r)

        return tr[k].mn;

    int mid=(l+r)>>1;

    if(t<=mid)

        return ask(k<<1,s,t);

    if(s>mid)

        return ask(k<<1|1,s,t);

    return min(ask(k<<1,s,mid),ask(k<<1|1,mid+1,t));

}

int main()

{

    int n,q;

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

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

    {

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

    }

    build(1,1,n);

    for(int i=1;i<=q;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        printf("%d ",ask(1,x,y));

    }

    return 0;

}