fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct tree {
  5. long * tr;
  6. tree(int n) {
  7. tr = new long[4 * n + 1];
  8. }
  9. void build(int * arr, int v, int l, int r) {
  10. if (l == r) tr[v] = arr[l];
  11. else {
  12. int mid = (l + r) / 2;
  13. build(arr, v * 2, l, mid);
  14. build(arr, v * 2 + 1, mid + 1, r);
  15. tr[v] = tr[v * 2] + tr[v * 2 + 1];
  16. }
  17. }
  18. void update(int v, int l, int r, int pos, int val) {
  19. if (l == r) tr[v] = val;
  20. else {
  21. int mid = (l + r) / 2;
  22. if (pos <= mid) update(v * 2, l, mid, pos, val);
  23. else update(v * 2 + 1, mid + 1, r, pos, val);
  24. tr[v] = tr[v * 2] + tr[v * 2 + 1];
  25. }
  26. }
  27. int find(int v, int l, int r, int max) {
  28. if (l == r)
  29. return (tr[v] <= max);
  30. int mid = (l + r) / 2;
  31. if (tr[v * 2] > max)
  32. return find(v * 2, l, mid, max);
  33. else
  34. return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);
  35. }
  36. };
  37.  
  38. int main() {
  39. int n, m, * arr;
  40. cin >> n;
  41. arr = new int[n + 1];
  42. for (int i = 1; i <= n; ++i) cin >> arr[i];
  43. tree tr(n);
  44. tr.build(arr, 1, 1, n);
  45. cin >> m;
  46. int com, x, y, v;
  47. for (int i = 0; i < m; ++i) {
  48. cin >> com;
  49. switch (com) {
  50. case 1:
  51. {
  52. cin >> v;
  53. cout << tr.find(1, 1, n, v) << '\n';
  54. break;
  55. }
  56. case 2:
  57. {
  58. cin >> x >> y;
  59. tr.update(1, 1, n, x, y);
  60. break;
  61. }
  62. }
  63. }
  64. return 0;
  65. }
Success #stdin #stdout 0s 15248KB
stdin
5
1 3 4 5 6
5
1 7
1 9
2 3 5
1 7
2 3 1
stdout
2
3
2