hdu 1698 Just a Hook

题意：给你个n，表示区间【1，n】，价值初始为1，给你m段区间和价值，更新区间，区间价值以最后更新为准，问更新后区间价值总和为多少

思路：两种方法，可以先存下来，倒过来更新，一更新节点马上跳出，比较快

线段树

#include <iostream>

using namespace std;

int data[100005][3];

int main()

{

    int t,q,n,i,j,sum,k,v;

    scanf("%d",&t);

    for(i=1;i<=t;i++)

    {

        scanf("%d%d",&n,&q);

        for(j=1;j<=q;j++)

            scanf("%d%d%d",&data[j][0],&data[j][1],&data[j][2]);

        sum=0;

        for(k=1;k<=n;k++)

        {

            v=1;

            for(j=q;j>=1;j--)

                if(data[j][0]<=k && k<=data[j][1])//寻找k所在的更新区间，若存在则更新

                {

                    v=data[j][2];                 //若找的最后面的更新区间，则停止

                    break;

                }

            sum+=v;

        }

        printf("Case %d: The total value of the hook is %d.\n",i,sum);

    }

    return 0;

}

#include <iostream>

#include<cstdio>

using namespace std;

#define N 300010

struct node{

	int value;

	int l,r;

}tree[N];

void Build(int l,int r,int id){

	tree[id].l=l;

	tree[id].r=r;

	tree[id].value=1;

	if(l!=r){

		int mid=(l+r)>>1;

		Build(l,mid,id<<1);

		Build(mid+1,r,id<<1|1);

	}

}

void update(int l,int r,int value,int id){

	int mid=(tree[id].l+tree[id].r)>>1;

	if(tree[id].l==l&&tree[id].r==r){

		tree[id].value=value;

		return;

	}

	if(tree[id].value==value)

		return;

	if(tree[id].value!=-1){

		tree[id<<1].value=tree[id<<1|1].value=tree[id].value;

		tree[id].value=-1;

	}

	if(r<=mid)

		update(l,r,value,id<<1);

	else if(l>mid)

	    update(l,r,value,id<<1|1);

	else{

		update(l,mid,value,id<<1);

		update(mid+1,r,value,id<<1|1);

	}

}

int query(int id){

	if(tree[id].value!=-1)

		return (tree[id].r-tree[id].l+1)*tree[id].value;

	return query(id<<1)+query(id<<1|1);

}

int main(int argc, char** argv) {

	int t,n,m,x,y,k,Cas=1;

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		Build(1,n,1);

		scanf("%d",&m);

		while(m--){

			scanf("%d%d%d",&x,&y,&k);

			update(x,y,k,1);

		}

		printf("Case %d: The total value of the hook is %d.\n",Cas++,query(1));

	}

	return 0;

}

巴特西

hdu 1698 Just a Hook_线段树

最新文章

热门文章