接連做了維修數(shù)列和這個題，看來線段樹能做的區(qū)間操作，用splay樹應(yīng)該也是可以的（都是打一個延遲標(biāo)記嘛）,做這題時發(fā)現(xiàn)有一點很重要，就是當(dāng)我們壓入延遲標(biāo)記的時候(不管是push_down還是C a,b,c時都需要)一定要保證這個結(jié)點代表區(qū)間的最新信息。
#include <iostream>
using namespace std;
int const maxn=300000;
#define bint __int64
struct node
{
int value,size;
int add;
bint sum;
node *ch[2], *pre;
}tree[maxn],*Null, *root;//設(shè)置一個Null指針是一個亮點
int num[maxn];
int n,m;
int top=0;
node *New_Node(int x)
{
node *p=&tree[top++];
p->ch[0]=p->ch[1]=p->pre=Null;
p->add=0;
p->sum=x;
p->size=1;
p->value=x;
return p;
}
void Push_Down(node *x)//下壓延遲標(biāo)記后要將子樹信息更新到最新
{
if (x == Null) return;
x->value+=x->add;
x->ch[0]->add+=x->add;
x->ch[1]->add+=x->add;
if(x->ch[0]!=Null)
x->ch[0]->sum+=(bint)(x->add)*(x->ch[0]->size);
if(x->ch[1]!=Null)
x->ch[1]->sum+=(bint)(x->add)*(x->ch[1]->size);
x->add=0;
}
void Update(node *x)
{
if (x == Null) return;
x->size = x->ch[0]->size + x->ch[1]->size + 1;
x->sum = (bint)x->value+ x->ch[0]->sum + x->ch[1]->sum;
}
void Rotate(node *x, int c)
{
node *y = x->pre;
Push_Down(y), Push_Down(x);
y->ch[! c] = x->ch[c], x->pre = y->pre;
if (x->ch[c] != Null) x->ch[c]->pre = y;
if (y->pre != Null) y->pre->ch[y->pre->ch[1] == y] = x;
y->pre = x, x->ch[c] = y;
if (y == root) root = x;
Update(y);
}
void Splay(node *x, node *f)
{
for (Push_Down(x); x->pre != f; )
{
if (x->pre->pre == f)
Rotate(x, x->pre->ch[0] == x);
else
{
node *y = x->pre, *z = y->pre;
if (z->ch[0] == y)
if (y->ch[0] == x)
Rotate(y, 1), Rotate(x, 1);
else
Rotate(x, 0), Rotate(x, 1);
else
if (y->ch[1] == x)
Rotate(y, 0), Rotate(x, 0);
else
Rotate(x, 1), Rotate(x, 0);
}
}
Update(x);
}
void Select(int k, node *f)
{
node *now=root;
while(true)
{
Push_Down(now);
int tmp = now->ch[0]->size;
if (tmp + 1 == k) break;
if (k <= tmp)
now = now->ch[0];
else
now = now->ch[1], k -= tmp + 1;
}
Splay(now, f);
}
node *Make_Tree(int l, int r, node *fa)
{
if (l > r) return Null;
int mid = l + r >> 1;
node *p = New_Node(num[mid]);
p->ch[0] = Make_Tree(l, mid-1, p);
p->ch[1] = Make_Tree(mid+1, r, p);
p->pre = fa, Update(p);
return p;
}
int main()
{
top=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
Null=New_Node(0);
Null->size=0;
root=New_Node(-1);
root->ch[1]=New_Node(-1);
root->ch[1]->pre=root;
Update(root);
root->ch[1]->ch[0]=Make_Tree(1,n,root->ch[1]);
char s[2];
for(int i=0;i<m;i++)
{
scanf("%s",s);
if(s[0]=='C')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Select(a,Null);
Select(b+2,root);
root->ch[1]->ch[0]->add+=c;
root->ch[1]->ch[0]->sum+=(bint)c*(root->ch[1]->ch[0]->size);
}
else
{
int a,b;
scanf("%d%d",&a,&b);
Select(a,Null);
Select(b+2,root);
printf("%I64d\n",root->ch[1]->ch[0]->sum);
}
}
return 0;
}