cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
verify/yosupo/data-structure/range_reverse_range_sum.test.cpp
- View this file on GitHub
- Last update: 2024-10-31 23:18:18+07:00
- Problem: https://judge.yosupo.jp/problem/range_reverse_range_sum
Depends on
- data-structure/link-cut-tree/reversible-bbst.hpp
- data-structure/link-cut-tree/reversible-splay-tree.hpp
- data-structure/link-cut-tree/splay-tree-base.hpp
- group/monoid/add.hpp
- template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"
#include "template.hpp"
#include "data-structure/link-cut-tree/reversible-splay-tree.hpp"
#include "group/monoid/add.hpp"
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);
}
}
}#line 1 "verify/yosupo/data-structure/range_reverse_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
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);
}
}
}
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};
push(t);
if(k<=size(t->l)){
auto x=split(t->l,k);
t->l=x.second;
t->p=nullptr;
if(x.second)x.second->p=t;
pull(t);
return {x.first,t};
}else{
auto x=split(t->r,k-size(t->l)-1);
t->r=x.first;
t->p=nullptr;
if(x.first)x.first->p=t;
pull(t);
return {t,x.second};
}
}
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/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);
}
}
}