HDU1698(线段树+延迟标记)

一看便知道用线段树，题目比较水，一般简单的线段树就是两招 离散化和延迟标记

这道题目明显是用延迟标记，不要用链式树，用树状数组，否则会超空间。

#include
        #include
        #include
        using namespace std;
        
        int N,Q;
        
        typedef struct node
        {
        int l,r;
        int left_value,right_value;
        int delay;
}node;
node tree[100000*4+10];

int build(int p,int x,int y)
{
tree[p].delay=0;
tree[p].l=x;
tree[p].r=y;
if(x==y)
{
tree[p].left_value=1;
tree[p].right_value=0; 
}
else
{
tree[p].left_value=build(p*2,x,(x+y)/2);
tree[p].right_value=build(p*2+1,(x+y)/2+1,y);   
}
return tree[p].left_value+tree[p].right_value;
}

int updates(int p,int x,int y,int v)
{
if(tree[p].delay!=0)
{
tree[p].left_value=((tree[p].l+tree[p].r)/2-tree[p].l+1)*tree[p].delay;
tree[p].right_value=(tree[p].r-(tree[p].l+tree[p].r)/2)*tree[p].delay;
if(tree[p].l!=tree[p].r) tree[p*2].delay=tree[p].delay;
if(tree[p].l!=tree[p].r) tree[p*2+1].delay=tree[p].delay;
tree[p].delay=0;
}

if(!(x<=tree[p].r&&y>=tree[p].l))
return tree[p].left_value+tree[p].right_value;


if(x<=tree[p].l&&y>=tree[p].r)
{
tree[p].left_value=((tree[p].l+tree[p].r)/2-tree[p].l+1)*v;
tree[p].right_value=(tree[p].r-(tree[p].l+tree[p].r)/2)*v;
if(tree[p].l!=tree[p].r) tree[p*2].delay=v;
if(tree[p].l!=tree[p].r) tree[p*2+1].delay=v;
}
else
{
tree[p].left_value=updates(p*2,x,y,v);
tree[p].right_value=updates(p*2+1,x,y,v);
}
return tree[p].left_value+tree[p].right_value;
}
        
        int main()
{
    int T;
    scanf("%d",&T);
    for(int Case=1;Case<=T;Case++)
    {
    scanf("%d%d",&N,&Q);
    build(1,1,N);
    for(int i=1;i<=Q;i++)
    {
    int a,b,v;
    scanf("%d%d%d",&a,&b,&v);
    updates(1,a,b,v);
}
printf("Case %d: The total value of the hook is %d.\n",
Case,tree[1].left_value+tree[1].right_value);
}
}