| 1234 |
- #include <iostream>
- #include <vector>
- using namespace std;struct Node{int ch[2]{},parent=0,size=1;long long value=0,sum=0;bool rev=false;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<long long>a(n+2);for(int i=1;i<=n;++i)cin>>a[i];vector<Node>tr(n+3);int nodes=0,root=0;auto size=[&](int x){return x?tr[x].size:0;};auto sum=[&](int x){return x?tr[x].sum:0LL;};auto pull=[&](int x){tr[x].size=size(tr[x].ch[0])+size(tr[x].ch[1])+1;tr[x].sum=sum(tr[x].ch[0])+sum(tr[x].ch[1])+tr[x].value;};auto apply=[&](int x){if(x){swap(tr[x].ch[0],tr[x].ch[1]);tr[x].rev^=1;}};auto push=[&](int x){if(x&&tr[x].rev){apply(tr[x].ch[0]);apply(tr[x].ch[1]);tr[x].rev=false;}};auto build=[&](auto&&self,int l,int r,int parent)->int{if(l>r)return 0;int m=(l+r)/2,x=++nodes;tr[x].parent=parent;tr[x].value=a[m];tr[x].ch[0]=self(self,l,m-1,x);tr[x].ch[1]=self(self,m+1,r,x);pull(x);return x;};root=build(build,0,n+1,0);auto rotate=[&](int x){int y=tr[x].parent,z=tr[y].parent,d=tr[y].ch[1]==x,b=tr[x].ch[d^1];if(z)tr[z].ch[tr[z].ch[1]==y]=x;else root=x;tr[x].parent=z;tr[x].ch[d^1]=y;tr[y].parent=x;tr[y].ch[d]=b;if(b)tr[b].parent=y;pull(y);pull(x);};auto splay=[&](int x,int goal=0){vector<int>path;for(int u=x;u!=goal;u=tr[u].parent)path.push_back(u);for(auto it=path.rbegin();it!=path.rend();++it)push(*it);while(tr[x].parent!=goal){int y=tr[x].parent,z=tr[y].parent;if(z!=goal)((tr[y].ch[1]==x)==(tr[z].ch[1]==y)?rotate(y):rotate(x));rotate(x);}if(!goal)root=x;};auto kth=[&](int k){int u=root;while(true){push(u);int left=size(tr[u].ch[0]);if(k==left+1)return u;if(k<=left)u=tr[u].ch[0];else k-=left+1,u=tr[u].ch[1];}};auto expose=[&](int l,int r){int x=kth(l);splay(x);int y=kth(r+2);splay(y,x);return tr[y].ch[0];};while(q--){int type,l,r;cin>>type>>l>>r;int segment=expose(l,r);if(type==1){apply(segment);int y=tr[segment].parent;pull(y);pull(tr[y].parent);}else cout<<tr[segment].sum<<'\n';}}
|
