Algorithm-Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub UScuber/Algorithm-Library

:heavy_check_mark: test/yosupo/Data-Structure/Range-Reverse-Range-Sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"

#include "../../../template/template.hpp"

#include "../../../data-structure/Treap.hpp"
#include "../../../others/fastIO.hpp"

int main(){
  int n,q;
  cin >> n >> q;
  SumAddQuery<ll,ll> tr;
  rep(i, n){
    int a;
    cin >> a;
    tr.insert(i, a);
  }
  rep(_, q){
    int t,l,r;
    cin >> t >> l >> r;
    if(t == 0){
      tr.reverse(l, r);
    }else{
      cout << tr.query(l, r) << '\n';
    }
  }
}
#line 1 "test/yosupo/Data-Structure/Range-Reverse-Range-Sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"

#line 1 "template/template.hpp"
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/yosupo/Data-Structure/Range-Reverse-Range-Sum.test.cpp"

#line 1 "data-structure/Treap.hpp"
#include <random>
#include <chrono>
// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
struct BaseImplicitTreap {
private:
  virtual T0 f0(const T0 &, const T0 &) = 0;
  const T0 u0;
  virtual T1 f1(const T1 &, const T1 &) = 0;
  const T1 u1;
  virtual T0 g(const T0 &, const T1 &) = 0;
  virtual T1 p(const T1 &, const int) = 0;

  struct xorshift {
    uint64_t x;
    xorshift(){
      mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
      x = rnd();
      for(int i = 0; i < 100; i++){
        random();
      }
    }
    uint64_t random(){
      x = x ^ (x << 7);
      return x = x ^ (x >> 9);
    }
  } rnd;

  struct Node {
    T0 value, acc;
    T1 lazy;
    int priority, cnt;
    bool rev;
    Node *l, *r;
    Node(const T0 &value_, const int priority_, const T0 &u0_, const T1 &u1_)
        : value(value_), acc(u0_), lazy(u1_), priority(priority_), cnt(1), rev(false), l(nullptr), r(nullptr){}
  } *root = nullptr;

  using Tree = Node *;

  inline int cnt(Tree t) const noexcept{ return t ? t->cnt : 0; }
  inline T0 acc(Tree t) const noexcept{ return t ? t->acc : u0; }
  void update_cnt(Tree t){
    if(t) t->cnt = 1 + cnt(t->l) + cnt(t->r);
  }
  void update_acc(Tree t){
    if(t) t->acc = f0(acc(t->l), f0(t->value, acc(t->r)));
  }
  void pushup(Tree t){ update_cnt(t), update_acc(t); }
  void pushdown(Tree t){
    if(t && t->rev){
      t->rev = false;
      swap(t->l, t->r);
      if(t->l) t->l->rev ^= 1;
      if(t->r) t->r->rev ^= 1;
    }
    if(t && t->lazy != u1){
      if(t->l){
        t->l->lazy = f1(t->l->lazy, t->lazy);
        t->l->acc = g(t->l->acc, p(t->lazy, cnt(t->l)));
      }
      if(t->r){
        t->r->lazy = f1(t->r->lazy, t->lazy);
        t->r->acc = g(t->r->acc, p(t->lazy, cnt(t->r)));
      }
      t->value = g(t->value, p(t->lazy, 1));
      t->lazy = u1;
    }
    pushup(t);
  }
  void split(Tree t, int key, Tree &l, Tree &r){
    if(!t){
      l = r = nullptr;
      return;
    }
    pushdown(t);
    int implicit_key = cnt(t->l) + 1;
    if(key < implicit_key){
      split(t->l, key, l, t->l), r = t;
    }else{
      split(t->r, key - implicit_key, t->r, r), l = t;
    }
    pushup(t);
  }
  void insert(Tree &t, int key, Tree item){
    Tree t1, t2;
    split(t, key, t1, t2);
    merge(t1, t1, item);
    merge(t, t1, t2);
  }
  void merge(Tree &t, Tree l, Tree r){
    pushdown(l);
    pushdown(r);
    if(!l || !r){
      t = l ? l : r;
    }else if(l->priority > r->priority){
      merge(l->r, l->r, r), t = l;
    }else{
      merge(r->l, l, r->l), t = r;
    }
    pushup(t);
  }
  void erase(Tree &t, int key){
    Tree t1, t2, t3;
    split(t, key + 1, t1, t2);
    split(t1, key, t1, t3);
    merge(t, t1, t2);
  }
  void update(Tree t, int l, int r, T1 x){
    if(l >= r) return;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    t2->lazy = f1(t2->lazy, x);
    t2->acc = g(t2->acc, p(x, cnt(t2)));
    merge(t2, t2, t3);
    merge(t, t1, t2);
  }
  T0 query(Tree t, int l, int r){
    if(l == r) return u0;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    T0 ret = t2->acc;
    merge(t2, t2, t3);
    merge(t, t1, t2);
    return ret;
  }
  // [l, r)の中で左から何番目か
  int find(Tree t, T0 x, int offset, bool left = true){
    if(f0(t->acc, x) == x){
      return -1;
    }else{
      if(left){
        if(t->l && f0(t->l->acc, x) != x){
          return find(t->l, x, offset, left);
        }else{
          return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left);
        }
      }else{
        if(t->r && f0(t->r->acc, x) != x){
          return find(t->r, x, offset + cnt(t->l) + 1, left);
        }else{
          return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left);
        }
      }
    }
  }
  void reverse(Tree t, int l, int r){
    if(l >= r) return;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    t2->rev ^= 1;
    merge(t2, t2, t3);
    merge(t, t1, t2);
  }
  // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様
  void rotate(Tree t, int l, int m, int r){
    reverse(t, l, r);
    reverse(t, l, l + r - m);
    reverse(t, l + r - m, r);
  }
  void dump(Tree t){
    if(!t) return;
    pushdown(t);
    dump(t->l);
    cout << t->value << " ";
    dump(t->r);
  }
