#line 1 "verify/yosupo/data-structure/bbst/treap/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/bbst/treap.hpp"
template<class Monoid>
struct Treap{
using T = typename Monoid::value_type;
struct Node{
int l,r,sz,prio;
bool rev;
T val,sum,revsum;
};
vector<Node> t;
Treap(int n=0){
t.reserve(n+1);
t.push_back(Node{0,0,0,0,false,Monoid::unit(),Monoid::unit(),Monoid::unit()});
}
int new_node(const T &v){
t.push_back(Node{0,0,1,rng(),false,v,v,v});
return SZ(t)-1;
}
int size(int x){return t[x].sz;}
T sum(int x){return t[x].sum;}
void pull(int x){
Node &v=t[x];
v.sz=t[v.l].sz+1+t[v.r].sz;
v.sum=Monoid::op(Monoid::op(t[v.l].sum,v.val),t[v.r].sum);
v.revsum=Monoid::op(Monoid::op(t[v.r].revsum,v.val),t[v.l].revsum);
}
void toggle(int x){
if(!x)return;
swap(t[x].l,t[x].r);
swap(t[x].sum,t[x].revsum);
t[x].rev^=1;
}
void push(int x){
if(t[x].rev){
toggle(t[x].l);
toggle(t[x].r);
t[x].rev=false;
}
}
int build(const vector<T> &a){
vector<int> st;
for(auto &v:a){
int x=new_node(v),last=0;
while(!st.empty()&&t[st.back()].prio<t[x].prio){
last=st.back();
pull(last);
st.pop_back();
}
t[x].l=last;
if(!st.empty())t[st.back()].r=x;
st.push_back(x);
}
for(int i=SZ(st)-1;i>=0;i--)pull(st[i]);
return st.empty()?0:st[0];
}
int merge(int a,int b){
if(!a||!b)return a|b;
if(t[a].prio>t[b].prio){
push(a);
t[a].r=merge(t[a].r,b);
pull(a);
return a;
}else{
push(b);
t[b].l=merge(a,t[b].l);
pull(b);
return b;
}
}
pair<int,int> split(int x,int k){
if(!x)return {0,0};
push(x);
int ls=t[t[x].l].sz;
if(k<=ls){
auto [a,b]=split(t[x].l,k);
t[x].l=b;
pull(x);
return {a,x};
}else{
auto [a,b]=split(t[x].r,k-ls-1);
t[x].r=a;
pull(x);
return {x,b};
}
}
T query(int &x,int l,int r){
if(l>r)return Monoid::unit();
auto [a,b]=split(x,l);
auto [c,d]=split(b,r-l+1);
T res=sum(c);
x=merge(a,merge(c,d));
return res;
}
void reverse(int &x,int l,int r){
if(l>=r)return;
auto [a,b]=split(x,l);
auto [c,d]=split(b,r-l+1);
toggle(c);
x=merge(a,merge(c,d));
}
T get(int &x,int k){
auto [a,b]=split(x,k);
auto [c,d]=split(b,1);
T res=t[c].val;
x=merge(a,merge(c,d));
return res;
}
void set(int &x,int k,const T &v){
auto [a,b]=split(x,k);
auto [c,d]=split(b,1);
t[c].val=v;
pull(c);
x=merge(a,merge(c,d));
}
void insert(int &x,int k,const T &v){
auto [a,b]=split(x,k);
x=merge(merge(a,new_node(v)),b);
}
void erase(int &x,int k){
auto [a,b]=split(x,k);
auto [c,d]=split(b,1);
x=merge(a,d);
}
};
#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/bbst/treap/range_reverse_range_sum.test.cpp"
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;
Treap<AddMonoid<ll>> s(n);
int root=s.build(a);
while(q--){
int op,l,r;
cin >> op >> l >> r;
if(op)cout << s.query(root,l,r-1) << "\n";
else s.reverse(root,l,r-1);
}
}
verify/yosupo/data-structure/bbst/treap/range_reverse_range_sum.test.cpp