UVALive 4108城市天际线,混杂着递归与非递归的线段树

Posted by Cww97 on 2016-03-10

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50842125
题目这里

题意:城市会建设很多摩天楼,从侧面看城市,新楼会把旧楼挡住(如果新楼高度>=旧楼)
每新建一栋楼,会产生一个“建设值”=挡住了多少长度的旧楼(地面看做h=0的楼)
输出建设值总和,
tip:每栋楼产生的“建设值”取决于这栋楼建成之前的状态,故顺序很重要

分析:数据范围10W,楼的一维范围,开一个10W的线段树。
众所周知,线段树是一颗近似的完全二叉树,为何近似呢,最下面一层有一点不均匀
当叶子节点数量恰好是2的n次方的时候,则是完全二叉树。。。
中了zkw的线段树的毒,把线段树直接建到131072=2的k次方。后面超过10的地方,不用管它就好
这样写的好处是。。。。build直接for循环就好了(具体看程序)非常简单,不容易写残
线段树开几个域:max,tag,l,r都可以猜到什么意思了
还可以加个min域来加速更新。。比min小就不用进去了嘛。。
最后一点废话:这题是线段,不是独立的点,所以从l到r,转化成从l到r-1,,,长度就不会比答案多一个了

zkw线段树的区间修改还是没有学会。。。求神犇指教啊
所以本次写的代码只有建树部分是非递归的,其他还是传统的线段树

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=262144,M=131071;
//const int N=40,M=15;
int n,ans;

struct tree{
int l[N],r[N],ma[N],mi[N],tag[N];

void build(){
memset(ma ,0,sizeof(ma ));
memset(mi ,0,sizeof(mi ));
memset(tag,0,sizeof(tag));
for (int i=1+M;i<=M*2+1;i++)l[i]=r[i]=i-M;
for (int i=M;i>=1;i--)l[i]=l[i<<1],r[i]=r[i<<1^1];
}

void down(int t){//无标记或叶子节点无需down
if ((!tag[t])||t>M)return ;
ma[t<<1] = ma[t<<1^1]= ma[t];
mi[t<<1] = mi[t<<1^1]= mi[t];
tag[t<<1]=tag[t<<1^1]=tag[t];
tag[t]=0;
}

void set(int t,int L,int R,int H){
if (mi[t]>H)return;
//printf("T%d:[%d,%d]:%d,%d,%d\n",t,l[t],r[t],ma[t],mi[t],tag[t]);
if (L<=l[t]&&r[t]<=R&&ma[t]<=H){
ans+=r[t]-l[t]+1;
//printf("ans=%d\n",ans);
ma[t]=mi[t]=tag[t]=H;
return;
}
down(t);
int mid=(l[t]+r[t])>>1;
if (L<=mid)set(t<<1 ,L,R,H);
if (mid< R)set(t<<1^1,L,R,H);
ma[t]=max(ma[t<<1],ma[t<<1^1]);
mi[t]=min(mi[t<<1],mi[t<<1^1]);
}
}T;

int main(){
//freopen("fuck.in","r",stdin);
int cas;scanf("%d",&cas);
while (cas--){
scanf("%d",&n);
T.build();
ans=0;int L,R,H;
while (n--){
//printf("ask %d\n",n);
scanf("%d%d%d",&L,&R,&H);
R--;
T.set(1,L,R,H);
//printf("ans=%d\n",ans);
}
printf("%d\n",ans);
}
return 0;
}

边刷题边听歌听到了西游记后传的主题曲
跟室友一起中毒了,,,,看了几集
完全是中国鬼畜的起源啊。。。。。
看完之后蒙蔽了,,,说好的学习呢,,,,啊啊啊啊

这次在F9之前,由于对自己yy出的写法不是很自信
把样例在纸上模拟了一遍,改出了很多错误,还加了min域
模拟样例的纸条:
这里写图片描述
这里写图片描述

还是某犇说的好啊:写线段树要仔细
久违的一遍A啊。。。