原题见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<