Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // segtree hash
- //
- // Created by Артем Стрельцов on 16.09.17.
- // Copyright © 2017 Артем Стрельцов. All rights reserved.
- //
- #include <bits/stdc++.h>
- #define int long long
- #define mp(x, y) make_pair(x, y)
- #define fs first
- #define sc second
- #define pb(x) push_back(x)
- #define sz(x) (int)x.size()
- #define len(x) (int)x.length()
- #define forn(i, a, b) for (int i = a; i < b; ++i)
- typedef long long ll;
- using namespace std;
- const int MAX_SIZE = 4e5;
- const int mod = (int)1e9 + 13;
- const int p = 239;
- int pows[MAX_SIZE];
- int h[MAX_SIZE];
- struct segtree{
- int t[MAX_SIZE];
- int psh[MAX_SIZE];
- void init() {
- forn(i, 0, MAX_SIZE) psh[i] = -1;
- }
- void push(int i, int tl, int tr) {
- if (tl == tr) {
- if (psh[i] != -1) {
- t[i] = psh[i];
- }
- }
- else {
- if (psh[i] != -1) {
- t[i] = (h[tr - tl] * psh[i]) % mod;
- psh[i * 2 + 1] = psh[i];
- psh[i * 2 + 2] = psh[i];
- }
- }
- psh[i] = -1;
- }
- int recount(int one, int two, int delta) {
- if (one == -1)
- return two;
- if (two == -1)
- return one;
- return ((one * pows[delta]) % mod + two) % mod;
- }
- void set(int i, int tl, int tr, int ind, int val) {
- push(i, tl, tr);
- if (tl == tr) {
- t[i] = val;
- return;
- }
- int tm = (tl + tr) / 2;
- if (tm >= ind)
- set(i * 2 + 1, tl, tm, ind, val);
- else
- set(i * 2 + 2, tm + 1, tr, ind, val);
- t[i] = recount(t[i * 2 + 1], t[i * 2 + 2], tr - tm);
- }
- void upd(int i, int tl, int tr, int l, int r, int val) {
- push(i, tl, tr);
- if (tr < l || tl > r)
- return;
- if (l <= tl && r >= tr) {
- psh[i] = val;
- push(i, tl, tr);
- return;
- }
- int tm = (tl + tr) / 2;
- upd(2 * i + 1, tl, tm, l, r, val);
- upd(2 * i + 2, tm + 1, tr, l, r, val);
- t[i] = recount(t[i * 2 + 1], t[i * 2 + 2], tr - tm);
- }
- int get(int i, int tl, int tr, int l, int r) {
- push(i, tl, tr);
- if (tr < l || tl > r) return -1;
- if (tl >= l && tr <= r)
- return t[i];
- int tm = (tl + tr) / 2;
- return recount(get(i * 2 + 1, tl, tm, l, r), get(i * 2 + 2, tm + 1, tr, l, r), min(tr, r) - tm);
- }
- };
- void calc_hash() {
- pows[0] = 1;
- forn(i, 1, MAX_SIZE) pows[i] = (pows[i - 1] * p) % mod;
- h[0] = 1;
- forn(i, 1, MAX_SIZE) h[i] = (h[i - 1] + pows[i]);
- }
- signed main() {
- int n, m;
- cin >> n;
- segtree tree;
- tree.init();
- calc_hash();
- forn(i, 0, n) {
- int val;
- cin >> val;
- tree.set(0, 0, n - 1, i, val);
- }
- cin >> m;
- forn(i, 0, m) {
- int q, l, r, k;
- cin >> q >> l >> r >> k;
- --l, --r;
- if (q == 0)
- tree.upd(0, 0, n - 1, l, r, k);
- else {
- cout << (tree.get(0, 0, n - 1, l, l + k - 1) == tree.get(0, 0, n - 1, r, r + k - 1) ? '+' : '-');
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment