九江企业网站制作,为客户网站做产品描述,wordpress 多商家插件,有了网站怎么做优化Joy of Handcraft Gym - 102822J
题意#xff1a;
每个灯有亮的周期和亮度#xff0c;问1~m这段时间灯光最亮是多少
题解#xff1a;
线段树维护区间最大值 根据灯的周期向这段区间加亮度k#xff0c;然后利用线段树维护区间最大值 但是这样会超时#xff0c;加个小优…Joy of Handcraft Gym - 102822J
题意
每个灯有亮的周期和亮度问1~m这段时间灯光最亮是多少
题解
线段树维护区间最大值 根据灯的周期向这段区间加亮度k然后利用线段树维护区间最大值 但是这样会超时加个小优化就ac了670ms 我们考虑因为题目只要求最亮的一段而且所有灯亮的时间起点是一样的也就是如果两个灯周期一样只有亮度高的才会有用所有我们将所有灯按照亮度排序每加完一组灯记录该周期后面再出现该周期的就不用加了。因此所有的区间数量为Σi-nm/ti mlogn
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e59;
struct node{int time,light;
}a[maxn];
struct tree{int l,r;int lazy;int sum;
}tr[maxn2];
bool cmp(node a,node b){return a.lightb.light;
}
void solve(int rt,int val){tr[rt].summax(tr[rt].sum,val);tr[rt].lazymax(tr[rt].lazy,val);
}
void pushdown(int rt){solve(rt1,tr[rt].lazy);solve(rt1|1,tr[rt].lazy);tr[rt].lazy0;
}
void pushup(int rt){tr[rt].summax(tr[rt1].sum,tr[rt1|1].sum);
}
void build(int rt,int l,int r){tr[rt].ll;tr[rt].rr;if(lr){tr[rt].lazy0;tr[rt].sum0;return ;}int midlr1;build(rt1,l,mid);build(rt1|1,mid1,r);pushup(rt);
}
void update(int rt,int l,int r,int k){if(tr[rt].lr||tr[rt].rl)return ;if(tr[rt].lltr[rt].rr){solve(rt,k);return ;}if(tr[rt].lazy)pushdown(rt);update(rt1,l,r,k);update(rt1|1,l,r,k);pushup(rt);
}
int query(int rt,int l,int r){if(tr[rt].lr||tr[rt].rl)return 0;if(tr[rt].lltr[rt].rr){return tr[rt].sum;}pushdown(rt);return max(query(rt1,l,r),query(rt1|1,l,r));
}
int vis[maxn];
int main()
{int t;cint;int cas0;while(t--){int n,m;cinnm;memset(tr,0,sizeof(tr));memset(vis,0,sizeof(vis));build(1,1,m);for(int i1;in;i){scanf(%d%d,a[i].time,a[i].light);}sort(a1,a1n,cmp);for(int i1;in;i){if(vis[a[i].time])continue;vis[a[i].time]1;for(int j0;j!-1;j){int l2*j*a[i].time1,r2*j*a[i].timea[i].time;// printf(l%d r%d\n,l,r);if(lm)break;if(rm)update(1,l,m,a[i].light);else update(1,l,r,a[i].light);}}printf(Case #%d:,cas);for(int i1;im;i){printf( %d,query(1,i,i));}printf(\n);}return 0;
}
方法二 差分
整体思路我们对所有灯按照灯光从小到达排序然后利用差分思想来存灯光add来存这个灯光的开始时刻del来存结束时刻 如图红色表示开始时刻蓝色为删除红色到蓝色不含蓝色这一段均为该灯亮的时刻从蓝色开始熄灭 这样存得到add和del再查询答案时对于每一时刻加入当前的灯光开始时刻的灯光亮度然后删除此刻del中记录的灯光利用差分来维护 复杂度是Ologlogm) 时间904ms 注意我们对灯光是排过序的所以输出是ans的尾
差分代码
#includecstdio
#includecstring
#includealgorithm
#includevector
#includesetusing namespace std;const int MAXN 4e55;struct bub {int t, x;
}b[MAXN];bool cmp(bub a, bub b) {return a.xb.x;
}bool vis[MAXN];
vectorint add[MAXN], del[MAXN];
multisetint ans;void init(int n) {for(int i0;in;i) { add[i].clear();del[i].clear();}memset(vis, 0, sizeof(vis));ans.clear();
}int main() {int T; scanf(%d, T);for(int kase 1;kaseT;kase) {int n, m; scanf(%d%d, n, m);init(m);for(int i0;in;i) { scanf(%d%d, b[i].t, b[i].x);}sort(b, bn, cmp);for(int i0;in;i) {if(vis[b[i].t]) continue;vis[b[i].t]true;for(int j0;jm/b[i].t1;j2) {add[j*b[i].t1].push_back(b[i].x);del[(j1)*b[i].t1].push_back(b[i].x);}}printf(Case #%d:, kase);for(int i1;im;i) {for(const auto x: add[i]) {ans.insert(x);}for(const auto y: del[i]) {//ans.erase(y)是删去集合内所有的元素yans.erase(ans.find(y));}if(!ans.empty()) printf( %d, *ans.rbegin());else printf( 0);} printf(\n); }return 0;}
