线段树(lazy)-hdu1689

题目链接:https://vjudge.net/problem/HDU-1698

题目描述:

线段树(lazy)-hdu1689线段树(lazy)-hdu1689

现在Pudge想做一些操作。让我们将钩子的连续金属棒从1编号到N。对于每个操作,Pudge可以将连续金属棒(编号为X到Y)更改为铜棒、银棒或金棒。钩的总值是N根金属棒的总和。更确切地说,每种棍棒的价值计算如下:对于每个铜棒,其值为1。对于每个银棒,其值为2。对于每个金棒,其值为3。Pudge希望知道在执行操作后钩子的总值。你可以认为原来的钩子是用铜棒做的。

输入:

输入由几个测试用例组成。输入的第一行是实例的数目。不超过10例。对于每种情况,第一行包含一个整数N,1<=N<=100000,它是Pudge的钩子的棒的数量,而第二行包含一个整数Q,0<=Q<=100000,它是操作的数量。接下来的Q行,每行包含三个整数X,Y,1<=X<=Y<=N,Z,1<=Z<=3,它定义了一个操作:将编号从X到Y的棒变为金属类Z,其中Z=1表示铜类,Z=2表示银类,Z=3表示金类。

输出:

对于每种情况,在操作之后用表示钩子总值的行中打印出钩子的总价值。使用示例中的格式。

代码实现:

 #include <cstdio>

 using namespace std;
const int MAXN = 1e6;
int N;
typedef long long ll; struct node{
int l,r;
ll sum,lazy;
void update(ll x){//将(r-l)之间的value值变为x,即对sum进行修改
sum=1ll*(r-l+)*x;///1LL是为了在计算时,把int类型的变量转化为long long,然后再赋值给long long类型的变量。
lazy=x;
}
}tree[MAXN<<];
//相当于压栈操作
void push_up(int x){
tree[x].sum=tree[x<<].sum+tree[x<<|].sum;
} void push_down(int x){
ll lazyval=tree[x].lazy;
if(lazyval>){
tree[x<<].update(lazyval);
tree[x<<|].update(lazyval);
tree[x].lazy=;//将其变为0,便于后续操作,因为后续还可能对该区间做更改
}
}
//build(1,1,n),从第一个区间开始建立
void build(int x,int l,int r){
tree[x].lazy=tree[x].sum=;
tree[x].l=l;tree[x].r=r;
if(l==r){
tree[x].sum=;
return;
}
int mid=(l+r)/;
build(x<<,l,mid);
build(x<<|,mid+,r);
push_up(x);//相当于压栈操作
}
//update(1,l,r,val),从第一个区间开始更新
void update(int x,int l,int r,ll val){
int L=tree[x].l,R=tree[x].r;
if(l<=L && R<=r){//保证区间[L,R]处在区间(l,r)内部
tree[x].update(val);//直接进入结构体内部对sum值进行修改
return ;
}
push_down(x);
int mid=(L+R)/;
if(mid>=l)
update(x<<,l,r,val);
if(mid<r)
update(x<<|,l,r,val);
push_up(x);
}
//query(1,1,N),从第一个区间开始查询
ll query(int x,int l,int r){
int L=tree[x].l,R=tree[x].r;
if(l<=L && R<=r)
return tree[x].sum;
push_down(x);
int mid=(L+R)/;
ll ans=;
if(mid>=l)
ans+=query(x<<,l,r);
if(mid<r)
ans+=query(x<<|,l,r);
return ans;
} int main(){
int T;
scanf("%d",&T);
int cae=;
while(T--){
scanf("%d",&N);
build(,,N);
int M;scanf("%d",&M);
while(M--){
int l,r;
ll val;
scanf("%d%d%lld",&l,&r,&val);
update(,l,r,val);
}
printf("Case %d: The total value of the hook is %lld.\n",++cae,query(,,N));
}
return ;
}
上一篇:【C++实现python字符串函数库】strip、lstrip、rstrip方法


下一篇:【C++实现python字符串函数库】二:字符串匹配函数startswith与endswith