public:
  BaseImplicitTreap(const T0 &u0_, const T1 &u1_) : u0(u0_), u1(u1_){}
  void set_by_vector(const vector<T0> &a){
    for(int i = 0; i < (int)a.size(); i++){
      insert(i, a[i]);
    }
  }
  int size(){ return cnt(root); }
  void insert(int pos, const T0 &x){ insert(root, pos, new Node(x, rnd.random(), u0, u1)); }
  void update(int l, int r, const T1 &x){ update(root, l, r, x); }
  T0 query(int l, int r){ return query(root, l, r); }
  // 二分探索。[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のもの。存在しない場合は-1
  // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す
  int binary_search(int l, int r, const T0 &x, bool left = true){
    if(l >= r) return -1;
    Tree t1, t2, t3;
    split(root, l, t1, t2);
    split(t2, r - l, t2, t3);
    int ret = find(t2, x, l, left);
    merge(t2, t2, t3);
    merge(root, t1, t2);
    return ret;
  }
  void erase(int pos){ erase(root, pos); }
  void reverse(int l, int r){ reverse(root, l, r); }
  void rotate(int l, int m, int r){ rotate(root, l, m, r); }
  void dump(){
    dump(root);
    cout << "\n";
  }
  T0 operator[](int pos){ return query(pos, pos + 1); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseImplicitTreap<T0, T1> {
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()){}
  T0 f0(const T0 &x, const T0 &y) override{ return min(x, y); }
  T1 f1(const T1 &x, const T1 &y) override{ return y == numeric_limits<T1>::min() ? x : y; }
  T0 g(const T0 &x, const T1 &y) override{ return y == numeric_limits<T1>::min() ? x : y; }
  T1 p(const T1 &x, const int len) override{ return x; }
};

template <class T0, class T1>
struct SumAddQuery : public BaseImplicitTreap<T0, T1> {
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  SumAddQuery() : SumAddQuery(0, 0){}
  T0 f0(const T0 &x, const T0 &y) override{ return x + y; }
  T1 f1(const T1 &x, const T1 &y) override{ return x + y; }
  T0 g(const T0 &x, const T1 &y) override{ return x + y; }
  T1 p(const T1 &x, const int len) override{ return x * len; }
};

template <class T0, class T1>
struct MinAddQuery : public BaseImplicitTreap<T0, T1> {
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0){}
  T0 f0(const T0 &x, const T0 &y) override{ return min(x, y); }
  T1 f1(const T1 &x, const T1 &y) override{ return x + y; }
  T0 g(const T0 &x, const T1 &y) override{ return x + y; }
  T1 p(const T1 &x, const int len) override{ return x; }
};

template <class T0, class T1>
struct SumUpdateQuery : public BaseImplicitTreap<T0, T1> {
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()){}
  T0 f0(const T0 &x, const T0 &y) override{ return x + y; }
  T1 f1(const T1 &x, const T1 &y) override{ return y == numeric_limits<T1>::min() ? x : y; }
  T0 g(const T0 &x, const T1 &y) override{ return y == numeric_limits<T1>::min() ? x : y; }
  T1 p(const T1 &x, const int len) override{ return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};

template <class T0>
struct SumAffineQuery : public BaseImplicitTreap<T0, pair<T0, T0>> {
  using T1 = pair<T0, T0>; // first * x + second
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  SumAffineQuery() : SumAffineQuery(0, { 1, 0 }){}
  T0 f0(const T0 &x, const T0 &y) override{ return x + y; }
  T1 f1(const T1 &x, const T1 &y) override{ return {x.first * y.first, x.second * y.first + y.second}; }
  T0 g(const T0 &x, const T1 &y) override{ return y.first * x + y.second; }
  T1 p(const T1 &x, const int len) override{ return {x.first, x.second * len}; }
};

