The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3468 A Simple Problem with Integers Splay树区间操作

    接连做了维修数列和这个题,看来线段树能做的区间操作,用splay树应该也是可以的(都是打一个延迟标记嘛),做这题时发现有一点很重要,就是当我们压入延迟标记的时候(不管是push_down还是C a,b,c时都需要)一定要保证这个结点代表区间的最新信息。
   
#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;//设置一个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)//下压延迟标记后要将子树信息更新到最新
{
    
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 
*= 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 
*= x->pre, *= 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 
*= 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;
}








posted on 2010-10-22 22:26 abilitytao 阅读(1954) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理