#line 1 "verify/yosupo/data-structure/link-cut-tree/reversible-splay-tree/range_reverse_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}
int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
vector<int> p(SZ(a));
iota(ALL(p),0);
stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
return p;
}
template<class T,size_t D=0>
struct VecBuilder{
array<size_t,D> d;
VecBuilder<T,D+1> operator[](size_t n)const{
VecBuilder<T,D+1> res{};
for(size_t i=0;i<D;i++)res.d[i]=d[i];
res.d[D]=n;
return res;
}
template<size_t I=0>
auto build(const T &x)const{
if constexpr(I+1==D)return vector<T>(d[I],x);
else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
}
auto operator()(const T &x=T())const{
static_assert(D>0);
return build(x);
}
};
template<class T>
inline constexpr VecBuilder<T> VEC{};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "data-structure/link-cut-tree/splay-tree-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-13
* Description: Splay Tree. splay(u) will make node u be the root of the tree in amortized O(log n) time.
*/
template<class Node>
struct SplayTreeBase{
using Ptr = Node*;
bool is_root(Ptr t){
return !(t->p)||(t->p->l!=t&&t->p->r!=t);
} // The parent of the root stores the path parant in link cut tree.
int size(Ptr t){
return t?t->size:0;
}
virtual void push(Ptr t){};
virtual void pull(Ptr t){};
int pos(Ptr t){
if(t->p){
if(t->p->l==t)return -1;
if(t->p->r==t)return 1;
}
return 0;
}
void rotate(Ptr t){
Ptr x=t->p,y=x->p;
if(pos(t)==-1){
if((x->l=t->r))t->r->p=x;
t->r=x,x->p=t;
}else{
if((x->r=t->l))t->l->p=x;
t->l=x,x->p=t;
}
pull(x),pull(t);
if((t->p=y)){
if(y->l==x)y->l=t;
if(y->r==x)y->r=t;
}
}
void splay(Ptr t){
if(!t)return;
push(t);
while(!is_root(t)){
Ptr x=t->p;
if(is_root(x)){
push(x),push(t);
rotate(t);
}else{
Ptr y=x->p;
push(y),push(x),push(t);
if(pos(x)==pos(t))rotate(x),rotate(t);
else rotate(t),rotate(t);
}
}
}
void splay_kth(Ptr &t,int k){
assert(0<=k&&k<size(t));
while(true){
push(t);
if(k<size(t->l))t=t->l;
else if(size(t->l)==k)break;
else{
k-=size(t->l)+1;
t=t->r;
}
}
splay(t);
}
Ptr get_first(Ptr t){
while(t->l)push(t),t=t->l;
splay(t);
return t;
}
Ptr get_last(Ptr t){
while(t->r)push(t),t=t->r;
splay(t);
return t;
}
Ptr merge(Ptr l,Ptr r){
splay(l),splay(r);
if(!l)return r;
if(!r)return l;
l=get_last(l);
l->r=r;
r->p=l;
pull(l);
return l;
}
pair<Ptr,Ptr> split(Ptr t,int k){
if(!t)return {nullptr,nullptr};
if(k==0)return {nullptr,t};
if(k==size(t))return {t,nullptr};
splay_kth(t,k-1);
Ptr x=t->r;
t->r=x->p=nullptr;
pull(t);
return {t,x};
}
void insert(Ptr &t,int k,Ptr v){
splay(t);
auto x=split(t,k);
t=merge(merge(x.first,v),x.second);
}
void erase(Ptr &t,int k){
splay(t);
auto x=split(t,k);
auto y=split(x.second,1);
// delete y.first;
t=merge(x.first,y.second);
}
template<class T>
Ptr build(const vector<T> &v){
if(v.empty())return nullptr;
function<Ptr(int,int)> build=[&](int l,int r){
if(l==r)return new Node(v[l]);
int m=(l+r)/2;
return merge(build(l,m),build(m+1,r));
};
return build(0,v.size()-1);
}
};
#line 2 "data-structure/link-cut-tree/reversible-bbst.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-13
* Description: Revesible BBST Base.
*/
template<class Tree,class Node,class Monoid>
struct ReversibleBBST:Tree{
using Tree::merge;
using Tree::split;
using typename Tree::Ptr;
using T = typename Monoid::value_type;
ReversibleBBST()=default;
T sum(Ptr t){
return t?t->sum:T();
}
void pull(Ptr t){
if(!t)return;
t->size=1;
t->sum=t->val;
t->revsum=t->val;
if(t->l){
t->size+=t->l->size;
t->sum=Monoid::op(t->l->sum,t->sum);
t->revsum=Monoid::op(t->revsum,t->l->revsum);
}
if(t->r){
t->size+=t->r->size;
t->sum=Monoid::op(t->sum,t->r->sum);
t->revsum=Monoid::op(t->r->revsum,t->revsum);
}
}
void push(Ptr t){
if(!t)return;
if(t->rev){
toggle(t->l);
toggle(t->r);
t->rev=false;
}
}
void toggle(Ptr t){
if(!t)return;
swap(t->l,t->r);
swap(t->sum,t->revsum);
t->rev^=true;
}
T query(Ptr &t,int l,int r){
if(l>r)return T();
auto x=split(t,l);
auto y=split(x.second,r-l+1);
T res=sum(y.first);
t=merge(x.first,merge(y.first,y.second));
return res;
}
void reverse(Ptr &t,int l,int r){
if(l>r)return;
auto x=split(t,l);
auto y=split(x.second,r-l+1);
toggle(y.first);
t=merge(x.first,merge(y.first,y.second));
}
};
#line 4 "data-structure/link-cut-tree/reversible-splay-tree.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-13
* Description: Reversible Splay Tree.
*/
template<class T>
struct ReversibleSplayTreeNode{
using Ptr = ReversibleSplayTreeNode*;
using value_type = T;
Ptr l,r,p;
T val,sum,revsum;
int size;
bool rev;
ReversibleSplayTreeNode(const T &_val)
:l(),r(),p(),val(_val),sum(_val),revsum(_val),size(1),rev(false){}
};
template<class Monoid>
struct ReversibleSplayTree
: ReversibleBBST<SplayTreeBase<ReversibleSplayTreeNode<typename Monoid::value_type>>,
ReversibleSplayTreeNode<typename Monoid::value_type>,Monoid>{
using Node = ReversibleSplayTreeNode<typename Monoid::value_type>;
};
#line 2 "group/monoid/add.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-14
* Description: Add Monoid class.
*/
template<class T>
struct AddMonoid{
using value_type = T;
static constexpr T op(const T &x,const T &y){return x+y;}
static constexpr T inverse(const T &x){return -x;}
static constexpr T unit(){return T(0);}
};
#line 5 "verify/yosupo/data-structure/link-cut-tree/reversible-splay-tree/range_reverse_range_sum.test.cpp"
using Monoid = AddMonoid<ll>;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,q;
cin >> n >> q;
vector<ll> a(n);
for(auto &x:a)cin >> x;
using Tree = ReversibleSplayTree<Monoid>;
using Ptr = Tree::Node*;
Tree s;
Ptr root=s.build(a);
while(q--){
int op;
cin >> op;
if(op){
int l,r;
cin >> l >> r;
cout << s.query(root,l,r-1) << "\n";
}else{
int l,r;
cin >> l >> r;
s.reverse(root,l,r-1);
}
}
}
verify/yosupo/data-structure/link-cut-tree/reversible-splay-tree/range_reverse_range_sum.test.cpp