題目大意:
很多學校流行一種比較的習慣。老師們很喜歡詢問,從某某到某某當中,分數最高的是多少。
這讓很多學生很反感。
不管你喜不喜歡,現在需要你做的是,就是按照老師的要求,寫一個程序,模擬老師的詢問。當然,老師有時候需要更新某位同學的成績。
思路:
線段樹即可。。
PS:某一題線段樹太久沒寫一直調不出,先來做做水題。。
I Hate It !
#include#include #include using namespace std; typedef long long LL; const int MAXN=200000; int data[MAXN]; const int INF=-0x3fffffff; int A[MAXN],maxv[MAXN*3]; int n,qL,qR,p,v; void build(int k,int L,int R) { if(L==R) maxv[k]=A[L]; else { int m=(L+R)/2; build(k*2,L,m); build(k*2+1,m+1,R); maxv[k]=max(maxv[k*2],maxv[k*2+1]); } } // 查詢區間[a,b] 對應區間[L,R]; int query(int k,int L,int R,int a,int b) { int m=(L+R)/2,ans=INF; if(a<=L && R<=b) return maxv[k]; if(a<=m) ans=max(ans,query(k*2,L,m,a,b)); if(m