fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева
  5. {
  6. if (i == j)
  7. tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P"
  8. else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом
  9. {
  10. int m = (i + j) / 2;
  11. sequence(tree, given, position * 2, i, m);
  12. sequence(tree, given, position * 2 + 1, m + 1, j);
  13. tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок
  14. }
  15. }
  16.  
  17. void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")
  18. {
  19. if (i == j)
  20. tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);
  21. else if (i!=j)
  22. {
  23. int m = (i + j) / 2;
  24. if (nposition <= m)
  25. For_C_command(tree, position * 2, i, m, nposition, v);
  26. else
  27. For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);
  28. tree[position] = tree[position * 2] * tree[position * 2 + 1];
  29. }
  30. }
  31.  
  32. int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"
  33. {
  34. if (i == qi && j == qj)
  35. return tree[position];
  36. else
  37. {
  38. int m = (i + j) / 2;
  39. if (qj <= m)
  40. return For_P_command(tree, position * 2, i, m, qi, qj);
  41. else if (qi >= m + 1)
  42. return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);
  43. else
  44. return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);
  45. }
  46. }
  47.  
  48. int main()
  49. {
  50. ios::sync_with_stdio(false); // ускоряем чтение
  51. int n, k;
  52. while (cin >> n >> k)
  53. {
  54. int given[n];
  55. for (int i = 0; i < n; i++)
  56. cin >> given[i];
  57. int tree[n * 4];
  58. sequence(tree, given, 1, 0, n - 1);
  59. for (int i = 0; i < k; i++)
  60. {
  61. char command;
  62. int xi, xj;
  63. cin >> command >> xi >> xj;
  64. if (command == 'P')
  65. {
  66. int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи
  67. if (x < 0)
  68. printf("-");
  69. else if (x > 0)
  70. printf("+");
  71. else
  72. printf("0");
  73. }
  74. else
  75. For_C_command(tree, 1, 0, n - 1, xi - 1, xj);
  76. }
  77. printf("\n");
  78. }
  79. }
  80.  
Success #stdin #stdout 0s 3460KB
stdin
6 4
0 20 0 30 0 -10
P 2 2
P 2 3
P 3 6
P 2 6
4 3
0 -1 -2 0
P 2 3
C 1 9
P 1 2
3 3
5 2 0
C 1 7
C 3 0
C 1 0
6 5
100 10 55 11 0 -33
P 1 4
C 5 6
C 3 72
C 5 -200
P 5 6


stdout
+000
+-

++