SKYLINE
time limit per test 3 second memory limit per test 256 megabytes
题目大意就是:有一个序列,开始时全为零。现有一些操作,将区间[l,r)上小于等于c的数全部改为c,求总修改次数。

传送门:UVA1232

题解

一开始我就想一个区间最大值就行了,但其实不行 比如有左孩子高度:2,右孩子高度:1,他们的父亲在回溯的时候会更新为2,当有一个线段高为2来比较时就忽略了这个区间的右孩子 所以还得记录每个区间的孩子是否被更新过 如果被更新过那肯定得继续递归到孩子再做比较 这里很讨巧的用lazy[num]=-1记为这个区间需要再往下比较 即当lazy[num]!=-1时,那他的值就是这个区间的最大值,且这个区间没有比他小的。因为如果往下更新他孩子的话,这个点的lazy[num]就会置为-1 还有这道题还需要一个剪枝 否则会超时
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
while(sc.hasNext()){
int n=sc.nextInt();
int sum=0;
if(n==0)break;
SegTree tree=new SegTree(100010);
for(int i=0;i<n;i++){
int l=sc.nextInt();
int r=sc.nextInt();
int max=sc.nextInt();
int k=tree.regupdate(l, r, max);
sum+=k;
}
pw.println(sum);
pw.flush();
}
}
}
class SegTree{
long[]tree=new long[400050];
long[]lazy=new long[400050];
int n;
SegTree(int n_){
this.n=1;
while(n<n_){
n*=2;
}
}
void pushdown(int num,int l,int r){
if(lazy[num]!=-1){
tree[num*2+1]=lazy[num];
tree[num*2+2]=lazy[num];
lazy[num*2+1]=lazy[num];
lazy[num*2+2]=lazy[num];
lazy[num]=-1;
}
}
int update(int num,int l,int r,long add,int x,int y){
if(r<=x||l>=y)return 0;
if(lazy[num]!=-1&&tree[num]>add)return 0; //剪枝 如果是一个完整的区间 且大于了 那么就不pushdown下去
if(lazy[num]!=-1){
if(l<=x&&r>=y){
if(tree[num]<=add){
tree[num]=add;
lazy[num]=add;
return y-x;
}
return 0;
}
}
pushdown(num,x,y);
int left=update(num*2+1,l,r,add,x,(x+y)/2);
int right=update(num*2+2,l,r,add,(x+y)/2,y);
tree[num]=Math.max(tree[num*2+1], tree[num*2+2]);
return left+right;
}
int regupdate(int l,int r,int add){
return update(0,l,r,add,0,n);
}
long regquery(int l,int r){
return query(0,l,r,0,n);
}
long query(int num,int l,int r,int x,int y){
if(r<=x||l>=y)return 0;
if(l<=x&&r>=y){
return tree[num];
}
pushdown(num,x,y);
long left=query(num*2+1,l,r,x,(x+y)/2);
long right=query(num*2+2,l,r,(x+y)/2,y);
return left+right;
}
}