template <class T>
struct MinmaxAffineQuery : public BaseImplicitTreap<pair<T, T>, pair<T, T>> {
  using T0 = pair<T, T>; // {min, max}
  using T1 = pair<T, T>; // first * x + second
  using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
  MinmaxAffineQuery() : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, { 1, 0 }){}
  T0 f0(const T0 &x, const T0 &y) override{ return { min(x.first, y.first), max(x.second, y.second) }; }
  T1 f1(const T1 &x, const T1 &y) override{ return { x.first * y.first, x.second * y.first + y.second }; }
  T0 g(const T0 &x, const T1 &y) override{
    T0 ret = { x.first * y.first + y.second, x.second * y.first + y.second };
    if(y.first < 0) swap(ret.first, ret.second);
    return ret;
  }
  T1 p(const T1 &x, int len) override{ return x; }
};
#line 1 "others/fastIO.hpp"
namespace FastIO {
struct PreCalc {
  char num[10000 * 4];
  constexpr PreCalc() : num(){
    for(int i = 0; i < 10000; i++){
      int t = i;
      for(int j = 3; j >= 0; j--){
        num[i*4 + j] = (t % 10) + '0';
        t /= 10;
      }
    }
  }
};
static constexpr PreCalc pr;
struct FastIO {
  template <class T>
  using enable_if_integer = enable_if_t<is_integral<T>::value || is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value>;
  static constexpr int buf_size = 1 << 20;
  static constexpr int rem = 1 << 6;
  char in_buf[buf_size], *in_cur = in_buf + buf_size;
  char out_buf[buf_size], *out_cur = out_buf;
  FastIO(){ load(); }
  ~FastIO(){ flush(); }
  void load(){
    const int len = in_buf + buf_size - in_cur;
    memmove(in_buf, in_cur, len);
    in_cur = in_buf;
    fread(in_buf + len, 1, buf_size - len, stdin);
  }
  void flush(){
    fwrite(out_buf, 1, out_cur - out_buf, stdout);
    out_cur = out_buf;
  }
  void through(){
    if(in_cur - in_buf >= buf_size - rem) load();
    while(*in_cur <= ' ') in_cur++;
    assert(in_buf <= in_cur && in_cur < in_buf + buf_size);
  }
  #define gc() (*in_cur++)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void read(T &x){
    through();
    bool neg = false;
    int c = gc();
    if(c == '-') neg = true, c = gc();
    x = c^'0'; c = gc();
    while(c >= '0' && c <= '9') x = x*10 + (c^'0'), c = gc();
    if(neg) x = -x;
  }
  inline void read(string &x){
    through();
    x.clear();
    while(true){
      char *p = in_cur;
      while(*p > ' ' && p - in_buf < buf_size - rem) p++;
      copy(in_cur, p, back_inserter(x));
      in_cur = p;
      if(*p <= ' ') break;
      load();
    }
  }
  inline void read(char &x){
    through();
    x = gc();
  }
  #undef gc
  #define pc(c) *out_cur++ = (c)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void out(T x){
    static constexpr int tmp_size = sizeof(T)*5/2;
    static char tmp[tmp_size];
    if(out_cur - out_buf >= buf_size - rem) flush();
    if(!x){ pc('0'); return; }
    if(x < 0){ pc('-'); x = -x; }
    int idx = tmp_size;
    while(x >= 10000){
      idx -= 4;
      memcpy(tmp + idx, pr.num + (x % 10000)*4, 4);
      x /= 10000;
    }
    if(x < 100){
      if(x < 10){
        pc(x + '0');
      }else{
        pc(x/10 + '0');
        pc(x%10 + '0');
      }
    }else{
      if(x < 1000){
        memcpy(out_cur, pr.num + x*4 + 1, 3);
        out_cur += 3;
      }else{
        memcpy(out_cur, pr.num + x*4, 4);
        out_cur += 4;
      }
    }
    memcpy(out_cur, tmp + idx, tmp_size - idx);
    out_cur += tmp_size - idx;
  }
  inline void out(const string &s){
    flush();
    fwrite(s.c_str(), 1, s.size(), stdout);
  }
  inline void out(const char c){
    if(out_cur - out_buf >= buf_size - rem) flush();
    pc(c);
  }
  #undef pc
  template <class T>
  friend FastIO &operator>>(FastIO &io, T &x){
    io.read(x);
    return io;
  }
  template <class T>
  friend FastIO &operator<<(FastIO &io, const T &x){
    io.out(x);
    return io;
  }
};
FastIO io;
} // namespace FastIO

using FastIO::io;
#define cin io
#define cout io
#line 7 "test/yosupo/Data-Structure/Range-Reverse-Range-Sum.test.cpp"

int main(){
  int n,q;
  cin >> n >> q;
  SumAddQuery<ll,ll> tr;
  rep(i, n){
    int a;
    cin >> a;
    tr.insert(i, a);
  }
  rep(_, q){
    int t,l,r;
    cin >> t >> l >> r;
    if(t == 0){
      tr.reverse(l, r);
    }else{
      cout << tr.query(l, r) << '\n';
    }
  }
}
Back to top page