題意：在每個測試的第一行，有兩個正整數 N 和 M ( 0<N<=200000,0<M<5000 )，分別代表學生的數目和操作的數目。 學生ID編號分別從1編到N。 第二行包含N個整數，代表這N個學生的初始成績，其中第i個數代表ID為i的學生的成績。 接下來有M行。每一行有一個字符 C (只取'Q'或'U') ，和兩個正整數A，B。 當C為'Q'的時候，表示這是一條詢問操作，它詢問ID從A到B(包括A,B)的學生當中，成績最高的是多少。 當C為'U'的時候，表示這是一條更新操作，要求把ID為A的學生的成績更改為B。 ——>>線段樹點修改，幸運，這次遞歸建樹沒有超時，437MS過！ [cpp] #include <cstdio> #include <algorithm> using namespace std; const int maxn = 200000 + 10, INF = -214748364; int a[maxn], maxv[4*maxn], A, B; //a為輸入數組，maxv為線段樹結點數組，存該相應區間的最大值 void update(int o, int L, int R) //線段樹更新，把a[A]改為B { if(L == R) maxv[o] = B; else { int M = L + (R - L) / 2; if(A <= M) update(2*o, L, M); else update(2*o+1, M+1, R); maxv[o] = max(maxv[2*o], maxv[2*o+1]); } } int query(int o, int L, int R) //線段樹查詢[A, B]間的最大值 { if(A <= L && R <= B) return maxv[o]; int M = L + (R - L) / 2, ans = INF; if(A <= M) ans = max(ans, query(2*o, L, M)); if(B > M) ans = max(ans, query(2*o+1, M+1, R)); return ans; } void build(int o, int L, int R) //建樹 { if(L == R) { maxv[o] = a[L]; return; } int M = L + (R - L) / 2; if(L <= M) build(2*o, L, M); if(R > M) build(2*o+1, M+1, R); maxv[o] = max(maxv[2*o], maxv[2*o+1]); } www.2cto.com int main() { int N, M; char C; while(~scanf("%d%d\n", &N, &M)) { for(int i = 1; i <= N; i++) scanf("%d", &a[i]); build(1, 1, N); while(M--) { scanf("\n%c%d%d", &C, &A, &B); if(C == 'U') update(1, 1, N); else printf("%d\n", query(1, 1, N)); } } return 0; }
