#line 1 "verify/yosupo/data-structure/bbst/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/bbst/splay-tree.hpp"
template<class Monoid>
struct SplayTree{
using T = typename Monoid::value_type;
struct Node{
int l,r,p,sz;
bool rev;
T val,sum,revsum;
};
vector<Node> t;
SplayTree(int reserve=0){
t.reserve(reserve+1);
t.push_back(Node{0,0,0,0,false,Monoid::unit(),Monoid::unit(),Monoid::unit()});
}
int make(const T &v){
t.push_back(Node{0,0,0,1,false,v,v,v});
return SZ(t)-1;
}
int sz(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;
}
}
void rotate(int x){
int p=t[x].p,g=t[p].p;
if(t[p].l==x){
t[p].l=t[x].r;
if(t[x].r)t[t[x].r].p=p;
t[x].r=p;
}else{
t[p].r=t[x].l;
if(t[x].l)t[t[x].l].p=p;
t[x].l=p;
}
t[p].p=x;
t[x].p=g;
if(g)(t[g].l==p?t[g].l:t[g].r)=x;
pull(p);
}
void splay(int x){
while(int p=t[x].p){
int g=t[p].p;
if(g)rotate((t[g].l==p)==(t[p].l==x)?p:x);
rotate(x);
}
pull(x);
}
int kth(int x,int k){
assert(0<=k&&k<sz(x));
while(true){
push(x);
int ls=t[t[x].l].sz;
if(k<ls)x=t[x].l;
else if(k==ls)break;
else k-=ls+1,x=t[x].r;
}
splay(x);
return x;
}
int build(const vector<T> &a){
auto rec=[&](auto &&self,int l,int r)->int{
if(l>r)return 0;
int m=(l+r)/2,x=make(a[m]);
int lc=self(self,l,m-1),rc=self(self,m+1,r);
t[x].l=lc,t[x].r=rc;
if(lc)t[lc].p=x;
if(rc)t[rc].p=x;
pull(x);
return x;
};
return rec(rec,0,SZ(a)-1);
}
int merge(int a,int b){
if(!a||!b)return a|b;
a=kth(a,sz(a)-1);
t[a].r=b;
t[b].p=a;
pull(a);
return a;
}
pair<int,int> split(int x,int k){
if(k<=0)return {0,x};
if(k>=sz(x))return {x,0};
x=kth(x,k-1);
int y=t[x].r;
t[x].r=0;
t[y].p=0;
pull(x);
return {x,y};
}
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){
x=kth(x,k);
return t[x].val;
}
void set(int &x,int k,const T &v){
x=kth(x,k);
t[x].val=v;
pull(x);
}
void insert(int &x,int k,const T &v){
auto [a,b]=split(x,k);
x=merge(merge(a,make(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/splay-tree/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;
SplayTree<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/splay-tree/range_reverse_range_sum.test.cpp