区间更新用到的延迟标记，不过是在更新时只更新到最大父区间，不继续往下更新，把更新的状态记录下来。当访问到子区间时再根据相应记录及时更新，pushodown()。
code:
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;
#define SET(arr, what) memset(arr, what, sizeof(arr))
#define FF(i, a) for(i=0; i<a; i++)
#define SD(a) scanf("%d", &a)
#define SSD(a, b) scanf("%d%d", &a, &b)
#define SF(a) scanf("%lf", &a)
#define SS(a) scanf("%s", a)
#define SLD(a) scanf("%lld", &a)
#define PF(a) printf("%d\n", a)
#define PPF(a, b) printf("%d %d\n", a, b)
#define SZ(arr) (int)a.size()
#define SWAP(a,b) a=a xor b;b= a xor b;a=a xor b;
#define read freopen("in.txt", "r", stdin)
#define write freopen("out.txt", "w", stdout)
#define MAX 1<<30
#define ESP 1e-5
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a==-1||a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int maxn = 100001 ;
int sum[maxn<<2] ;
int val[maxn<<2] ;
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;
}
void pushdown(int rt, int cnt){
if(val[rt]){
val[rt<<1] = val[rt<<1|1] = val[rt] ;
sum[rt<<1] = (cnt - (cnt>>1)) * val[rt] ;
sum[rt<<1|1] = (cnt>>1) * val[rt] ;
val[rt] = 0 ;//更新后修改缓存值为0，避免重复更新
}
}
void build(int l, int r, int rt){
val[rt] = 0 ;
sum[rt] = 1 ;
if(r==l) return ;
int m = (l + r) >> 1 ;
build(lson) ;
build(rson) ;
pushup(rt) ;
}
void update(int L, int R, int c, int l, int r, int rt){
if(L<=l&&r<=R){
val[rt] = c ;
sum[rt] = (r - l + 1) * c ;
return ;
}
pushdown(rt, r-l+1) ;//用到子区间，根据父节点的val往下更新
int m = (l + r) >> 1 ;
if(L<=m) update(L, R, c, lson) ;
if(R>m) update(L, R, c, rson) ;
pushup(rt) ;
}
int main(){
int t, n, i, j, m, a, b, c ;
SD(t) ;
FF(i, t){
SSD(n, m) ;
build(1, n, 1) ;
while(m--){
SSD(a, b) ;SD(c) ;
update(a, b, c, 1, n, 1) ;
}
printf("Case %d: The total value of the hook is %d.\n", i+1, sum[1]) ;
}
return 0 ;
}
区间合并看的比较纠结，主要是开始没明白lsum和rsum的准确意义。在更新时也用到了延迟技术。
code:
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;
#define SET(arr, what) memset(arr, what, sizeof(arr))
#define FF(i, a) for(i=0; i<a; i++)
#define SD(a) scanf("%d", &a)
#define SSD(a, b) scanf("%d%d", &a, &b)
#define SF(a) scanf("%lf", &a)
#define SS(a) scanf("%s", a)
#define SLD(a) scanf("%lld", &a)
#define PF(a) printf("%d\n", a)
#define PPF(a, b) printf("%d %d\n", a, b)
#define SZ(arr) (int)a.size()
#define SWAP(a,b) a=a xor b;b= a xor b;a=a xor b;
#define read freopen("in.txt", "r", stdin)
#define write freopen("out.txt", "w", stdout)
#define MAX 1<<30
#define ESP 1e-5
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a==-1||a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int maxn = 50010 ;
int msum[maxn<<2], lsum[maxn<<2], rsum[maxn<<2] ;
int cover[maxn<<2] ;
void pushup(int rt, int cnt){
lsum[rt] = lsum[rt<<1] ;
rsum[rt] = rsum[rt<<1|1] ;
if(lsum[rt]==cnt-(cnt>>1)) lsum[rt] += lsum[rt<<1|1] ;
if(rsum[rt]==(cnt>>1)) rsum[rt] += rsum[rt<<1] ;
msum[rt] = Max(lsum[rt<<1|1]+rsum[rt<<1], Max(msum[rt<<1], msum[rt<<1|1])) ;
}
void pushdown(int rt, int cnt){
if(cover[rt]!=-1){
cover[rt<<1] = cover[rt<<1|1] = cover[rt] ;
msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : cnt - (cnt >> 1) ;
msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (cnt >> 1) ;
cover[rt] = -1 ;
}
}
void build(int l, int r, int rt){
msum[rt] = lsum[rt] = rsum[rt] = r - l + 1 ;
cover[rt] = -1 ;
if(l==r) return ;
int m = (l + r) >> 1 ;
build(lson) ;
build(rson) ;
}
void update(int L, int R, int c, int l, int r, int rt){
if(L<=l&&r<=R){
msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : (r-l+1) ;
cover[rt] = c ;
return ;
}
pushdown(rt, r-l+1) ;
int m = (r + l) >> 1 ;
if(L<=m) update(L, R, c, lson) ;
if(m<R) update(L, R, c, rson) ;
pushup(rt, r-l+1) ;
}
int query(int w, int l, int r, int rt){
if(l==r) return l ;
pushdown(rt, r-l+1) ;
int m = (l + r) >> 1 ;
if(msum[rt<<1]>=w) return query(w, lson) ;//左区间满足
else if(rsum[rt<<1]+lsum[rt<<1|1]>=w) return m - rsum[rt<<1] + 1 ;//区间合并满足
return query(w, rson) ;//只能右区间满足
}
int main(){
int n, m, i, j, t, a, b, q ;
while(~SSD(n, m)){
build(1, n, 1) ;
while(m--){
SD(t) ;
if(t==1){
SD(a) ;
if(msum[1]<a) PF(0) ;
else{
q = query(a, 1, n, 1) ;
PF(q) ;
update(q, q+a-1, 1, 1, n, 1) ;
}
}else{
SSD(a, b) ;
update(a, a+b-1, 0, 1, n, 1) ;
}
}
}
return 0 ;}