题目大意

有$n$个程序$:p_1,p_2 \cdots p_n$，程序$p_i$已经占用了$a_i$个单位内存，还需要$b_i$个空闲内存就能结束运作，然后返还内存$a_i+b_i$

整台机子运作了$m$分钟，每分钟都有且只有一个程序改变了它的状态($a_i,b_i$),求在那一分钟至少需要多少空闲内存才能运作所有程序

数据范围

$1\leqslant n,m\leqslant 10^5$

题解

戳我

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define lp p<<1
#define rp p<<1|1 
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f; 
}

int n,m,cnt;
struct tree{ll a,b;}t[800500];
struct data{int id,a,b;}q[200500];
int num[200500],hash[200500];

inline int bin(int x){
    int l=1,r=cnt;
    while (l<=r){
        int mid=(l+r)>>1;
        if (hash[mid]<x) l=mid+1;
        else r=mid-1;
    }
    return l;
}
void modify(int p,int l,int r,int x,int a,int b){
    if (l==r){t[p].a+=a;t[p].b=t[p].a?b:0;return;}
    int mid=(l+r)>>1;
    if (x<=mid) modify(lp,l,mid,x,a,b);
    else modify(rp,mid+1,r,x,a,b);
    t[p].a=t[lp].a+t[rp].a;
    t[p].b=t[lp].b+max(t[rp].b-t[lp].a-t[lp].b,0ll);
}
inline void prepare(){
    n=read(),m=read();
    For(i,1,n) q[i]=(data){i,read(),read()},num[i]=q[i].b;
    For(i,n+1,n+m) q[i]=(data){read(),read(),read()},num[i]=q[i].b;
    sort(num+1,num+n+m+1);
    For(i,1,n+m) if (num[i]!=num[i-1]) hash[++cnt]=num[i];
}
inline void solve(){
    For(i,1,n) modify(1,1,cnt,bin(q[i].b),q[i].a,q[i].b);
    For(i,n+1,n+m){
        modify(1,1,cnt,bin(q[q[i].id].b),-q[q[i].id].a,q[q[i].id].b);
        q[q[i].id]=(data){i,q[i].a,q[i].b}; 
        modify(1,1,cnt,bin(q[q[i].id].b),q[q[i].id].a,q[q[i].id].b);
        printf("%I64d\n",t[1].b);
    }
}
int main(){
    prepare();
    solve();
    return 0;
}