时间戳

首页 > 技术文章 > J. Joy of Handcraft

J. Joy of Handcraft

PdrEam 2020-11-27 16:08 原文

每个灯泡会闪ti分钟，然后灭ti分钟。

灯泡闪的时候亮度为bi

最后问每分钟最亮的亮度是多少。

 

首先先对灯泡排序，这样相同t值的不重复更新

灯泡去重之后最多只有m个。

线段树维护”时间“这个区间上的最大值。

最多的情况下，m要被更新m/1+m/2+m/3…+m/m=mlogm

区间个数是个调和级数

最后乘上线段树的logm，时间复杂度为mloglogm，可以ac

#include<bits/stdc++.h>
#define inf 1e18
#define ll long long 
#define ull unsigned long long 
#define int long long
#define PI acos(-1.0)
#define PII pair<int,int>
using namespace std;
const int N = 2e5+7 , M = N * 2;
const int mod = 1e9+7;
int m,p,n,las,vis[N];
struct bumb{
    int t,x;
}b[N];
int cmp(bumb xx,bumb yy){
    return xx.x>yy.x;
}
struct node{
    int l,r;
    int v;
    int lz;
}tr[N*4];
void pushdown(int u,int l,int r){
    tr[l].lz = max(tr[l].lz,tr[u].lz);
    tr[r].lz = max(tr[r].lz,tr[u].lz);
    tr[l].v = max(tr[l].v,tr[u].lz);
    tr[r].v = max(tr[r].v,tr[u].lz);
    tr[u].lz = 0;
}
void pushdown(int u){
    pushdown(u,u<<1,u<<1|1);
}
void pushup(int u){
    tr[u].v = max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r){
    tr[u]={l,r,0,0};
    if(l==r)    return ;
    int mid = l + r >>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int k){
    if(l<=tr[u].l&&r>=tr[u].r){
        tr[u].lz = max(tr[u].lz,k);
        tr[u].v = max(tr[u].v,k);
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >>1;
    if(l<=mid)    modify(u<<1,l,r,k);
    if(r>mid)    modify(u<<1|1,l,r,k);
    pushup(u);
}
int query(int u,int l,int r){
    if(l<=tr[u].l&&r>=tr[u].r)
        return tr[u].v;
    pushdown(u);
    int ans=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)        ans=max(ans,query(u<<1,l,r));
    if(r>mid)        ans=max(ans,query(u<<1|1,l,r));
    return ans;
}
void solve(){
    memset(vis,0,sizeof(vis));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&b[i].t,&b[i].x);
    sort(b+1,b+1+n,cmp);
    build(1,1,m);
    for(int i=1;i<=n;++i){
        if(vis[b[i].t]==1)    continue;
        vis[b[i].t]=1;
        int st=1,ed=b[i].t;
        while(st<=m){
            modify(1,st,min(ed,m),b[i].x);
            st=st+2*b[i].t;ed=ed+2*b[i].t;
        }
    }
    for(int i=1;i<=m;++i)
        printf(" %lld",query(1,i,i));
    printf("\n");
}
signed main(){
    int t=1;
    scanf("%lld",&t);
    for(int _=1;_<=t;++_){
        printf("Case #%lld:",_);
        solve();
    }
    return 0;
}

 线段树的做法会过于繁琐

如果从大到小染色，那么先染色的时间点一定不会再被更优的更新

在这里可以用并查集来维护已经染色的区间

这样就可以快速的跳过染色过的区间

#include<bits/stdc++.h>
#define inf 1e18
#define ll long long 
#define ull unsigned long long 
#define int long long
#define PI acos(-1.0)
#define PII pair<int,int>
using namespace std;
const int N = 2e5+7 , M = N * 2;
const int mod = 1e9+7;
int m,p,n,las,vis[N],ans[N],fa[N];
struct bumb{
    int t,x;
}b[N];
int cmp(bumb a,bumb b){
    return a.x>b.x;
}
int find(int x){
    if(x == fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void solve(){
    memset(vis,0,sizeof(vis));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&b[i].t,&b[i].x);
    }
    for(int i=1;i<=m;++i){
        ans[i] = 0;fa[i] = i;
    }
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;++i){
        if(vis[b[i].t]==1)    continue;
        vis[b[i].t]=1;
        
        for(int st = 1;st <= m;st=st+2*b[i].t){//区间起点 
            for(int pos = st;pos<st+b[i].t && pos<=m;pos++){//更新区间 
                if(ans[pos]==0)    ans[pos]=b[i].x,fa[pos-1]=pos;
                else            pos = find(pos);//直接跳到已经染色过的末尾 
            }
        }
    }
    for(int i=1;i<=m;++i)
        printf(" %lld",ans[i]);
    printf("\n");
}
signed main(){
    int t=1;
    scanf("%lld",&t);
    for(int _=1;_<=t;++_){
        printf("Case #%lld:",_);
        solve();
    }
    return 0;
}

 

推荐阅读