fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12.  
  13. const int N = 512 * 1024;
  14. const ll mod = 1e9 + 9;
  15. const ll X = 13371337;
  16.  
  17. ll tab[N];
  18.  
  19. ll potega(ll a, ll b) {
  20.     ll wyn = 1;
  21.     a %= mod;
  22.     while(b){
  23.         if(b & 1) wyn = (wyn * a) % mod;
  24.         a = (a * a) % mod;
  25.         b >>= 1;
  26.     }
  27.     return wyn;
  28. }
  29.  
  30. struct node{
  31.     ll h;
  32.     ll mn1, cnt, mn2;
  33.     ll lazy_ustaw, lazy_add;
  34. };
  35.  
  36. node seg[2 * N];
  37.  
  38. void apply(int v){
  39.     seg[v].h = (seg[2 * v].h + seg[2 * v + 1].h) % mod;
  40.  
  41.     if(seg[2 * v].mn1 == seg[2 * v + 1].mn1){
  42.         seg[v].cnt = seg[2 * v].cnt + seg[2 * v + 1].cnt;
  43.         seg[v].mn1 = seg[2 * v].mn1;
  44.         seg[v].mn2 = min(seg[2 * v].mn2, seg[2 * v + 1].mn2);
  45.     }else if(seg[2 * v].mn1 < seg[2 * v + 1].mn1){
  46.         seg[v].mn1 = seg[2 * v].mn1; 
  47.         seg[v].cnt = seg[2 * v].cnt;
  48.         seg[v].mn2 = min(seg[2 * v].mn2, seg[2 * v + 1].mn1);
  49.     }else{
  50.         seg[v].mn1 = seg[2 * v + 1].mn1; 
  51.         seg[v].cnt = seg[2 * v + 1].cnt;
  52.         seg[v].mn2 = min(seg[2 * v + 1].mn2, seg[2 * v].mn1);
  53.     }
  54. }
  55.  
  56. void ustaw(int v, int l, int r, ll val){
  57.     if(val == 0) return;
  58.  
  59.     ll dl = r - l + 1;
  60.     seg[v].h = (dl * potega(X, val)) % mod;
  61.     seg[v].mn1 = val;
  62.     seg[v].mn2 = 2e18;
  63.     seg[v].cnt = dl;
  64.  
  65.     seg[v].lazy_ustaw = val;
  66.     seg[v].lazy_add = 0;
  67. }
  68.  
  69. void dodaj(int v, int l, int r, ll val){
  70.     if(val == 0) return;
  71.  
  72.     if(seg[v].lazy_ustaw){
  73.         ustaw(v, l, r, val + seg[v].lazy_ustaw);
  74.         return;
  75.     }
  76.  
  77.     seg[v].h = (seg[v].h * potega(X, val)) % mod;
  78.  
  79.     seg[v].mn1 += val;
  80.     if(seg[v].mn2 != 2e18) seg[v].mn2 += val;
  81.     seg[v].lazy_add += val;
  82. }
  83.  
  84. void maxuj(int v, int l, int r, ll val){
  85.     if(val <= seg[v].mn1) return;
  86.  
  87.     ll stary_hash_min = (seg[v].cnt * potega(X, seg[v].mn1)) % mod;
  88.     ll nowy_hash_min = (seg[v].cnt * potega(X, val)) % mod;
  89.  
  90.     seg[v].h = (seg[v].h - stary_hash_min + nowy_hash_min + mod) % mod;
  91.  
  92.     seg[v].mn1 = val;
  93.     if(seg[v].lazy_ustaw != 0) seg[v].lazy_ustaw = max(val, seg[v].lazy_ustaw);
  94. }
  95.  
  96. void push(int v, int l, int r){
  97.     if(l == r) return;
  98.  
  99.     int mid = (l + r) / 2;
  100.     if(seg[v].lazy_ustaw != 0){
  101.         ustaw(2 * v, l, mid, seg[v].lazy_ustaw);
  102.         ustaw(2 * v + 1, mid + 1, r, seg[v].lazy_ustaw);
  103.         seg[v].lazy_ustaw = 0;
  104.     }
  105.  
  106.     if(seg[v].lazy_add != 0){
  107.         dodaj(2 * v, l, mid, seg[v].lazy_add);
  108.         dodaj(2 * v + 1, mid + 1, r, seg[v].lazy_add);
  109.         seg[v].lazy_add = 0;
  110.     }
  111.  
  112.     if(seg[2 * v].mn1 < seg[v].mn1) maxuj(2 * v, l, mid, seg[v].mn1);
  113.     if(seg[2 * v + 1].mn1 < seg[v].mn1) maxuj(2 * v + 1, mid + 1, r, seg[v].mn1);
  114. }
  115.  
  116. void build(int v, int l, int r){
  117.     if(l == r){
  118.         seg[v].h = potega(X, tab[l]);
  119.  
  120.         seg[v].mn1 = tab[l];
  121.         seg[v].cnt = 1; 
  122.         seg[v].mn2 = 2e18;
  123.  
  124.         seg[v].lazy_ustaw = 0; 
  125.         seg[v].lazy_add = 0;
  126.         return;
  127.     }
  128.  
  129.     int mid = (l + r) / 2;
  130.     build(2 * v, l, mid);
  131.     build(2 * v + 1, mid + 1, r);
  132.  
  133.     apply(v);
  134. }
  135.  
  136. void upd_dod(int v, int l, int r, int ql, int qr, ll val){
  137.     if(ql > qr || qr < l || ql > r) return;
  138.     if(ql <= l && r <= qr){
  139.         dodaj(v, l, r, val);
  140.         return;
  141.     }
  142.  
  143.     push(v, l, r);
  144.  
  145.     int mid = (l + r) / 2;
  146.     upd_dod(2 * v, l, mid, ql, qr, val); 
  147.     upd_dod(2 * v + 1, mid + 1, r, ql, qr, val);
  148.  
  149.     apply(v);
  150. }
  151.  
  152. void upd_ustaw(int v, int l, int r, int ql, int qr, ll val){
  153.     if(ql > qr || qr < l || ql > r) return;
  154.     if(ql <= l && r <= qr){
  155.         ustaw(v, l, r, val);
  156.         return;
  157.     }
  158.  
  159.     push(v, l, r);
  160.  
  161.     int mid = (l + r) / 2;
  162.     upd_ustaw(2 * v, l, mid, ql, qr, val); 
  163.     upd_ustaw(2 * v + 1, mid + 1, r, ql, qr, val);
  164.  
  165.     apply(v);
  166. }
  167.  
  168. void upd_mx(int v, int l, int r, int ql, int qr, ll val){
  169.     if(ql > qr || qr < l || ql > r) return;
  170.     if(val <= seg[v].mn1) return;
  171.     if(ql <= l && r <= qr && seg[v].mn2 > val){
  172.         maxuj(v, l, r, val);
  173.         return;
  174.     }
  175.  
  176.     push(v, l, r);
  177.  
  178.     int mid = (l + r) / 2;
  179.     upd_mx(2 * v, l, mid, ql, qr, val); 
  180.     upd_mx(2 * v + 1, mid + 1, r, ql, qr, val);
  181.  
  182.     apply(v);
  183. }
  184.  
  185. ll query(int v, int l, int r, int ql, int qr){
  186.     if(ql > qr || qr < l || ql > r){
  187.         return 0;
  188.     }
  189.     if(ql <= l && r <= qr){
  190.         return seg[v].h;
  191.     }
  192.  
  193.     push(v, l, r);
  194.  
  195.     int mid = (l + r) / 2;
  196.     ll lewy = query(2 * v, l, mid, ql, qr);
  197.     ll prawy = query(2 * v + 1, mid + 1, r, ql, qr);
  198.  
  199.     return (lewy + prawy) % mod;
  200. }
  201.  
  202. int main(){
  203.     ios_base::sync_with_stdio(0);
  204.     cin.tie(0);
  205.  
  206.     int n, q;
  207.     cin >> n >> q;
  208.  
  209.     for(int i = 1; i <= n; i++) cin >> tab[i];
  210.     build(1, 1, n);
  211.  
  212.     while(q--){
  213.         int typ; cin >> typ;
  214.         if(typ == 1){
  215.             int l, r; ll k;
  216.             cin >> l >> r >> k;
  217.             upd_ustaw(1, 1, n, l, r, k);
  218.         }else if(typ == 2){
  219.             int l, r; ll k;
  220.             cin >> l >> r >> k;
  221.             upd_dod(1, 1, n, l, r, k);
  222.         }else if(typ == 3){
  223.             int l, r; ll k;
  224.             cin >> l >> r >> k;
  225.             upd_mx(1, 1, n, l, r, k);
  226.         }else{
  227.             int l1, r1, l2, r2;
  228.             cin >> l1 >> r1 >> l2 >> r2;
  229.             if(query(1, 1, n, l1, r1) == query(1, 1, n, l2, r2)) cout << "TAK\n";
  230.             else cout << "NIE\n";
  231.         }
  232.     }
  233.  
  234.     return 0;
  235. }
Success #stdin #stdout 0.01s 5556KB
comments (?)
stdin
copy 
5 8
5 10 15 20 25
0 1 2 2 3
1 1 2 15
0 1 2 2 3
2 4 5 10
3 1 3 20
0 1 3 2 4
1 4 4 20
0 1 3 2 4
stdout
copy 
NIE
TAK
NIE
TAK
https://ideone.com/p4SkM5
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!