众所周知，当涉及到线段树的区间修改时，往往会引入lazy标记，通过懒惰标记的push_down优化区间修改和查询
如这道板题: 题目链接
1 #include <bits/stdc++.h>
2 #define Lson(x) ((x)<<1)
3 #define Rson(x) ((x)<<1|1)
4 using namespace std;
5
6 const int maxn =1e5;
7 int d[(maxn<<2)+10];
8 int lazy[(maxn<<2)+10];
9 int raw[maxn+10];
10 void build(int s,int t,int p){
11 if(s==t){
12 d[p] = raw[s];
13 return;
14 }
15 int mid = (s+t)>>1;
16 build(s,mid,Lson(p));
17 build(mid+1,t,Rson(p));
18 d[p] = d[Lson(p)] + d[Rson(p)];
19 return;
20 }
21
22 void update(int L,int R,int C,int s,int t,int p){
23 if(L==s&&t==R){
24 d[p] = (R-L+1)*C;
25 lazy[p] = C;
26 return ;
27 }
28
29 int mid = (s+t)>>1;
30
31 if(lazy[p]&&s!=t){//not leaf node and lazy
32 d[Lson(p)] = (mid - s + 1 )*lazy[p];lazy[Lson(p)] = lazy[p];
33 d[Rson(p)] = (t - mid)*lazy[p];lazy[Rson(p)] = lazy[p];
34 lazy[p] = 0;
35 }
36
37 if(R<=mid) update(L,R,C,s,mid,Lson(p));
38 else if(L>mid) update(L,R,C,mid+1,t,Rson(p));
39 else update(L,mid,C,s,mid,Lson(p)) , update(mid+1,R,C,mid+1,t,Rson(p));
40 d[p] = d[Lson(p)] + d[Rson(p)];
41 }
42
43 int query(int L,int R,int s,int t,int p){
44 if(L==s&&t==R){
45 return d[p];
46 }
47
48 int mid = (s+t)>>1;
49 if(lazy[p]&&s!=t){
50 d[Lson(p)] = (mid - s + 1 )*lazy[p];lazy[Lson(p)] = lazy[p];
51 d[Rson(p)] = (t - mid)*lazy[p];lazy[Rson(p)] = lazy[p];
52 lazy[p] = 0;
53 }
54
55 int sum = 0;
56 if(R<=mid) sum+=query(L,R,s,mid,Lson(p));
57 else if(L>mid) sum+=query(L,R,mid+1,t,Rson(p));
58 else sum = query(L,mid,s,mid,Lson(p)) + query(mid+1,R,mid+1,t,Rson(p));
59 return sum;
60 }
61
62 int main(){
63 int N;
64 scanf("%d",&N);
65 for(int i=1;i<=N;++i){
66 scanf("%d",&raw[i]);
67 }
68 build(1,N,1);
69 int Q;
70 scanf("%d",&Q);
71 for (int i = 0; i < Q; ++i) {
72 int op;
73 scanf("%d",&op);
74 if(op) {
75 int L,R,C;
76 scanf("%d%d%d",&L,&R,&C);
77 update(L,R,C,1,N,1);
78 } else {
79 int L,R;
80 scanf("%d%d",&L,&R);
81 printf("%d\n",query(L,R,1,N,1));
82 }
83 }
84 return 0;
85 }
View Code
而关于lazy标记，还有一种标签永久化的思路，请看这题: 题目链接
题意是一个长为 n 的序列 a[n](下标1~n) ，初始时每个元素为0，现在有m次操作L , R ,V将区间[L, R]里小于V的元素更新为V，最后询问每个 ai * i 的异或和。这道题的输入是根据三个初始数字和一个函数不断生成的，可以看做是随机的区间修改。(n<=1e5,m<=5e6)
“区间[L, R]里小于V的元素更新为V”那肯定是有的元素更新有的不更新，而最后的询问是每个元素的值都用上了，值得注意的是只有一个询问。
于是我们可以采用lazy标记永久化的思路，每一次区间修改中没有标记的push_down也没有maintain，只是单纯地更新区间lazy标记（如此线段树只需要存lazy标记），而在最后的查询里DFS搜到底部的过程中，我们只需要记录一路走到该点的最大标记值，然后计算对答案贡献即可。之前打标记复杂度是O(mlogn) 最后DFS遍历所有点O(nlogn)。
1 #include <bits/stdc++.h>
2 #define Lson(x) ((x)<<1)
3 #define Rson(x) ((x)<<1|1)
4 using namespace std;
5
6 const int maxn = 1e5;
7 const unsigned int mod = 1<<30;
8 //const pair<int ,int > KONG = make_pair(0,0);
9 unsigned X,Y,Z;
10 //int d[(maxn<<2)+10];
11 int lazy[(maxn<<2)+10];
12 long long ans;
13 unsigned int RNG61(){
14 X = X^(X<<11);
15 X = X^(X>>4);
16 X = X^(X<<5);
17 X = X^(X>>14);
18 unsigned W = X ^(Y ^ Z);
19 X = Y;
20 Y = Z;
21 Z = W;
22 return Z;
23 }
24
25 void build(int s,int t,int p){
26 if(s==t){
27 // d[p] = 0;
28 lazy[p] = 0;
29 return ;
30 }
31 int mid = (s+t)>>1;
32 build(s,mid,Lson(p));
33 build(mid+1,t,Rson(p));
34 // d[p] = 0;
35 lazy[p] = 0;
36 return;
37 }
38
39 void update(int L,int R,int C,int s,int t,int p){
40 if(C < lazy[p]) return;//根本不用往下搜,剪枝
41
42 if(L==s && R==t){
43 lazy[p] = max(lazy[p],C);
44 return ;
45 }
46 int mid = (s+t) >> 1;
47 if(R<=mid) update(L,R,C,s,mid,Lson(p));
48 else if(L>mid) update(L,R,C,mid+1,t,Rson(p));
49 else update(L,mid,C,s,mid,Lson(p)),update(mid+1,R,C,mid+1,t,Rson(p));
50 }
51
52
53 void DFS(int s,int t,int p,int tmax){
54 tmax = max(lazy[p],tmax);
55 if(s==t){
56 // printf("%d :%d\n",s,tmax);
57 ans ^= 1ll*s*tmax;
58 return;
59 }
60 int mid = (s+t)>>1;
61 DFS(s,mid,Lson(p),tmax);
62 DFS(mid+1,t,Rson(p),tmax);
63 return ;
64 }
65
66 int main(){
67 // __clock_t stt = clock();
68 int T;
69 cin >> T;
70 while(T--){
71 int N,M;
72 cin >> N >> M >> X >> Y >> Z;
73 unsigned int n = static_cast<unsigned int>(N);
74 build(1,N,1);
75 for(int i=1;i<=M;++i){
76 unsigned int f1 = RNG61();
77 unsigned int f2 = RNG61();
78 unsigned int f3 = RNG61();
79 int L = (f1 % n) + 1;
80 int R = (f2 % n) + 1;
81 int V = f3 % (1<<30);
82 update(min(L,R),max(L,R),V,1,N,1);
83 }
84 ans = 0;
85 DFS(1,N,1,0);
86 printf("%lld\n",ans);
87 }
88 // __clock_t ent = clock();
89 // printf("Used Time: %.3lf", static_cast<double>(ent - stt)/1000.0);
90 return 0;
91 }
View Code
开始写的还是TLE了，自己测了测时间大概20秒，DFS遍历所有点是必须的，那么其实可以在打标记时进行剪枝优化:
if(C < lazy[p]) return;//根本不用往下搜,剪枝
当前区间的lazy标记值已经大于修改值C，那么这个lazy标记将会覆盖C的影响，所以没有必要往下方更新。
最后2秒通过，随机数据还是能剪枝不少。