Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 给出两种解法：splay、线段树

Posted by ACAccepted at 2020-01-18 15:28:50 on Problem 3468 and last updated at 2020-01-18 15:34:35
```//splay：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

template<typename T>
{
T x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

const int MAXN=100005;
int n,m;

struct Splay
{
struct BST
{
int lson,rson,father,size;
long long val,cover,sum;
}tree[MAXN];

#define root tree[0].rson

inline void push_down(int now)
{
if (tree[now].cover==0) return ;
if (tree[now].lson!=0)
{
tree[tree[now].lson].val+=tree[now].cover;
tree[tree[now].lson].cover+=tree[now].cover;
tree[tree[now].lson].sum+=tree[now].cover*tree[tree[now].lson].size;
}
if (tree[now].rson!=0)
{
tree[tree[now].rson].val+=tree[now].cover;
tree[tree[now].rson].cover+=tree[now].cover;
tree[tree[now].rson].sum+=tree[now].cover*tree[tree[now].rson].size;
}
tree[now].cover=0;
}

inline void size_update(int now)
{
if (now==0) return ;
tree[now].size=tree[tree[now].lson].size+tree[tree[now].rson].size+1;
tree[now].sum=tree[tree[now].lson].sum+tree[tree[now].rson].sum+tree[now].val;
}

inline void left_rotate(int now)
{
int fa=tree[now].father;
push_down(fa);push_down(now);
tree[fa].rson=tree[now].lson;
tree[now].father=tree[fa].father;
tree[fa].father=now;
tree[now].lson=fa;
if (tree[fa].rson!=0) tree[tree[fa].rson].father=fa;
if (tree[tree[now].father].lson==fa) tree[tree[now].father].lson=now;
else tree[tree[now].father].rson=now;
size_update(fa);size_update(now);
}

inline void right_rotate(int now)
{
int fa=tree[now].father;
push_down(fa);push_down(now);
tree[fa].lson=tree[now].rson;
tree[now].father=tree[fa].father;
tree[fa].father=now;
tree[now].rson=fa;
if (tree[fa].lson!=0) tree[tree[fa].lson].father=fa;
if (tree[tree[now].father].lson==fa) tree[tree[now].father].lson=now;
else tree[tree[now].father].rson=now;
size_update(fa);size_update(now);
}

inline void splay(int now,int &rt)
{
int fa,to=tree[rt].father;push_down(now);
while (tree[now].father!=to)
{
fa=tree[now].father;
if (tree[fa].father==to)
{
if (now>fa) left_rotate(now);
else right_rotate(now);
break;
}
if (now==tree[fa].lson)
{
if (tree[tree[fa].father].lson==fa)
{
right_rotate(fa);
right_rotate(now);
}
else
{
right_rotate(now);
left_rotate(now);
}
}
else
{
if (tree[tree[fa].father].lson==fa)
{
left_rotate(now);
right_rotate(now);
}
else
{
left_rotate(fa);
left_rotate(now);
}
}
}
rt=now;
}

inline void build()
{
root=1;
for (int i=n;i>=2;i--) tree[i-1].rson=i,tree[i].father=i-1,size_update(i-1);
if (n>1) splay(n/2,root);
}

inline void modify(int l,int r,long long cover)
{
int now;
if (l==1&&r==n) now=root;
else if (l==1)
{
splay(r+1,root);
now=tree[root].lson;
}
else if (r==n)
{
splay(l-1,root);
now=tree[root].rson;
}
else
{
splay(l-1,root),splay(r+1,tree[root].rson);
now=tree[tree[root].rson].lson;
}
tree[now].val+=cover;
tree[now].cover+=cover;
tree[now].sum+=cover*tree[now].size;
size_update(tree[now].father);
}

inline long long query(int l,int r)
{
int now;
if (l==1&&r==n) now=root;
else if (l==1)
{
splay(r+1,root);
now=tree[root].lson;
}
else if (r==n)
{
splay(l-1,root);
now=tree[root].rson;
}
else
{
splay(l-1,root);splay(r+1,tree[root].rson);
now=tree[tree[root].rson].lson;
}
return tree[now].sum;
}
}Tr;

int main()
{
char c;int l,r;
Tr.build();
while (m--)
{
switch (c)
{
case 'Q':printf("%lld\n",Tr.query(l,r));break;
}
}
return 0;
}

/*----------------------------------------------------------------------------------------------------------------------------------------------------分割线*/

//线段树

#include <cstdio>
#include <iostream>
using namespace std;

template<typename T>
{
T x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

const int MAXN=100005;
int n,m;
long long a[MAXN];

namespace stree
{
long long tree[MAXN<<2],val[MAXN<<2];

inline void build(int k,int l,int r)
{
if (l==r) {tree[k]=a[l];return ;}
int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
tree[k]=tree[k<<1]+tree[k<<1|1];
}

inline void update(int k,int l,int r,int _l,int _r,long long d)
{
if (_l<=l&&_r>=r) {tree[k]+=d*(r-l+1);val[k]+=d;return ;}
int mid=l+r>>1;
if (_l<=mid) update(k<<1,l,mid,_l,_r,d);
if (_r>mid) update(k<<1|1,mid+1,r,_l,_r,d);
tree[k]=tree[k<<1]+tree[k<<1|1]+val[k]*(r-l+1);
}

inline long long query(int k,int l,int r,int _l,int _r,long long ans=0)
{
if (_l<=l&&_r>=r) return tree[k];
int mid=l+r>>1;
if (_l<=mid) ans+=query(k<<1,l,mid,_l,_r);
if (_r>mid) ans+=query(k<<1|1,mid+1,r,_l,_r);
return ans+val[k]*(min(r,_r)-max(l,_l)+1);
}
}

int main()
{
char c;int x,y;
stree::build(1,1,n);
for (int i=1;i<=m;i++)
{
else printf("%lld\n",stree::query(1,1,n,x,y));
}
return 0;
}```

Followed by: