This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://yukicoder.me/problems/5398" #include "../template.hpp" #include "../BinarySearchTree/SplayTree.hpp" signed main(){ int n,q;cin>>n>>q; SplayTree<ll> splay([](ll a,ll b){return a+b;},0); vector<ll> a(n); cin>>a; auto t=splay.build(a); while(q--){ int type;cin>>type; if(type==1){ int l,r;cin>>l>>r; l--; ll sum=splay.query(t,l,r); auto x=splay.split(t,l); auto y=splay.split(x.second,r-l); x.first=splay.push_back(x.first,sum); t=splay.merge(x.first,y.second); }else{ int l,r;cin>>l>>r;l--; cout<<splay.query(t,l,r)<<endl; } } return 0; }
#line 1 "test/yuki5398_2.test.cpp" #define PROBLEM "https://yukicoder.me/problems/5398" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yuki5398_2.test.cpp" #line 1 "BinarySearchTree/SplayTree.hpp" template<typename Monoid> struct SplayTree{ public: using F=function<Monoid(Monoid,Monoid)>; struct Node{ Node *l,*r,*p; Monoid val,sum; int sz; bool rev; bool is_root(){ return !p; } Node(const Monoid &val):l(nullptr),r(nullptr),p(nullptr), val(val),sum(val),sz(1),rev(false){} }; const F f; const Monoid e; SplayTree(F f,Monoid e):f(f),e(e){} int size(Node *t){return t?t->sz:0;} Monoid sum(Node *t){return t?t->sum:e;} Node *build(const vector<Monoid> &v){ return build(0,(int)v.size(),v); } Node *build(){ return nullptr; } pair<Node *,Node *> split(Node *t,int k){ if(!t) return {nullptr,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; return {x.first,update(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; return {update(t),x.second}; } } Node *merge(Node *l,Node *r){ if(!l and !r) return nullptr; if(!l){ splay(r); return r; } if(!r){ splay(l); return l; } splay(l); splay(r); l=get_right(l); splay(l); l->r=r; r->p=l; update(l); return l; } Node *insert(Node *&t,int k,Monoid val){ assert(k<=size(t)); if(!t){ t=new Node(val); return t; } splay(t); auto x=split(t,k); t=merge(merge(x.first,new Node(val)),x.second); return t; } Node *erase(Node *&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); return t; } // [a,b) Monoid query(Node *&t,int a,int b){ splay(t); auto x=split(t,a); auto y=split(x.second,b-a); auto res=sum(y.first); t=merge(merge(x.first,y.first),y.second); return res; } Node *push_front(Node *t,Monoid x){ if(!t){ t=new Node(x); return t; } splay(t); Node *cur=get_left(t),*add=new Node(x); splay(cur); add->p=cur; cur->l=add; splay(add); return add; } Node *push_back(Node *t,Monoid x){ if(!t){ t=new Node(x); return t; } Node *cur=get_right(t),*add=new Node(x); splay(cur); add->p=cur; cur->r=add; splay(add); return add; } Node *reverse(Node *t,int a,int b){ splay(t); auto x=split(t,a); auto y=split(x.second,b-a); y.first->rev^=true; return merge(x.first,merge(y.first,y.second)); } // rotate v[l] <- v[m] Node *rotate(Node *t,int a,int m,int b){ t=reverse(t,a,b); t=reverse(t,a,a+b-m); t=reverse(t,a+b-m,b); return t; } private: Node *build(int l,int r,const vector<Monoid> &v){ if(l+1==r) return new Node(v[l]); int m=(l+r)/2; return merge(build(l,m,v),build(m,r,v)); } Node *get_left(Node *cur){ while(true){ push(cur); if(!cur->l) return cur; cur=cur->l; } } Node *get_right(Node *cur){ while(true){ push(cur); if(!cur->r) return cur; cur=cur->r; } } // tを1個上に,右回転 void rotr(Node *cur){ auto *par=cur->p; auto *parpar=par->p; // A < cur < B < par < C // ((A) - cur - (B)) - par - (C) auto *B=cur->r; par->l=B; if(B) B->p=par; cur->r=par; par->p=cur; update(par);// parがcurの右子に変わった update(cur); cur->p=parpar; if(parpar){ if(parpar->l==par) parpar->l=cur; if(parpar->r==par) parpar->r=cur; update(parpar); } } // tを1個上に,左回転 void rotl(Node *cur){ auto *par=cur->p; auto *parpar=par->p; // (C) - par - ((B) - cur - (A)) // C < par < B < cur < A auto *B=cur->l; par->r=B; if(B) B->p=par; cur->l=par; par->p=cur; update(par);// parがcurの右子に変わった update(cur); cur->p=parpar; if(parpar){ if(parpar->l==par) parpar->l=cur; if(parpar->r==par) parpar->r=cur; update(parpar); } } // 子から集約 Node *update(Node *t){ t->sz=1; t->sum=t->val; if(t->l) t->sz+=t->l->sz,t->sum=f(t->l->sum,t->sum); if(t->r) t->sz+=t->r->sz,t->sum=f(t->sum,t->r->sum); return t; } void push(Node *t){ if(t and t->rev){ swap(t->l,t->r); if(t->l) t->l->rev^=true; if(t->r) t->r->rev^=true; t->rev=false; } } void splay(Node *cur){ push(cur); while(!cur->is_root()){ auto *par=cur->p; if(par->is_root()){// zig push(par); push(cur); if(par->l==cur) rotr(cur); else rotl(cur); }else{// zig-zig, zig-zag auto *parpar=par->p; push(parpar); push(par); push(cur); if(parpar->l==par){ if(par->l==cur){// / rotr(par); rotr(cur); }else{// く rotl(cur); rotr(cur); } }else{ if(par->r==cur){ rotl(par); rotl(cur); }else{ rotr(cur); rotl(cur); } } } } } }; #line 6 "test/yuki5398_2.test.cpp" signed main(){ int n,q;cin>>n>>q; SplayTree<ll> splay([](ll a,ll b){return a+b;},0); vector<ll> a(n); cin>>a; auto t=splay.build(a); while(q--){ int type;cin>>type; if(type==1){ int l,r;cin>>l>>r; l--; ll sum=splay.query(t,l,r); auto x=splay.split(t,l); auto y=splay.split(x.second,r-l); x.first=splay.push_back(x.first,sum); t=splay.merge(x.first,y.second); }else{ int l,r;cin>>l>>r;l--; cout<<splay.query(t,l,r)<<endl; } } return 0; }