心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
此题AC了不止一次,用线段树和树状数组都实现过。
以下是我的代码:
#include<cstdio>
#define
 L(x) ((x)<<1)
#define R(x) (((x)<<1)^1)
using namespace std;
const int kMaxn(100007);

struct Node
{
    
int a,b,kind,sum;
};

int N,Q;
Node tree[kMaxn
<<2];

void Build(int node,int x,int y)
{
    tree[node].a
=x;
    tree[node].b
=y;
    tree[node].kind
=0;
    
if(x==y)
        tree[node].sum
=1;
    
else
    {
        
int m((x+y)>>1);
        Build(L(node),x,m);
        Build(R(node),m
+1,y);
        tree[node].sum
=tree[L(node)].sum+tree[R(node)].sum;
    }
}

void Modify(int node,int x,int y,int z)
{
    
if(x<=tree[node].a && tree[node].b<=y)
    {
        tree[node].kind
=z;
        tree[node].sum
=(tree[node].b-tree[node].a+1)*z;
    }
    
else
    {
        
if(tree[node].kind)
        {
            tree[L(node)].kind
=tree[R(node)].kind=tree[node].kind;
            tree[node].kind
=0;
            tree[L(node)].sum
=(tree[L(node)].b-tree[L(node)].a+1)*tree[L(node)].kind;
            tree[R(node)].sum
=(tree[R(node)].b-tree[R(node)].a+1)*tree[R(node)].kind;
        }
        
int m((tree[node].a+tree[node].b)>>1);
        
if(x<=m)
            Modify(L(node),x,y,z);
        
if(m+1<=y)
            Modify(R(node),x,y,z);
        tree[node].sum
=tree[L(node)].sum+tree[R(node)].sum;
    }
}

int main()
{
    
int T;
    scanf(
"%d",&T);
    
for(int case_num=1;case_num<=T;case_num++)
    {
        scanf(
"%d%d",&N,&Q);

        Build(
1,1,N);

        
while(Q--)
        {
            
int x,y,z;
            scanf(
"%d%d%d",&x,&y,&z);
            Modify(
1,x,y,z);
        }

        printf(
"Case %d: The total value of the hook is %d.\n",case_num,tree[1].sum);
    }

    
return 0;
}
posted on 2011-07-31 09:24 lee1r 阅读(322) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理