Guest User

Untitled

a guest
Nov 2nd, 2014
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.87 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:1164777216")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include<iostream>
  4. #include<stdio.h>
  5. #include<algorithm>
  6. #include<vector>
  7. #include<math.h>
  8. #include<string>
  9. #include<sstream>
  10. #include<set>
  11. #include<map>
  12. #include<stack>
  13. #include<queue>
  14. #include<deque>
  15. #include<memory.h>
  16. #include<ctime>
  17. #include<cassert>
  18.  
  19. #define pb push_back
  20. #define sz(a) (int)a.size()
  21. #define bs binary_search
  22. #define np next_permutation
  23. #define mp make_pair
  24. #define all(a) a.begin(),a.end()
  25. #define read(a) scanf("%d", &a)
  26. #define writeln(a) printf("%d\n", a);
  27. #define forn(i, n) for (int i = 0; i < n; ++i)
  28. #define forv(i, v) for (int i = 0; i < sz(v); ++i)
  29. #define _(a, b) memset(a, b, sizeof a)
  30.  
  31. typedef long long ll;
  32. typedef unsigned long long ull;
  33.  
  34. using namespace std;
  35.  
  36. template<class T> inline T sqr(T x) { return x * x; }
  37.  
  38. const double pi = acos(-1.0), eps = 1e-18;
  39. const int INF = 1000 * 1000 * 1000, MAXN = 100005, MOD = 1000003;
  40.  
  41. void prepare(string s) {
  42. #ifdef _DEBUG
  43. freopen("input.txt", "r", stdin);
  44. freopen("output.txt","w",stdout);
  45. #else
  46. if (sz(s) != 0) {
  47. freopen((s + ".in").c_str(), "r", stdin);
  48. freopen((s + ".out").c_str(), "w", stdout);
  49. }
  50. #endif
  51. }
  52.  
  53. struct SegmentTree {
  54. ll tp[4*MAXN];
  55.  
  56. void build (ll *a, ll v, ll L, ll R) {
  57. if (L == R)
  58. tp[v] = a[L] % MOD;
  59. else {
  60. ll M = (L + R) / 2;
  61. build(a, v * 2, L, M);
  62. build(a, v * 2 + 1, M + 1, R);
  63. tp[v] = (MOD + (tp[v*2] * tp[v*2+1]) % MOD) % MOD;
  64. }
  65. }
  66.  
  67. ll get_product (ll v, ll L, ll R, ll l, ll r) {
  68. if (l > r)
  69. return 1;
  70. if (l == L && r == R)
  71. return tp[v] % MOD;
  72. ll M = (L + R) / 2;
  73. return (MOD + (get_product(v*2, L, M, l, min(M, r)) *
  74. get_product(v*2+1, M + 1, R, max(l, M + 1), r)) % MOD) % MOD;
  75. }
  76.  
  77. void update (ll v, ll L, ll R, ll pos, ll val) {
  78. if (L == R)
  79. tp[v] = val % MOD;
  80. else {
  81. ll M = (L + R) / 2;
  82. if (pos <= M)
  83. update(v*2, L, M, pos, val);
  84. else
  85. update(v*2+1, M + 1, R, pos, val);
  86. tp[v] = (MOD + (tp[v*2] * tp[v*2+1]) % MOD) % MOD;
  87. }
  88. }
  89. };
  90.  
  91. SegmentTree T;
  92. ll n, a[MAXN], m, q, l, r;
  93.  
  94. void solve()
  95. {
  96. cin >> n;
  97. forn (i, n) cin >> a[i];
  98. T.build(a, 1, 0, n - 1);
  99. cin >> m;
  100. forn (i, m) {
  101. cin >> q >> l >> r;
  102. --l; --r;
  103. if (q == 1) {
  104. ll res = T.get_product(1, 0, n-1, l, r);
  105. assert(res >= 0);
  106. cout << res % MOD << '\n';
  107. }
  108. else {
  109. for (int j = l; j <= r; j++)
  110. ++a[j];
  111. T.build(a, 1, 0, n - 1);
  112. }
  113. }
  114. }
  115.  
  116. int main()
  117. {
  118. prepare("army");
  119. srand(time(NULL));
  120.  
  121. solve();
  122.  
  123. return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment