HDU 1698 线段树
http://acm.hdu.edu.cn/showproblem.php?pid=1698
In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.
Now Pudge wants to do some operations on the hook.
Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks.
The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows:
For each cupreous stick, the value is 1.
For each silver stick, the value is 2.
For each golden stick, the value is 3.
Pudge wants to know the total value of the hook after performing the operations.
You may consider the original hook is made up of cupreous sticks.
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations.
Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind.
Output
For each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example.
Sample Input
1 10 2 1 5 2 5 9 3
Sample Output
Case 1: The total value of the hook is 24.
题目大意：(看到这种题面真的很怀念啊23333)给出长度为n的DOTA中屠夫的钩子， 钩子有三种材质： 铜、 铁、 金， 对应的价值分别为1、2、3。 屠夫可以改变[a， b]内钩子的材质，在经过m个操作后，问钩子的总价值。
思路：线段树，维护的值可以多种多样，我第一时间想到的就是维护该节点区间范围内铜质钩子的长度和铁质钩子的长度，(金质钩子的长度可以通过区间左右端点和这两个长度计算出来)虽然有点暴力，(时间复杂度不如更优的算法)但是是比较容易想到也比较容易理解的。lazy标记着钩子的材质。
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=100005;
struct node
{
int l,r,n1,n2,lazy; //铜和银的长度
};
node tree[maxn<<2];
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
if(l==r)
{
tree[i].n1=1;
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
tree[i].n1=tree[i<<1].n1+tree[i<<1|1].n1;//价值总和
}
void down(int i)
{
if(tree[i].lazy==1)//铜
{
tree[i<<1].lazy=tree[i<<1|1].lazy=1;
tree[i<<1].n1=tree[i<<1].r-tree[i<<1].l+1;
tree[i<<1].n2=0;
tree[i<<1|1].n1=tree[i<<1|1].r-tree[i<<1|1].l+1;
tree[i<<1|1].n2=0;
}
else if(tree[i].lazy==2)//银
{
tree[i<<1].lazy=tree[i<<1|1].lazy=2;
tree[i<<1].n1=0;
tree[i<<1].n2=tree[i<<1].r-tree[i<<1].l+1;
tree[i<<1|1].n1=0;
tree[i<<1|1].n2=tree[i<<1|1].r-tree[i<<1|1].l+1;
}
else//金
{
tree[i<<1].lazy=tree[i<<1|1].lazy=3;
tree[i<<1].n1=0;
tree[i<<1].n2=0;
tree[i<<1|1].n1=0;
tree[i<<1|1].n2=0;
}
tree[i].lazy=0;
}
void update(int i,int l,int r,int v)
{
if(tree[i].l==l&&tree[i].r==r)
{
tree[i].lazy=v;
if(v==1)//铜
{
tree[i].n1=tree[i].r-tree[i].l+1;
tree[i].n2=0;
}
else if(v==2)//银
{
tree[i].n1=0;
tree[i].n2=tree[i].r-tree[i].l+1;
}
else//金
tree[i].n1=tree[i].n2=0;
return ;
}
if(tree[i].lazy)
down(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
update(i<<1,l,r,v);
else if(l>mid)
update(i<<1|1,l,r,v);
else
{
update(i<<1,l,mid,v);
update(i<<1|1,mid+1,r,v);
}
tree[i].n1=tree[i<<1].n1+tree[i<<1|1].n1;//修改铜质长度
tree[i].n2=tree[i<<1].n2+tree[i<<1|1].n2;//修改银质长度
}
int get(int i)//得到节点i区间 钩子的总价值
{
return tree[i].n1+tree[i].n2*2+(tree[i].r-tree[i].l-tree[i].n1-tree[i].n2+1)*3;
}
int query(int i,int l,int r)
{
if(tree[i].l==l&&tree[i].r==r)
return get(i);
if(tree[i].lazy)
down(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
return query(i<<1,l,r);
else if(l>mid)
return query(i<<1|1,l,r);
else
return query(i<<1,l,mid)+query(i<<1|1,mid+1,r);
}
int main()
{
int n,m,t;
scanf("%d",&t);
int times=0;
while(t--)
{
memset(tree,0,sizeof(tree));
scanf("%d%d",&n,&m);
build(1,1,n);
int t1,t2,t3;
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
update(1,t1,t2,t3);
}
printf("Case %d: The total value of the hook is %d.\n",++times,query(1,1,n));
}
return 0;
}
下面提供另外一种思路， 维护的是该区间钩子的材质， 如果该区间钩子的材质是混杂的话， 就用-1表示。无需lazy标记。 效率比上面那个方法快很多， 但可能稍微有点难以理解。
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=100005;
struct node
{
int l,r,c; //c代表该区间材质 -1代表杂的
};
node tree[maxn<<2];
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].c=1; //初始化为铜
if(l==r)
return ;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void update(int i,int l,int r,int v)
{
if(tree[i].c==v) //材质相同 就不用改了
return ;
if(tree[i].l==l&&tree[i].r==r) //刚好是要修改的区间
{
tree[i].c=v; //修改材质
return ;
}
if(tree[i].c!=-1) //该区间只有一种材质 但是又修改了部分材质
{
tree[i<<1].c=tree[i<<1|1].c=tree[i].c; //子区间材质修改成跟当前区间一样的
tree[i].c=-1; //该区间现在是杂的
}
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid)
update(i<<1,l,r,v);
else if(l>mid)
update(i<<1|1,l,r,v);
else
{
update(i<<1,l,mid,v);
update(i<<1|1,mid+1,r,v);
}
}
int query(int i,int l,int r)
{
if(tree[i].c!=-1) //只有一种材质
return (tree[i].r-tree[i].l+1)*tree[i].c;
int mid=(l+r)>>1;
return query(i<<1,l,mid)+query(i<<1|1,mid+1,r);
}
int main()
{
int n,m,t,times=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(1,1,n);
int t1,t2,t3;
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
update(1,t1,t2,t3);
}
printf("Case %d: The total value of the hook is %d.\n",++times,query(1,1,n));
}
return 0;
}