区间更新求和
主要用来练习splay树区间更新问题
//splay树的题解
// File Name: 3468-splay.cpp
// Author: Zlbing
// Created Time: 2013年08月09日 星期五 16时30分32秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--) #define L ch[x][0]
#define R ch[x][1]
#define KT (ch[ch[rt][1]][0])
const int MAXN=2e5+;
struct SplayTree{
int ch[MAXN][];
int pre[MAXN],sz[MAXN],val[MAXN];
int rt,top;
void Rotate(int x,int f)
{
int y=pre[x];
down(y);down(x);
ch[y][!f]=ch[x][f];
pre[ch[x][f]]=y;
pre[x]=pre[y];
if(pre[x])
ch[pre[y]][ch[pre[y]][]==y]=x;
ch[x][f]=y;
pre[y]=x;
up(y);
}
void Splay(int x,int goal)
{
down(x);
while(pre[x]!=goal)
{
down(pre[pre[x]]);
down(pre[x]);
down(x);
if(pre[pre[x]]==goal)
Rotate(x,ch[pre[x]][]==x);
else
{
int y=pre[x],z=pre[y];
int f=(ch[z][]==y);
if(ch[y][f]==x)
Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
}
up(x);
if(goal==)rt=x;
}
void RTO(int k,int goal)
{
int x=rt;
down(x);
while(sz[L]+!=k)
{
if(k<sz[L]+)x=L;
else
{
k-=(sz[L]+);
x=R;
}
down(x);
}
Splay(x,goal);
}
void vist(int x)
{
if(x)
{
printf("结点%2d : 左儿子 %2d 右儿子 %2d val: %2d sum=%lld\n",x,ch[x][],ch[x][],val[x],sum[x]);
vist(L);
vist(R);
}
}
void debug()
{
puts(""); vist(rt); puts("");
}
void up(int x)
{
sz[x]=+sz[L]+sz[R];
sum[x]=val[x]+sum[L]+sum[R];
}
void down(int x)
{
if(add[x])
{
val[L]+=add[x];
val[R]+=add[x];
add[L]+=add[x];
add[R]+=add[x];
sum[L]+=(LL)add[x]*sz[L];
sum[R]+=(LL)add[x]*sz[R];
add[x]=;
}
}
void Newnode(int &x,int c,int f)
{
x=++top;
L=R=; sz[x]=; pre[x]=f;
val[x]=sum[x]=c;
add[x]=;
}
void build(int &x,int l,int r,int f)
{
if(l>r)return;
int m=(l+r)>>;
Newnode(x,num[m],f);
build(L,l,m-,x);
build(R,m+,r,x);
up(x);
}
void init(int n)
{
ch[][]=ch[][]=pre[]=;
sz[]=rt=top=; add[]=sum[]=;
Newnode(rt,-,);
Newnode(ch[rt][],-,rt);
sz[rt]=;
for(int i=;i<=n;i++)
scanf("%d",&num[i]); build(KT,,n,ch[rt][]);
up(ch[rt][]);up(rt);
}
void update()
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
RTO(l,);
RTO(r+,rt);
add[KT]+=c;
val[KT]+=c;
sum[KT]+=(LL)c*sz[KT];
}
void query()
{
int l,r;
scanf("%d%d",&l,&r);
RTO(l,);
RTO(r+,rt);
printf("%lld\n",sum[KT]);
}
LL sum[MAXN];
int add[MAXN];
int num[MAXN];
}spt;
int main()
{
int m,n;
char op[];
while(~scanf("%d%d",&n,&m))
{
spt.init(n);
while(m--)
{
scanf("%s",op);
if(op[]=='Q')spt.query();
else spt.update();
}
}
return ;
}
线段树的题解
// File Name: /home/neuacm/ACM/POJ/3468.cpp
// Author: Zlbing
// Created Time: 2013年08月09日 星期五 14时35分11秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN=1e5+;
LL col[MAXN<<];
LL sum[MAXN<<];
void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void pushdown(int rt,int l,int r)
{
if(col[rt])
{
col[rt<<]+=col[rt];
col[rt<<|]+=col[rt];
int m=(l+r)>>;
sum[rt<<]+=(m-l+)*col[rt];
sum[rt<<|]+=(r-m)*col[rt];
col[rt]=;
}
}
void build(int l,int r,int rt)
{
col[rt]=;
if(l==r)
{
//scanf("%I64d",&sum[rt]);
cin>>sum[rt];
return ;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt];
}
pushdown(rt,l,r);
int m=(l+r)>>;
LL ret=;
if(L<=m)ret+=query(L,R,lson);
if(R>m)ret+=query(L,R,rson);
return ret;
}
void update(int L,int R,int p,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
col[rt]+=p;
sum[rt]+=(r-l+)*p;
return;
}
pushdown(rt,l,r);
int m=(l+r)>>;
if(L<=m)update(L,R,p,lson);
if(R>m)update(L,R,p,rson);
pushup(rt);
}
void debug(int l,int r,int rt)
{
if(l==r)
{
printf("l==%d r==%d rt=%d sum[rt]=%lld col[rt]=%lld\n",l,r,rt,sum[rt],col[rt]);
return ;
}
printf("l==%d r==%d rt=%d sum[rt]=%lld col[rt]=%lld\n",l,r,rt,sum[rt],col[rt]);
int m=(l+r)>>;
debug(lson);
debug(rson);
}
int main()
{
int n,m;
//std::ios::sync_with_stdio(false);
while(~scanf("%d%d",&n,&m))
{
build(,n,);
char ch[];
int a,b,c;
REP(i,,m)
{
scanf("%s",ch);
if(ch[]=='Q')
{
scanf("%d%d",&a,&b);
LL ans=query(a,b,,n,);
//debug(1,n,1);
cout<<ans<<endl;
}
else if(ch[]=='C')
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,,n,);
//debug(1,n,1);
}
}
}
return ;
}