Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:1164777216")
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<vector>
- #include<math.h>
- #include<string>
- #include<sstream>
- #include<set>
- #include<map>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<memory.h>
- #include<ctime>
- #include<cassert>
- #define pb push_back
- #define sz(a) (int)a.size()
- #define bs binary_search
- #define np next_permutation
- #define mp make_pair
- #define all(a) a.begin(),a.end()
- #define read(a) scanf("%d", &a)
- #define writeln(a) printf("%d\n", a);
- #define forn(i, n) for (int i = 0; i < n; ++i)
- #define forv(i, v) for (int i = 0; i < sz(v); ++i)
- #define _(a, b) memset(a, b, sizeof a)
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
- template<class T> inline T sqr(T x) { return x * x; }
- const double pi = acos(-1.0), eps = 1e-18;
- const int INF = 1000 * 1000 * 1000, MAXN = 100005, MOD = 1000003;
- void prepare(string s) {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt","w",stdout);
- #else
- if (sz(s) != 0) {
- freopen((s + ".in").c_str(), "r", stdin);
- freopen((s + ".out").c_str(), "w", stdout);
- }
- #endif
- }
- struct SegmentTree {
- ll tp[4*MAXN];
- void build (ll *a, ll v, ll L, ll R) {
- if (L == R)
- tp[v] = a[L] % MOD;
- else {
- ll M = (L + R) / 2;
- build(a, v * 2, L, M);
- build(a, v * 2 + 1, M + 1, R);
- tp[v] = (MOD + (tp[v*2] * tp[v*2+1]) % MOD) % MOD;
- }
- }
- ll get_product (ll v, ll L, ll R, ll l, ll r) {
- if (l > r)
- return 1;
- if (l == L && r == R)
- return tp[v] % MOD;
- ll M = (L + R) / 2;
- return (MOD + (get_product(v*2, L, M, l, min(M, r)) *
- get_product(v*2+1, M + 1, R, max(l, M + 1), r)) % MOD) % MOD;
- }
- void update (ll v, ll L, ll R, ll pos, ll val) {
- if (L == R)
- tp[v] = val % MOD;
- else {
- ll M = (L + R) / 2;
- if (pos <= M)
- update(v*2, L, M, pos, val);
- else
- update(v*2+1, M + 1, R, pos, val);
- tp[v] = (MOD + (tp[v*2] * tp[v*2+1]) % MOD) % MOD;
- }
- }
- };
- SegmentTree T;
- ll n, a[MAXN], m, q, l, r;
- void solve()
- {
- cin >> n;
- forn (i, n) cin >> a[i];
- T.build(a, 1, 0, n - 1);
- cin >> m;
- forn (i, m) {
- cin >> q >> l >> r;
- --l; --r;
- if (q == 1) {
- ll res = T.get_product(1, 0, n-1, l, r);
- assert(res >= 0);
- cout << res % MOD << '\n';
- }
- else {
- for (int j = l; j <= r; j++)
- T.update(1, 0, n - 1, j, ++a[j]);
- }
- }
- }
- int main()
- {
- prepare("army");
- srand(time(NULL));
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment