in_chainz

Untitled

Nov 20th, 2018
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.25 KB | None | 0 0
  1. //
  2. //  main.cpp
  3. //  segtree hash
  4. //
  5. //  Created by Артем Стрельцов on 16.09.17.
  6. //  Copyright © 2017 Артем Стрельцов. All rights reserved.
  7. //
  8.  
  9. #include <bits/stdc++.h>
  10.  
  11. #define int long long
  12. #define mp(x, y) make_pair(x, y)
  13. #define fs first
  14. #define sc second
  15. #define pb(x) push_back(x)
  16. #define sz(x) (int)x.size()
  17. #define len(x) (int)x.length()
  18. #define forn(i, a, b) for (int  i = a; i < b; ++i)
  19.  
  20. typedef long long ll;
  21.  
  22. using namespace std;
  23.  
  24. const int MAX_SIZE = 4e5;
  25. const int mod = (int)1e9 + 13;
  26. const int p = 239;
  27. int pows[MAX_SIZE];
  28. int h[MAX_SIZE];
  29.  
  30. struct segtree{
  31.     int t[MAX_SIZE];
  32.     int psh[MAX_SIZE];
  33.     void init() {
  34.         forn(i, 0, MAX_SIZE) psh[i] = -1;
  35.     }
  36.    
  37.     void push(int i, int tl, int tr) {
  38.         if (tl == tr) {
  39.             if (psh[i] != -1) {
  40.                 t[i] = psh[i];
  41.             }
  42.         }
  43.         else {
  44.             if (psh[i] != -1) {
  45.                 t[i] = (h[tr - tl] * psh[i]) % mod;
  46.                 psh[i * 2 + 1] = psh[i];
  47.                 psh[i * 2 + 2] = psh[i];
  48.             }
  49.         }
  50.         psh[i] = -1;
  51.     }
  52.    
  53.     int recount(int one, int two, int delta) {
  54.         if (one == -1)
  55.             return two;
  56.         if (two == -1)
  57.             return one;
  58.         return ((one * pows[delta]) % mod + two) % mod;
  59.     }
  60.    
  61.     void set(int i, int tl, int tr, int ind, int val) {
  62.         push(i, tl, tr);
  63.         if (tl == tr) {
  64.             t[i] = val;
  65.             return;
  66.         }
  67.         int tm = (tl + tr) / 2;
  68.         if (tm >= ind)
  69.             set(i * 2 + 1, tl, tm, ind, val);
  70.         else
  71.             set(i * 2 + 2, tm + 1, tr, ind, val);
  72.         t[i] = recount(t[i * 2 + 1], t[i * 2 + 2], tr - tm);
  73.     }
  74.    
  75.     void upd(int i, int tl, int tr, int l, int r, int val) {
  76.         push(i, tl, tr);
  77.         if (tr < l || tl > r)
  78.             return;
  79.         if (l <= tl && r >= tr) {
  80.             psh[i] = val;
  81.             push(i, tl, tr);
  82.             return;
  83.         }
  84.         int tm = (tl + tr) / 2;
  85.         upd(2 * i + 1, tl, tm, l, r, val);
  86.         upd(2 * i + 2, tm + 1, tr, l, r, val);
  87.         t[i] = recount(t[i * 2 + 1], t[i * 2 + 2], tr - tm);
  88.     }
  89.    
  90.     int get(int i, int tl, int tr, int l, int r) {
  91.         push(i, tl, tr);
  92.         if (tr < l || tl > r) return -1;
  93.         if (tl >= l && tr <= r)
  94.             return t[i];
  95.         int tm = (tl + tr) / 2;
  96.         return recount(get(i * 2 + 1, tl, tm, l, r), get(i * 2 + 2, tm + 1, tr, l, r), min(tr, r) - tm);
  97.     }
  98.    
  99. };
  100.  
  101. void calc_hash() {
  102.     pows[0] = 1;
  103.     forn(i, 1, MAX_SIZE) pows[i] = (pows[i - 1] * p) % mod;
  104.     h[0] = 1;
  105.     forn(i, 1, MAX_SIZE) h[i] = (h[i - 1] + pows[i]);
  106.    
  107. }
  108.  
  109. signed main() {
  110.     int n, m;
  111.     cin >> n;
  112.     segtree tree;
  113.    
  114.     tree.init();
  115.     calc_hash();
  116.    
  117.     forn(i, 0, n) {
  118.         int val;
  119.         cin >> val;
  120.         tree.set(0, 0, n - 1, i, val);
  121.     }
  122.    
  123.     cin >> m;
  124.     forn(i, 0, m) {
  125.         int q, l, r, k;
  126.         cin >> q >> l >> r >> k;
  127.         --l, --r;
  128.         if (q == 0)
  129.             tree.upd(0, 0, n - 1, l, r, k);
  130.         else {
  131.             cout << (tree.get(0, 0, n - 1, l, l + k - 1) == tree.get(0, 0, n - 1, r, r + k - 1) ? '+' : '-');
  132.         }
  133.     }
  134.    
  135.     return 0;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment