Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define mt make_tuple
  4. #define pb push_back
  5. #define ll long long int
  6.  
  7. using namespace std;
  8. const int N = 100009;
  9.  
  10. struct node{
  11. int max1, max2, summ;
  12. node(){
  13. max1 = INT_MIN;
  14. max2 = INT_MIN;
  15. summ = INT_MIN;
  16. }
  17. };
  18.  
  19. node tree[4*N];
  20. int a[N];
  21.  
  22. node combine(const node nd1, const node nd2){
  23. node temp;
  24. int arr[] = {nd1.max1, nd1.max2, nd2.max1, nd2.max2};
  25. sort(arr, arr+4);
  26. temp.max1 = arr[3];
  27. temp.max2 = arr[2];
  28. temp.summ = temp.max1 + temp.max2;
  29. return temp;
  30. }
  31.  
  32. void build(int ni, int ns, int ne){
  33. node &val = tree[ni];
  34. if(ns == ne){
  35. val.max1 = a[ns];
  36. val.summ = 0;
  37. return;
  38. }
  39. int lf = 2*ni +1, rt = lf+1, mid = ns + ((ne - ns)/2);
  40. build(lf, ns, mid);
  41. build(rt, mid+1, ne);
  42. val = combine(tree[rt], tree[lf]);
  43. }
  44.  
  45. node query(int ql, int qr, int ni, int ns, int ne){
  46. if(ql > qr)
  47. return node();
  48. if(ql == ns and qr == ne)
  49. return tree[ni];
  50. int lf = 2*ni +1, rt = lf + 1, mid = ns + ((ne-ns)/2);
  51. return combine( query(ql, min(qr, mid), lf, ns, mid),
  52. query(max(ql, mid+1), qr, rt, mid+1, ne));
  53.  
  54. }
  55.  
  56. void update(int idx, int v, int ni, int ns, int ne){
  57. node & val = tree[ni];
  58. if(ns == ne){
  59. val.max1 = v;
  60. return;
  61. }
  62. int lf = 2*ni + 1, rt = lf+1, mid = ns + ((ne-ns)/2);
  63. if(idx <= mid)
  64. update(idx, v, lf, ns, mid);
  65. else
  66. update(idx, v, rt, mid+1, ne);
  67.  
  68. val = combine(tree[lf], tree[rt]);
  69. }
  70.  
  71. int main(){
  72.  
  73. ios_base::sync_with_stdio(0);
  74. cin.tie(0);
  75.  
  76. int n, q, xi, yi;
  77. char op;
  78. cin >> n;
  79.  
  80. for(int i = 0; i < n; i++)
  81. cin >> a[i];
  82.  
  83. build(0, 0, n-1);
  84.  
  85. cin >> q;
  86. while(q--){
  87. cin >> op >> xi >> yi;
  88. if(op == 'Q')
  89. cout << (query(xi-1, yi-1, 0, 0, n-1)).summ << endl;
  90. else
  91. update(xi-1, yi, 0, 0, n-1);
  92. }
  93.  
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement