fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using pii = pair<ull, ull>;
  7.  
  8. template<typename X, typename Y>
  9. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  10. template<typename X, typename Y>
  11. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  12.  
  13. const int N = 1e5+5;
  14.  
  15. int n, q, a[N];
  16.  
  17. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  18.  
  19. map<int, ull> H, _H;
  20.  
  21. ull bit[N], _bit[N];
  22.  
  23. void init(int x) {
  24.     if (H.find(x) == H.end()) {
  25.         H[x] = rng();
  26.         _H[x] = rng();
  27.     }
  28. }
  29.  
  30. void add(int p, int v, int sign) {
  31.     for (; p <= n; p += p & -p) {
  32.         bit[p] += H[v] * sign;
  33.         _bit[p] += _H[v] * sign;
  34.     }
  35. }
  36.  
  37. pii get(int p) {
  38.     ull res = 0, _res = 0;
  39.     for (; p > 0; p -= p & -p) {
  40.         res += bit[p];
  41.         _res += _bit[p];
  42.     }
  43.     return {res, _res};
  44. }
  45.  
  46. pii query(int l, int r) {
  47.     pii x = get(l - 1), y = get(r);
  48.     return {y.first - x.first, y.second - x.second};
  49. }
  50.  
  51. void solve() {
  52.     cin >> n >> q;
  53.     for (int i = 1; i <= n; i++) {
  54.         cin >> a[i]; init(a[i]);
  55.         add(i, a[i], 1);
  56.     }
  57.     while (q--) {
  58.         int type; cin >> type;
  59.         if (type == 1) {
  60.             int k, x; cin >> k >> x;
  61.             add(k, a[k], -1);
  62.             a[k] = x; init(x);
  63.             add(k, a[k], 1);
  64.         } else if (type == 2) {
  65.             int l, r, u, v; cin >> l >> r >> u >> v;
  66.             if (r - l != v - u) {
  67.                 cout << "NO\n";
  68.                 continue;
  69.             }
  70.             pii h1 = query(l, r), h2 = query(u, v);
  71.             if (h1.first == h2.first && h1.second == h2.second) cout << "YES\n";
  72.             else cout << "NO\n";
  73.         }
  74.     }
  75. }
  76.  
  77. int main() {
  78.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  79.  
  80.     #define TASK "ISOMERS"
  81.     if (fopen(TASK".INP", "r")) {
  82.         freopen(TASK".INP", "r", stdin);
  83.         freopen(TASK".OUT", "w", stdout);
  84.     }
  85.  
  86.     int tests = 1; // cin >> tests;
  87.     while (tests--) solve();
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/clM8Cv
language:
C++14 (gcc 8.3)
created:
1 hour 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!