题目来自COGS
绵延延绵的山峰这道题啊，裸的线段树，并不知道为什么就算到两星半的难度了。。
即使是一道水题，并不排除用高级算法解决来刷rank。
这几天我大致研究了一下zkw线段树，不得不说，从下到上的线段树就是快啊，膜拜神犇zkw，我是蒟蒻orz....
代码已经用了所有我能想到的常数优化，然而依然不是rank1，这就很尴尬了。。。
|
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 |
#include <iostream> #include <cstdio> #include <algorithm> #define MX 1000010 using namespace std; int tree[MX<<2]; int n, q, x, y, m, a; inline int get_num() { int ans=0; char tmp; while(tmp<'0'||tmp>'9') tmp=getchar(); while(tmp>='0'&&tmp<='9') { ans=ans*10+tmp-48; tmp=getchar(); } return ans; } int main() { //freopen("climb.in","r",stdin); //freopen("climb.out","w",stdout); n=get_num(); for(m=1;m<n+2;m<<=1); n++; for(int i=1;i<=n;i++) { tree[i+m]=get_num(); } for(int i=m-1;i>=1;i--) tree[i]=max(tree[i<<1],tree[(i<<1)^1]); q=get_num(); for(int i=1;i<=q;i++) { x=get_num()+1;y=get_num()+1; a=0; x=x+m-1; y=y+m+1; for(;x^y^1;x>>=1,y>>=1) { if(!(x&1)) a=max(a,tree[x^1]); if(y&1) a=max(a,tree[y^1]); } cout<<a<<"\n"; } return 0; } |