HDU 1698 <线段树,区间set>

时间:2023-12-27 14:34:13

题目连接

题意:

一条长为N的铜链子,每个结点的价值为1。有两种修改,l,r,z;
z=2:表示把[l,r]区间内链子改为银质,价值为2.
z=3:表示把[l,r]区间内链子改为金质,价值为3.

思路:

线段树,区间重设,求和。
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000+10;
struct node
{
int l;
int r;
int v;//标记该区间内的链条的属性,-1代表有杂色,1,2,3代表为纯色,并且属性值为;
};
node tree[maxn*4];
void maketree(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].v=1;起始为铜
if(r==l)
return ;
int mid=(l+r)>>1;
maketree(i<<1, l, mid);
maketree(i<<1|1, mid+1, r);
}
void update(int i,int l,int r,int v)
{
if(tree[i].v==v) //如果该区域内值一样则不用修改,以保证tree[i].l<=l,r<=tree[i].r;
return ;
if(tree[i].l==l&&tree[i].r==r)//如果区间与change区间一样则直接将tree[i].v=v;
{
tree[i].v=v;
return ;
}
if(tree[i].v!=-1)//修改区间不一致,并且为纯色则,向下延伸
{
tree[i<<1].v=tree[i<<1|1].v=tree[i].v;//颜色向下分配
tree[i].v=-1;//代表杂色
}
int mid=(tree[i].l+tree[i].r)>>1;
if(l>=mid+1)
update(i<<1|1, l, r, v);
else if(r<=mid)
update(i<<1, l, r, v);
else
{
update(i<<1, l, mid, v);
update(i<<1|1, mid+1,r,v);
}
}
int sum(int i)
{
if(tree[i].v!=-1)//叶子节点一定是纯色。
return (tree[i].r-tree[i].l+1)*tree[i].v;
return sum(i<<1)+sum(i<<1|1);
}
int main ()
{
int T;scanf("%d",&T);
int k=1;
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
maketree(1,1,n);
int l,r,v;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&l,&r,&v);
update(1, l, r, v);
}
printf("Case %d: The total value of the hook is %d.\n",k++,sum(1));
}
return 0;
}