1.并查集
#include<bits/stdc++.h>
using namespace std;
int l[100010], r[100010], k[100010], fa[100010];
int find(int x){if(x == fa[x]) return x; return fa[x] = find(fa[x]);}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt; cin >> tt;
for(int t = 1; t <= tt; t++) {
int n, m; cin >> n >> m;
for(int i = 1; i <= n + 2; i++) fa[i] = i;//每一个祖宗为自己
for(int i = 0; i < m; i++) cin >> l[i] >> r[i] >> k[i];
int ans = 0;
for(int i = m - 1; i >= 0; i--)
//因为钩子最后是什么材质由靠后的操作决定,所以从后往前倒序遍历。
//每个并查集维护的是这个节点当前被修改过的最远右区间端点是哪,因为是从后往前遍历,已经被修改过的就是最终结果不能再改了,所以下一个就跳到右端点的下一个位置。
for(int p = find(l[i]); p <= r[i]; p = fa[p] = find(p + 1)) ans += k[i];//一直往后面找祖宗
for(int i = 1; i <= n; i ++) ans += (find(i) == i);//没被赋值的值为1
cout << "Case "<< t << ": The total value of the hook is " << ans << ".\n";
}
return 0;
}
2.
区间修改线段树
#include<iostream>
using namespace std;
const int N=100010;
struct Segment{
int l,r,sum,lazy;
}seg[N*4];
int T,n,Q,l,r,k;
void pushup(int u){
seg[u].sum=seg[u<<1].sum+seg[u<<1|1].sum;
}
void build(int u,int l,int r){
seg[u]={l,r};
if(l==r){
seg[u].sum=1;
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void pushdown(int u){
auto &root=seg[u],&left=seg[u<<1],&right=seg[u<<1|1];
if(root.lazy){
left.lazy=root.lazy,left.sum=(left.r-left.l+1)*root.lazy;
right.lazy=root.lazy,right.sum=(right.r-right.l+1)*root.lazy;
root.lazy=0;
}
}
void modify(int u,int l,int r,int k){
if(seg[u].l>=l&&seg[u].r<=r){
seg[u].lazy=k;
seg[u].sum=(seg[u].r-seg[u].l+1)*k;
}else{
//如果要用到下一层,就要把当前层的lazy放到下一层,并更新下一层。
pushdown(u);
int mid=seg[u].l+seg[u].r>>1;
if(mid>=l) modify(u<<1,l,r,k);
if(mid+1<=r) modify(u<<1|1,l,r,k);
pushup(u);
}
}
int main(){
cin>>T;
for(int i=1;i<=T;i++){
cin>>n>>Q;
build(1,1,n);
while(Q--){
scanf("%d%d%d",&l,&r,&k);
modify(1,l,r,k);
}
printf("Case %d: The total value of the hook is %d.\n",i,seg[1].sum);
}
return 0;
}
只需要查第一个节点的值,不用query。
如果要用query的话
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}