2020 CCPC 绵阳7-10 Joy of Handcraft（线段树）

本文主要是介绍2020 CCPC 绵阳7-10 Joy of Handcraft（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
题意：
每个灯泡亮的时间为 $2kt_i+1,2kt_i+t_i]$ ,灭的时间为 $2kt_i+t_i+1,2kt_i+2*t_i]$ ，每个灯泡亮度为 $a [i]$ 。
求每个时刻最亮灯泡亮度。

思路：
将相同周期灯泡合并，那么所有灯泡周期都不同了。这样的话更新区间的复杂度就是一个调和级数，所以可以用线段树维护。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 1e5 + 7;
struct Node {int x,t;
}a[maxn];int cmp(Node a,Node b) {return a.t < b.t;
}struct Tree {int l,r;int mx,lazy;
}t[maxn << 2];void pushdown(int i) {if(t[i].lazy) {t[i * 2].lazy = max(t[i].lazy,t[i * 2].lazy);t[i * 2 + 1].lazy = max(t[i].lazy,t[i * 2 + 1].lazy);t[i * 2].mx = max(t[i].lazy,t[i * 2].mx);t[i * 2 + 1].mx = max(t[i].lazy,t[i * 2 + 1].mx);t[i].lazy = 0;}
}void pushup(int i) {t[i].mx = max(t[i * 2].mx,t[i * 2 + 1].mx);
}void build(int i,int l,int r) {t[i].l = l;t[i].r = r;t[i].mx = t[i].lazy = 0;if(l == r) {return;}int m = (l + r) >> 1;build(i * 2,l,m);build(i * 2 + 1,m + 1,r);pushup(i);
}void update(int i,int x,int y,int v) {if(x <= t[i].l && t[i].r <= y) {t[i].lazy = max(t[i].lazy,v);t[i].mx = max(t[i].mx,v);return;}pushdown(i);int m = (t[i].l + t[i].r) >> 1;if(x <= m) update(i * 2,x,y,v);if(y > m) update(i * 2 + 1,x,y,v);pushup(i);
}int query(int i,int x) {if(t[i].l == t[i].r) {return t[i].mx;}pushdown(i);int m = (t[i].l + t[i].r) >> 1;if(x <= m) return query(i * 2,x);if(x > m) return query(i * 2 + 1,x);return -1;
}int main() {int T;scanf("%d",&T);int kase = 0;while(T--) {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d%d",&a[i].t,&a[i].x);}sort(a + 1,a + 1 + n,cmp);//合并int cnt = 0;a[++cnt] = a[1];for(int i = 2;i <= n;i++) {if(a[i].t == a[cnt].t) {a[cnt].x = max(a[cnt].x,a[i].x);} else {a[++cnt] = a[i];}}n = cnt;build(1,1,m);for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j += a[i].t * 2) {update(1,j,min(m,j + a[i].t - 1),a[i].x);}}printf("Case #%d: ",++kase);for(int i = 1;i <= m;i++) {printf("%d",query(1,i));if(i == m) printf("\n");else printf(" ");}}return 0;
}