首页 > 代码库 > 【UVA】1232 - SKYLINE(线段树减枝)
【UVA】1232 - SKYLINE(线段树减枝)
注意中间的减枝,还需要用一个tr[i]记录结点的值,用col[i]记录结点区间是否被全覆盖。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 111111; const int maxd = 100001; #define lson pos<<1 #define rson pos<<1|1 int col[maxn << 2]; int tr[maxn << 2]; int ret; void pushdown(int pos){ if(col[pos] != -1){ tr[lson] = col[pos]; tr[rson] = col[pos]; col[lson]= col[pos]; col[rson]= col[pos]; col[pos] = -1; } return; } void Query(int L,int R,int l,int r,int pos,int value){ if(col[pos] != -1 && tr[pos] > value) return; //这个减枝非常重要,如果不加就TLE了 if(col[pos] != -1){ //这个区间是一个统一区间 if(L <= l && r <= R){ if(value >= tr[pos]){ ret += (r - l + 1); tr[pos] = value; //区间赋值 col[pos]= value; //懒惰标记 } return; } } pushdown(pos); int m = (l + r) >> 1; if(L <= m) Query(L,R,l,m,lson,value); if(R > m) Query(L,R,m + 1,r,rson,value); } int main(){ int T; scanf("%d",&T); while(T--){ int n = 0,m; ret = 0; scanf("%d",&m); memset(col,0,sizeof(col)); memset(tr,0,sizeof(tr)); for(int i = 0; i < m; i++){ int L,R,v; scanf("%d%d%d",&L,&R,&v); Query(L,R - 1,1,maxd,1,v); } printf("%d\n",ret); } return 0; }
【UVA】1232 - SKYLINE(线段树减枝)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。