I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28977 Accepted Submission(s):
11496
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 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。
在每个测试的第一行,有两个正整数 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。
Output
对于每一次询问操作,在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cinAuthor
linle
Source
Recommend
lcy
思路:线段树
超空间代码:
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int n,m; char str; int a,b; int flag; int ans; struct Node { int ld,rd; Node *lc,*rc; int maxn; }; int map[200010]; Node *buildtree(int begin,int end) { Node* p = new Node; p -> ld = begin; p -> rd = end; int maxn = 0; for(int i = begin;i <= end;i ++) if(map[i] > maxn) maxn = map[i]; p -> maxn = maxn; if(begin == end) return p; p -> lc = buildtree(begin,(begin + end) / 2); p -> rc = buildtree((begin + end) / 2 + 1,end); return p; } void insert(Node* T,int position,int score) { if(ans == 1) return ; if(position >= T -> ld && position <= T -> rd) { if(score > T -> maxn) T -> maxn = score; if(T -> ld == T -> rd) { ans = 1; return ; } } if(T -> ld == T -> rd == position) { ans = 1; return ; } if(ans == 1) return ; if(position <= (T -> ld + T -> rd) / 2) insert(T -> lc,position,score); if(position > (T -> ld + T -> rd) / 2) insert(T -> rc,position,score); } int search(Node* T,int begin,int end) { if(begin <= T -> ld && end >= T -> rd) { if(T -> maxn > flag) flag = T -> maxn; return flag; } if(begin <= (T -> ld + T -> rd) / 2) search(T -> lc,begin,end); if(end > (T -> ld + T -> rd) / 2) search(T -> rc,begin,end); return flag; } int main() { while(~scanf("%d%d",&n,&m)) { memset(map,0,sizeof(map)); for(int i = 1;i <= n;i ++) scanf("%d",&map[i]); Node* root = buildtree(1,n); for(int i = 1;i <= m;i ++) { scanf(" %c%d%d",&str,&a,&b); if(str == 'U') insert(root,a,b); else { flag = 0;ans = 0; printf("%d ",search(root,a,b)); } } } return 0; }
AC代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; #define MAXN 1100024 int n,m; int map[MAXN]; int a,b; char str_char; int ans; struct Node { int leftboundary,rightboundary; int max; }Tree[MAXN]; int buildtree(int position,int begin,int end) { Tree[position].leftboundary = begin; Tree[position].rightboundary = end; if(begin == end) return Tree[position].max = map[begin]; int x = buildtree(2 * position,begin,(begin + end) / 2); int y = buildtree(2 * position + 1,(begin + end) / 2 + 1,end); return Tree[position].max = x > y ? x : y; } void insert(int position,int begin,int score) { if(begin >= Tree[position].leftboundary && begin <= Tree[position].rightboundary) { if(Tree[position].max < score) Tree[position].max = score; } if(Tree[position].leftboundary == Tree[position].rightboundary) return ; if(begin <= (Tree[position].leftboundary + Tree[position].rightboundary) / 2) insert(2 * position,begin,score); if(begin > (Tree[position].leftboundary + Tree[position].rightboundary) / 2) insert(2 * position + 1,begin,score); } int search(int position,int begin,int end) { if(Tree[position].leftboundary == begin && end == Tree[position].rightboundary) { return Tree[position].max; } int mid = (Tree[position].leftboundary + Tree[position].rightboundary) / 2; if(end <= (Tree[position].leftboundary + Tree[position].rightboundary) / 2) return search(2 * position,begin,end); else if(begin > (Tree[position].leftboundary + Tree[position].rightboundary) / 2) { return search(2 * position + 1,begin,end); } else { int x = search(2 * position,begin,mid); int y = search(2 * position + 1,mid + 1,end); return x > y ? x : y; } } int main() { while(~scanf("%d%d",&n,&m)) { memset(map,0,sizeof(map)); memset(Tree,0,sizeof(Tree)); for(int i = 1;i <= n;i ++) { scanf("%d",&map[i]); } buildtree(1,1,n); ans = 0; while(m --) { scanf(" %c%d%d",&str_char,&a,&b); if(str_char == 'U') { insert(1,a,b); map[a] = b; } if(str_char == 'Q') { printf("%d ",search(1,a,b)); } } } return 0; }
修改后仍然超空间代码:
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int n,m; char str; int a,b; int flag; int ans; struct Node { int ld,rd; Node *lc,*rc; int maxn; }; int map[200001]; Node *buildtree(int begin,int end) { Node* p = new Node; p -> ld = begin; p -> rd = end; if(begin == end) { p -> maxn = map[begin]; return p; } p -> lc = buildtree(begin,(begin + end) / 2); p -> rc = buildtree((begin + end) / 2 + 1,end); int x = p -> lc -> maxn;int y = p -> rc -> maxn; p -> maxn = x > y ? x : y; return p; } void insert(Node* T,int position,int score) { if(T -> ld <= position && T -> rd >= position) { if(T -> maxn < score) T -> maxn = score; } if(T -> ld == T -> rd) return ; if(position <= (T -> ld + T -> rd) / 2) insert(T -> lc,position,score); if(position > (T -> ld + T -> rd) / 2) insert(T -> rc,position,score); } int search(Node* T,int begin,int end) { if(T -> ld == begin && T -> rd == end) { return T -> maxn; } int mid = (T -> ld + T -> rd) / 2; if(end <= mid) { return search(T -> lc,begin,end); } else if(begin > mid) { return search(T -> rc,begin,end); } else { int x = search(T -> lc,begin,mid); int y = search(T -> rc,mid + 1,end); return x > y ? x : y; } } int main() { while(~scanf("%d%d",&n,&m)) { memset(map,0,sizeof(map)); for(int i = 1;i <= n;i ++) scanf("%d",&map[i]); Node* root = buildtree(1,n); for(int i = 1;i <= m;i ++) { scanf(" %c%d%d",&str,&a,&b); if(str == 'U') { insert(root,a,b); map[a] = b; } else { flag = 0;ans = 0; printf("%d ",search(root,a,b)); } } } return 0; }
代码:哈囧