結果

問題 No.925 紲星 Extra
コンテスト
ユーザー hos.lyric
提出日時 2019-11-09 00:45:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,698 ms / 10,000 ms
コード長 5,972 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 119,248 KB
実行使用メモリ 65,408 KB
最終ジャッジ日時 2024-09-15 03:30:24
合計ジャッジ時間 71,453 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }

namespace RBST {

unsigned xrand() {
  static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}
constexpr int MAX = 20000010;
int n, l[MAX], r[MAX], size[MAX];
Int key[MAX], sum[MAX];
int node(Int key_) {
  n[l] = n[r] = -1;
  n[size] = 1;
  n[key] = n[sum] = key_;
  return n++;
}
int change(int a, int l_, int r_) {
  a[l] = l_;
  a[r] = r_;
  a[size] = (~l_ ? l_[size] : 0) + 1 + (~r_ ? r_[size] : 0);
  a[sum] = (~l_ ? l_[sum] : 0) + a[key] + (~r_ ? r_[sum] : 0);
  return a;
}
int merge(int a, int b) {
  if (!~a) return b;
  if (!~b) return a;
  if ((int)(xrand() % (a[size] + b[size])) < a[size]) {
    return change(a, a[l], merge(a[r], b));
  } else {
    return change(b, merge(a, b[l]), b[r]);
  }
}
pair<int, int> splitKey(int a, Int key_) {
  if (!~a) return {-1, -1};
  if (key_ <= a[key]) {
    const auto l_ = splitKey(a[l], key_);
    return {l_.first, change(a, l_.second, a[r])};
  } else {
    const auto r_ = splitKey(a[r], key_);
    return {change(a, a[l], r_.first), r_.second};
  }
}
pair<int, int> splitHead(int a) {
  if (~a[l]) {
    const auto l_ = splitHead(a[l]);
    return {l_.first, change(a, l_.second, a[r])};
  } else {
    const int r_ = a[r];
    return {change(a, -1, -1), r_};
  }
}
int insert(int a, Int key_) {
  const auto sp = splitKey(a, key_);
  return merge(merge(sp.first, node(key_)), sp.second);
}
int eraseKey(int a, Int key_) {
  const auto sp = splitKey(a, key_);
  return merge(sp.first, splitHead(sp.second).second);
}
pair<int, Int> sumLessThan(int a, Int key_) {
  int ret0 = 0;
  Int ret1 = 0;
  for (; ~a; ) {
    if (key_ <= a[key]) {
      a = a[l];
    } else {
      if (a[l]) {
        ret0 += a[l][size];
        ret1 += a[l][sum];
      }
      ret0 += 1;
      ret1 += a[key];
      a = a[r];
    }
  }
  return {ret0, ret1};
}
void print(int a) {
  if (!~a) return;
  printf("[");
  print(a[l]);
  printf(" (%d;%lld) ", a, a[key]);
  print(a[r]);
  printf("]");
}

}  // RBST

constexpr int MAX_N = 70010;
constexpr int MASK_16 = (1 << 16) - 1;
constexpr Int MASK_40 = (1LL << 40) - 1;

int N, Q;
Int A[MAX_N];

int segN;
int seg[MAX_N << 2];

pair<int, Int> get(int a, int b) {
  int ret0 = 0;
  Int ret1 = 0;
  for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
    if (a & 1) {
      ret0 += seg[a][RBST::size];
      ret1 += seg[a][RBST::sum];
      ++a;
    }
    if (b & 1) {
      --b;
      ret0 += seg[b][RBST::size];
      ret1 += seg[b][RBST::sum];
    }
  }
  return {ret0, ret1};
}
pair<int, Int> get(int a, int b, Int key_) {
  int ret0 = 0;
  Int ret1 = 0;
  for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
    if (a & 1) {
      const auto res = RBST::sumLessThan(seg[a++], key_);
      ret0 += res.first;
      ret1 += res.second;
    }
    if (b & 1) {
      const auto res = RBST::sumLessThan(seg[--b], key_);
      ret0 += res.first;
      ret1 += res.second;
    }
  }
  return {ret0, ret1};
}

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    
    RBST::n = 0;
    for (segN = 1; segN < N; segN <<= 1) {}
    fill(seg, seg + (segN << 1), -1);
    for (int i = 0; i < N; ++i) {
      for (int a = segN + i; a; a >>= 1) {
        seg[a] = RBST::insert(seg[a], A[i]);
      }
    }
// for(int a=1;a<segN<<1;++a){printf("seg[%d] = ",a);RBST::print(seg[a]);puts("");}
    
    Int s = 0;
    for (int q = 0; q < Q; ++q) {
      int typ;
      scanf("%d", &typ);
      switch (typ) {
        case 1: {
          int x;
          Int y;
          scanf("%d%lld", &x, &y);
          x ^= (s & MASK_16);
          y ^= (s & MASK_40);
          --x;
// cerr<<"query 1 "<<x<<" "<<y<<endl;
          assert(0 <= x && x < N);
          for (int a = segN + x; a; a >>= 1) {
            seg[a] = RBST::insert(RBST::eraseKey(seg[a], A[x]), y);
          }
          A[x] = y;
        } break;
        case 2: {
          int l, r;
          scanf("%d%d", &l, &r);
          l ^= (s & MASK_16);
          r ^= (s & MASK_16);
          if (l > r) {
            swap(l, r);
          }
          --l;
          assert(0 <= l && l < r && r <= N);
// cerr<<"query 2 "<<l<<" "<<r<<endl;
          // binary search O(log max A_i) tries -> O(log N) tries
          Int median = 0;
          for (int a = seg[1]; ~a; ) {
            if (get(l, r, a[RBST::key]).first >= (r - l + 1) / 2) {
              a = a[RBST::l];
            } else {
              chmax(median, a[RBST::key]);
              a = a[RBST::r];
            }
          }
// cerr<<"  median = "<<median<<endl;
          const auto all = get(l, r);
          const auto res = get(l, r, median);
          Int ans = all.second - all.first * median;
          ans -= 2 * (res.second - res.first * median);
          printf("%lld\n", ans);
          s ^= ans;
        } break;
        default: assert(false);
      }
    }
  }
  return 0;
}
0