洛谷P 083レンタル教室

ブログはもっと良いbossbaby's blogを食べます

構想

セグメントツリー

直接線分樹メンテナンスしようqwq

コード#コード#

#include
#define lid id<<1
#define rid id<<1|1
#define MAXN 1000010
#define LL long long
using namespace std;
struct SEG{
    int l,r;
    LL minn,lazy;
}tr[MAXN<<2];
LL a[1000010];
int n,m;
void pushup(int id){
    tr[id].minn=min(tr[lid].minn,tr[rid].minn);
}
void pushnow(int id,int v){
    tr[id].lazy+=v;
    tr[id].minn+=v;
}
void pushdown(int id){
    if(tr[id].lazy){
        pushnow(lid,tr[id].lazy);
        pushnow(rid,tr[id].lazy);
        tr[id].lazy=0;
    }
}
void build(int id,int l,int r){
    tr[id].l=l,tr[id].r=r;
    if(l==r){
        tr[id].minn=a[l];
        tr[id].lazy=0;
        return;
    }
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    pushup(id);
}
void update(int id,int l,int r,LL v){
    pushdown(id);
    if(tr[id].l>=l&&tr[id].r<=r){
        pushnow(id,v);
        return;
    }
    int mid=(tr[id].l+tr[id].r)>>1;
    if(l<=mid)
    update(lid,l,r,v);
    if(r>=mid+1)
    update(rid,l,r,v);
    pushup(id);
}
LL query(int id,int l,int r){
    pushdown(id);
    if(tr[id].l>=l&&tr[id].r<=r){
        return tr[id].minn;
    }
    int mid=(tr[id].l+tr[id].r)>>1;
    LL ans=LLONG_MAX;
    if(l<=mid)
    ans=min(ans,query(lid,l,r));
    if(r>=mid+1)
    ans=min(ans,query(rid,l,r));
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=n;i++){
        LL d,s,t;
        cin>>d>>s>>t;
        if(query(1,s,t)

以上は偽物

洛谷吸酸素90

構想

にぶん

二分はいつできないのか、接頭辞と差分メンテナンス

コード#コード#

#include
#define MAXN 1000010
#define LL long long
using namespace std;
LL a[MAXN],d[MAXN],c[MAXN],sum[MAXN];
int n,m,s[MAXN],t[MAXN];
bool check(int x){
    memset(c,0,sizeof(c));
    for(int i=1;i<=x;i++){
        c[s[i]]+=d[i];
        c[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+c[i];
        if(sum[i]>a[i])return 0;
    }
    return 1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>d[i]>>s[i]>>t[i];
    int l=1,r=m;
    if(check(m)){cout<<0<>1;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    cout<

転載先:https://www.cnblogs.com/bossbaby/p/11353218.html