线段树 （区间修改 区间查询 推延标记）

hdu 1698 Just a Hook

题意：

 给你一链子，这天链子由金银铜三种钩子组成，每种钩子都有自己的价值，起初，这条钩子全部由铜钩子组成，给你两个数n（钩子的个数），Q（操作的个数）每次操作就是将给定区间里的数变成某种钩子，求这条链子的总价值。

分析：

  线段树模版题，处理好延迟标记即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#pragma comment(linker, "/STACK:1024000000")
//#define LL __int64
#define LL long long
#define pi acos(-1.0)
#define PB push_back()
#define MP make_pair()
#define BG begin()
#define ED end()
#define clr(a,b)  memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define Mod  1e9+7
#define root  1,n,1
#define lson  l,mid,rt<<1
#define rson  mid+1,r,rt<<1|1
using namespace std;
const int maxn=100005;
int A[maxn];
int sum[maxn<<2];
int lazy[maxn<<2];


void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void PushDown(int rt,int len)
{
    if(lazy[rt])
    {
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
        sum[rt<<1]=(len-(len>>1))*lazy[rt];
        sum[rt<<1|1]=(len>>1)*lazy[rt];
        lazy[rt]=0;
    }
}

void Build(int l,int r,int rt)
{
    sum[rt]=1;
    lazy[rt]=0;
    if(l==r)  return ;
    int mid=l+r>>1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int ll,int rr,int c,int l,int r ,int rt)
{
    if(ll<=l&&rr>=r)
    {
        lazy[rt]=c;
        sum[rt]=(r-l+1)*c;
        return ;
    }
    PushDown(rt,r-l+1);
    int mid=l+r>>1;
    if(ll<=mid)  Update(ll,rr,c,lson);
    if(rr>mid)   Update(ll,rr,c,rson);
    PushUp(rt);
}
int main()
{
      #ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    #endif // ONLINE_JUDGE
    int T,i;
    cin>>T;
  for(i=1;i<=T;i++)
    {
        int n;
        scanf("%d",&n);
        Build(root);
        int Q;
        scanf("%d",&Q);
        while(Q--)
        {
            int l, r, z;
            scanf("%d%d%d",&l,&r,&z);
            Update(l,r,z,root);
        }
        printf("Case %d: The total value of the hook is %d.\n",i,sum[1]);
    }
    return 0;

}

poj 3468 A Simple Problem with Integers

题意比较简单，直接上代码；

代码：

#define root  1,n,1
#define lson  l,mid,rt<<1
#define rson  mid+1,r,rt<<1|1
const int maxn=100115;
LL sum[maxn<<2];
LL lazy[maxn<<2];

void PushUp(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int len)
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=(len-(len>>1))*lazy[rt];
        sum[rt<<1|1]+=(len>>1)*lazy[rt];
        lazy[rt]=0;
    }
}
void Build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r){
      scanf("%I64d",&sum[rt]);
        return ;
    }
    int mid=l+r>>1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int ll,int rr,int c,int l,int r,int rt)
{
    if(ll<=l&&rr>=r)
    {
        sum[rt]+=(LL)(r-l+1)*c;
        lazy[rt]+=c;
        return ;
    }
    PushDown(rt,r-l+1);
    int mid=l+r>>1;
    if(ll<=mid)  Update(ll,rr,c,lson);
    if(rr>mid)   Update(ll,rr,c,rson);
    PushUp(rt);
}

LL  Query(int ll,int rr,int l,int r,int rt)
{
    if(ll<=l&&rr>=r)
        return sum[rt];
    PushDown(rt,r-l+1);
    int mid=l+r>>1;
    LL cnt=0;
    if(ll<=mid) cnt+=Query(ll,rr,lson);
    if(rr>mid)  cnt+=Query(ll,rr,rson);
    return cnt;
}
char ty[10];
int main()
{
      #ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    #endif // ONLINE_JUDGE
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        Build(root);
        while(q--)
        {
            int a,b,z;
            scanf("%s",ty);
            if(ty[0]=='Q')  {
                scanf("%d%d",&a,&b);
                printf("%I64d\n",Query(a,b,root));
            }
            else if(ty[0]=='C'){
                scanf("%d%d%d",&a,&b,&z);
                Update(a,b,z,root);
            }
        }
    }
    return 0;

}