背景:在一段区间内将数组所有值改变为另一值.延迟标记

• 延迟标记还可以用在 将区间内数组所有的值增加或者减少一个值

HDU 1698

• 建个空线段树

• 更新所有的延迟标记为1

• change()的原理是:找到所有唯一的一个区间在线段树上的点.然后标记

• 查询要递归遍历到所有的节点

  #include <iostream>
  using namespace std;
  const int maxn = 1e5+5;
  
  struct segementTree {
  	int left,right;
  	int add,sum;
  	#define  left(i) tree[i].left 
  	#define  right(i) tree[i].right
  	#define add(i)  tree[i].add 
  	#define  sum(i) tree[i].sum
  } tree[maxn*4];
  
  void build(int p,int left,int right) {
  	left(p) = left; right(p) = right;
  	if (left == right) return ;
  	int mid = (left(p) + right(p))/2;
  	build(2*p,left,mid);
  	build(2*p+1,mid+1,right);
  }
  
  void pushDown(int p) {
  	if (add(p)) {
  		add(2*p) = add(p);
  		add(2*p+1) = add(p);
  		add(p) = 0;
  	}
  }
  
  void change(int p,int left,int right,int val) {
  	if (left(p)==left && right(p)==right) {
  		add(p) = val;
  		return ;
  	}
  	pushDown(p);
  	int mid = (left(p)+right(p))/2;
  	if (right <= mid) change(p*2,left,right,val);
  	else if (left > mid) change(2*p+1,left,right,val);
  	else {
  		change(p*2,left,mid,val);
  		change(p*2+1,mid+1,right,val);
  	}
  }
  int ans = 0;
  void query(int p,int left,int right) {
  	if (add(p)) {
  		ans += add(p) * (right - left + 1);
  		return ;
  	}
  	if (left == right) return ;
  	int mid = (left(p) + right(p))/2;
  	query(2*p,left,mid);
  	query(2*p+1,mid+1,right);
  	return ;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	int times; cin>>times;
  	int n,m,u,v,w,cnt=0;
  	while (times--) {
  		ans = 0;
  		scanf("%d%d",&n,&m);
  	
  		build(1,1,n);
  		change(1,1,n,1);
  		for (int i=1; i<=m; i++) {
  			scanf("%d%d%d",&u,&v,&w);
  			change(1,u,v,w);
  		}
  		query(1,1,n);
  		printf("Case %d: The total value of the hook is %d.\n",++cnt,ans);
  	}
  	return 0;
  }

  思维:

• 存读入.然后遍历每一个点.

• 从后往前找到倒数第一个值就退出,加起来

#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int num[maxn];
int e[maxn][3];
int main() {
	//freopen("a.txt","r",stdin);
	int times; scanf("%d",&times);
	for (int k=1; k<=times; k++) {
		int n,m; scanf("%d%d",&n,&m);
		for (int i=1; i<=m; i++) 
			scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
		int val,sum=0;
		for (int i=1; i<=n; i++) { //遍历每一个位置
			val = 1;
			for (int j=m; j>=0; j--) {
				if (e[j][0]<=i && i<=e[j][1]) {
					val = e[j][2];
					break;
				}
			}
			sum += val;
		}
		printf("Case %d: The total value of the hook is %d.\n",k,sum);
	}
	return 0;
}