|
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 1048576 int tree[MAXN]; int M = 1; void tree_init(int num){ memset(tree, 0, sizeof(tree)); M = 1; for (; M <= num; M <<= 1); M <<= 1; M--; } int tree_query(unsigned int from,unsigned int to){ from--,to++; from += M,to += M; int res = 0; while (from^to^1) { //cout << "+" << from << "+" << to << '~' << endl; if (~from & 1) {//这里是按位取反，不是负号，也不能和0与那样的话肯定是0啊 //from on left res = max(res,tree[from+1]); } if (to & 1) { //to on right res = max(res,tree[to-1]); } from >>= 1,to >>= 1; } return res; } void tree_update(unsigned int nodeNum,int newGrade){ nodeNum += M; tree[nodeNum] = newGrade; while (nodeNum != 1) { nodeNum >>= 1; tree[nodeNum] = max(tree[nodeNum << 1],tree[(nodeNum << 1) + 1]); } } int main(){ int n = 0,m = 0; while (cin >> n >> m) { tree_init(n); for (int i = 1; i <= n; i++) { int arg; scanf(" %d",&arg); tree_update(i+1, arg); } for (int i = 1; i <= m; i++) { char cmd; int arg1 = 0,arg2 = 0; scanf(" %c %d %d",&cmd,&arg1,&arg2); if (cmd == 'U') { arg1++; tree_update(arg1, arg2); }else{ arg1++,arg2++; cout << tree_query(min(arg1,arg2), max(arg1,arg2)) << endl; } } } return 0; } |
数组开的比较大，清数组会消耗很多时间所以跑了1000多。
基于zkw版线段树实现。
