fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. //Дерево отрезков.
  5. struct segment_tree{
  6. long *tree;
  7.  
  8. //Конструктор.
  9. segment_tree(int length){
  10. tree = new long[4*length+1];
  11. }
  12.  
  13. //Построение дерева отрезков по массиву a.
  14. void build(int *a, int v, int tree_l, int tree_r){
  15. if(tree_l == tree_r) tree[v] = a[tree_l];
  16. else{
  17. int tree_m = (tree_l + tree_r)/2;
  18. build(a, v*2, tree_l, tree_m);
  19. build(a, v*2+1, tree_m+1, tree_r);
  20. tree[v] = tree[v*2] + tree[v*2+1];
  21. }
  22. }
  23.  
  24. //Присваивание человечку на позиции pos веса new_val.
  25. void update(int v, int tree_l, int tree_r, int pos, int new_val){
  26. if(tree_l == tree_r) tree[v] = new_val;
  27. else{
  28. int tree_m = (tree_l + tree_r)/2;
  29. if(pos <= tree_m){
  30. update(v*2, tree_l, tree_m, pos, new_val);
  31. }
  32. else{
  33. update(v*2+1, tree_m+1, tree_r, pos, new_val);
  34. }
  35. tree[v] = tree[v*2] + tree[v*2+1];
  36. }
  37. }
  38.  
  39. //Нахождение количества поместившихся человечков.
  40. int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){
  41. if(tree_l == tree_r) return tree[v] <= max_w;
  42. int tree_m = (tree_l + tree_r)/2;
  43. if(tree[v*2] > max_w)
  44. return find_numb_of_p(v*2, tree_l, tree_m, max_w);
  45. else
  46. return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]);
  47. }
  48. };
  49.  
  50. int main() {
  51. int n, m, *weights;
  52. cin >> n;
  53. //Заполнение массива весов человечков.
  54. weights = new int[n+1];
  55. for(int i = 1; i <= n; ++i){
  56. cin >> weights[i];
  57. }
  58. //Построение дерева отрезков.
  59. segment_tree tr(n);
  60. tr.build(weights, 1, 1, n);
  61. //Обработка запросов.
  62. cin >> m;
  63. int type, x, y, v;
  64. for(int i = 0; i < m; ++i){
  65. cin >> type;
  66. if(type == 2){
  67. cin >> x >> y;
  68. tr.update(1, 1, n, x, y);
  69. }
  70. else{
  71. cin >> v;
  72. cout << tr.find_numb_of_p(1, 1, n, v) << '\n';
  73. }
  74. }
  75. return 0;
  76. }
Success #stdin #stdout 0s 16072KB
stdin
2
1 2
3
1 4
2 1 10
1 4
stdout
2
0