Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #define ll long long;
- using namespace std;
- const int MOD = 1e9 + 7;
- const int p = 15031;
- const int MAXN = 1e5;
- int pw[MAXN];
- int h[MAXN];
- int power[MAXN];
- const int inf = 39489;
- int tree[4 * MAXN];
- int color[4 * MAXN];
- int n;
- vector<int> a;
- void build(int v, int l, int r)
- {
- if (l == r)
- {
- tree[v] = (h[l] - h[l - 1] + MOD) % MOD;
- color[v] = -1;
- }
- else
- {
- int m = (l + r) / 2;
- build(v * 2, l, m);
- build(v * 2 + 1, m + 1, r);
- color[v] = -1;
- tree[v] = (tree[v * 2] + tree[v * 2 + 1]) % MOD;
- }
- }
- void push(int v, int l, int r)
- {
- if (color[v] == -1)
- {
- return;
- }
- int m = (l + r) / 2;
- tree[v * 2] = (color[v] * (power[m] - power[l - 1] + MOD)) % MOD;
- color[v * 2] = color[v];
- tree[v * 2 + 1] = (color[v] * (power[r] - power[m] + MOD)) % MOD;
- color[v * 2 + 1] = color[v];
- color[v] = -1;
- }
- int get(int l, int r, int tv, int tl, int tr)
- {
- if (tr < l || r < tl)
- {
- return inf;
- }
- else if (l <= tl && tr <= r)
- {
- return tree[tv];
- }
- else
- {
- push(tv, tl, tr);
- int tm = (tl + tr) / 2;
- return get(l, r, tv * 2, tl, tm) + get(l, r, tv * 2 + 1, tm + 1, tr);
- }
- }
- void upd(int l, int r, int x, int tv, int tl, int tr)
- {
- if (tr < l || r < tl)
- {
- return;
- }
- else if (l <= tl && tr <= r)
- {
- tree[tv] = (x * (power[tr] - power[tl - 1] + MOD)) % MOD;
- color[tv] = x;
- }
- else
- {
- push(tv, tl, tr);
- int tm = (tl + tr) / 2;
- upd(l, r, x, tv * 2, tl, tm);
- upd(l, r, x, tv * 2 + 1, tm + 1, tr);
- tree[tv] = tree[tv * 2] + tree[tv * 2 + 1];
- }
- }
- int main()
- {
- cin >> n;
- a.resize(n + 1);
- for (int i = 1; i <= n; ++i)
- {
- cin >> a[i];
- }
- pw[1] = 1;
- power[1] = 1;
- for (int i = 2; i <= n; ++i)
- {
- pw[i] = (pw[i - 1] * p) % MOD;
- power[i] = (power[i - 1] + pw[i]) % MOD;
- }
- h[1] = (a[1] * pw[1]) % MOD;
- for (int i = 2; i <= n; ++i)
- {
- h[i] = (h[i - 1] + (a[i] * pw[i]) % MOD) % MOD;
- }
- int q;
- cin >> q;
- for (int i = 0; i < q; ++i)
- {
- int k, l, r, x;
- cin >> k >> l >> r >> x;
- if (k == 0)
- {
- upd(l, r, x, 1, 1, n);
- }
- else
- {
- if (l > r)
- {
- swap(l, r);
- }
- int m = get(l, l + x - 1, 1, 1, n);
- int g = get(r, r + x - 1, 1, 1, n);
- int kek = r - l;
- m = (m * pw[kek]) % MOD;
- if (m == g)
- {
- cout << "+";
- }
- else
- {
- cout << "-";
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement