Joy of Handcraft Gym - 102822J

題意：

每個燈有亮的周期和亮度，問1~m這段時間燈光最亮是多少

題解：

線段樹維護區間最大值
根據燈的周期向這段區間加亮度k，然后利用線段樹維護區間最大值
但是這樣會超時，加個小優化就ac了（670ms）
我們考慮，因為題目只要求最亮的一段，而且所有燈亮的時間起點是一樣的，也就是如果兩個燈周期一樣，只有亮度高的才會有用，所有我們將所有燈按照亮度排序，每加完一組燈，記錄該周期，后面再出現該周期的就不用加了。因此所有的區間數量為Σi->n（m/ti）= mlogn

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e5+9; struct node{int time,light; }a[maxn]; struct tree{int l,r;int lazy;int sum; }tr[maxn<<2]; bool cmp(node a,node b){return a.light>b.light; } void solve(int rt,int val){tr[rt].sum=max(tr[rt].sum,val);tr[rt].lazy=max(tr[rt].lazy,val); } void pushdown(int rt){solve(rt<<1,tr[rt].lazy);solve(rt<<1|1,tr[rt].lazy);tr[rt].lazy=0; } void pushup(int rt){tr[rt].sum=max(tr[rt<<1].sum,tr[rt<<1|1].sum); } void build(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r;if(l==r){tr[rt].lazy=0;tr[rt].sum=0;return ;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt); } void update(int rt,int l,int r,int k){if(tr[rt].l>r||tr[rt].r<l)return ;if(tr[rt].l>=l&&tr[rt].r<=r){solve(rt,k);return ;}if(tr[rt].lazy)pushdown(rt);update(rt<<1,l,r,k);update(rt<<1|1,l,r,k);pushup(rt); } int query(int rt,int l,int r){if(tr[rt].l>r||tr[rt].r<l)return 0;if(tr[rt].l>=l&&tr[rt].r<=r){return tr[rt].sum;}pushdown(rt);return max(query(rt<<1,l,r),query(rt<<1|1,l,r)); } int vis[maxn]; int main() {int t;cin>>t;int cas=0;while(t--){int n,m;cin>>n>>m;memset(tr,0,sizeof(tr));memset(vis,0,sizeof(vis));build(1,1,m);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].time,&a[i].light);}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(vis[a[i].time])continue;vis[a[i].time]=1;for(int j=0;j!=-1;j++){int l=2*j*a[i].time+1,r=2*j*a[i].time+a[i].time;// printf("l=%d r=%d\n",l,r);if(l>m)break;if(r>m)update(1,l,m,a[i].light);else update(1,l,r,a[i].light);}}printf("Case #%d:",++cas);for(int i=1;i<=m;i++){printf(" %d",query(1,i,i));}printf("\n");}return 0; }

方法二 差分

整體思路，我們對所有燈按照燈光從小到達排序，然后利用差分思想來存燈光，add來存這個燈光的開始時刻，del來存結束時刻
如圖，紅色表示開始時刻，藍色為刪除，紅色到藍色（不含藍色）這一段均為該燈亮的時刻，從藍色開始熄滅

這樣存得到add和del，再查詢答案時，對于每一時刻，加入當前的燈光開始時刻的燈光亮度，然后刪除此刻del中記錄的燈光，利用差分來維護
復雜度是（Ologlogm)
時間：904ms
（注意我們對燈光是排過序的，所以輸出是ans的尾）

差分代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set>using namespace std;const int MAXN = 4e5+5;struct bub {int t, x; }b[MAXN];bool cmp(bub a, bub b) {return a.x>b.x; }bool vis[MAXN]; vector<int> add[MAXN], del[MAXN]; multiset<int> ans;void init(int n) {for(int i=0;i<=n;++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;kase<=T;++kase) {int n, m; scanf("%d%d", &n, &m);init(m);for(int i=0;i<n;++i) { scanf("%d%d", &b[i].t, &b[i].x);}sort(b, b+n, cmp);for(int i=0;i<n;++i) {if(vis[b[i].t]) continue;vis[b[i].t]=true;for(int j=0;j<=m/b[i].t+1;j+=2) {add[j*b[i].t+1].push_back(b[i].x);del[(j+1)*b[i].t+1].push_back(b[i].x);}}printf("Case #%d:", kase);for(int i=1;i<=m;++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;}

總結

以上是生活随笔為你收集整理的Joy of Handcraft Gym - 102822J（线段树或差分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。