原题见CodeVS
分析：这道题一看时间、数据范围、查询方式就能知道肯定是线段树。而且是裸线段树//雾。。。
顺带吐槽一下题面，这个主人能把账记得那么详细还要管家干什么。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <cstdio> #include <algorithm> 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<<ask(1,x,y)<<" "; } return 0; } |