Fork me on GitHub

[LA-4108] Skyline 线段树/树状数组+二分

发表于 | 分类于
字数统计: 336字 | 阅读时长 ≈ 2分钟

题面

传送门: LA-4108

样例

Sample Input
1
3
5 11 3
1 10 1
3 13 2
0
Sample Output
14

思路

线段树区间更新维护最大值即可

裸题啊

代码

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
#include<bits/stdc++.h>
using namespace std;
#define lc rt<<1
#define rc rt<<1|1
#define maxn 100010

inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

int ans = 0,n;
struct SegmentTree{
	int lazy[maxn<<2],maxv[maxn<<2];
	void Pushup(int rt)
	{
		maxv[rt] = max(maxv[lc],maxv[rc]);
	}
	void Pushdown(int rt)
	{
		lazy[lc] = max(lazy[lc],lazy[rt]);
		lazy[rc] = max(lazy[rc],lazy[rt]);
	}
	void Update(int rt,int l,int r,int x,int y,int v)
	{
		if (lazy[rt] > v) return ;
		if (x <= l && y >= r && v >= maxv[rt])
		{
			ans += (r-l+1);
			maxv[rt] = v;
			lazy[rt] = v;
			return ;
		}
		if (l == r) return ;
		Pushdown(rt);
		int m = (l+r) >> 1;
		if (x <= m) Update(lc,l,m,x,y,v);
		if (y > m) Update(rc,m+1,r,x,y,v);
		Pushup(rt);
	}
}Tree;
int main(int argc, char *argv[])
{
	int t,f,g,h;
	read(t);
	{
		while(t--)
		{
			ans = 0;
			memset(Tree.lazy,0,sizeof(Tree.lazy));
			memset(Tree.maxv,0,sizeof(Tree.maxv));
			read(n);
			while(n--)
			{
				read(f),read(g),read(h);
				Tree.Update(1,1,maxn,f,g-1,h);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}