这题有一个显然不优的正解。
思路
对于一个进程 ({a_i,b_i}) ，其需要的额外的内存为 (b_i-sumlimits_{b_j<b_i}) ，也就是 (b_i-) 已经释放的内存和。
那么对于所有的进程，需要的内存就为每一个进程需要内存的最大值，即 (max{left{b_i-sumlimits_{b_j<b_i} ight}})
感性理解一下就是最大的“断层”。证明就算了
这个式子可以用线段树维护，我们对于每一个进程，把 (b_i+1) 及以后减去 (a_i) ，每次修改把之前的贡献去掉再加上新的即可。
一开始把所有的 (b_i) 先扔进去。
如果用线段树做需要离散化，由于 (b_i) 排序后是单调递增的，所以不会影响正确性。同时，要注意维护所有 (b_i) 的最大值，最大值后的值不能查询（但还要正常修改，因为最大值可能变大），这个可以多记录一个 (cnt) 表示区间内是否有进程完成。当然，每次修改时也要把单个点的 (cnt) 修改掉。（所以显然很慢）
当然，使用可以区间修改的平衡树也许可以完美避免上述问题。但我不知道怎么打
Code
由于不(lan)喜(de)欢(bei) STL离散化，以及需要跨数组离散化，这里使用指针离散化。
#include<cstdio>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
struct tree{
long long mx,cnt,s;
}t[600010];
int n,m,mx=1,a[200010][2],c[200010][3],*l[200010],num[200010];
template<typename T>void read(T &x){
char c=getchar();
for(;c<33;c=getchar());
for(x=0;47<c&&c<58;x=x*10+c-48,c=getchar());
}
bool comp(int *x,int *y){
return(*x<*y);
}
void pushdown(int m){
t[m<<1].s+=t[m].s;t[m<<1].mx+=t[m].s;
t[m<<1|1].s+=t[m].s;t[m<<1|1].mx+=t[m].s;
t[m].s=0;
}
void update(int m){
t[m].mx=max(t[m<<1].mx,t[m<<1|1].mx);
t[m].cnt=t[m<<1].cnt+t[m<<1|1].cnt;
}
void sg(int m,int x,int y,int c,int l,int r){ //区间修改
if(x<=l&&r<=y){
t[m].s+=c;
t[m].mx+=c;
return;
}
pushdown(m);
if(x<=mid){
sg(m<<1,x,y,c,l,mid);
}
if(y>mid){
sg(m<<1|1,x,y,c,mid+1,r);
}
update(m);
}
void point(int m,int x,int z,int l,int r){ //对cnt进行修改
if(l==r){
t[m].cnt+=z;
return;
}
pushdown(m);
if(x<=mid){
point(m<<1,x,z,l,mid);
}else{
point(m<<1|1,x,z,mid+1,r);
}
update(m);
}
int pre(int m,int l,int r){ //找最大值
if(t[m<<1|1].cnt){
return(pre(m<<1|1,mid+1,r));
}else if(l==r){
return(r);
}else{
return(pre(m<<1,l,mid));
}
}
long long call(int m,int x,int y,int l,int r){ //查询
if(x<=l&&r<=y){
return(t[m].mx);
}
pushdown(m);
long long re=0;
if(x<=mid){
re=call(m<<1,x,y,l,mid);
}
if(y>mid){
re=max(re,call(m<<1|1,x,y,mid+1,r));
}
update(m);
return(re);
}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++){
read(a[i][0]);read(a[i][1]);
l[i]=&a[i][1];
}
for(int i=1;i<=m;i++){
read(c[i][0]);read(c[i][1]);read(c[i][2]);
l[i+n]=&c[i][2];
}
sort(l+1,l+n+m+1,comp);
for(int i=1;i<n+m;i++){
if(*l[i]<*l[i+1]){
num[mx]=*l[i];
*l[i]=mx++;
}else{
*l[i]=mx;
}
}
num[mx]=*l[n+m];
*l[n+m]=mx;
for(int i=1;i<=mx;i++){
sg(1,i,i,num[i],1,mx);
}
for(int i=1;i<=n;i++){
sg(1,a[i][1]+1,mx,-a[i][0],1,mx);
point(1,a[i][1]+1,1,1,mx);
}
for(int i=1;i<=m;i++){
point(1,a[c[i][0]][1]+1,-1,1,mx);
sg(1,a[c[i][0]][1]+1,mx,a[c[i][0]][0],1,mx);
a[c[i][0]][0]=c[i][1];a[c[i][0]][1]=c[i][2];
point(1,a[c[i][0]][1]+1,1,1,mx);
sg(1,a[c[i][0]][1]+1,mx,-a[c[i][0]][0],1,mx);
printf("%lld
",call(1,1,pre(1,1,mx),1,mx));
}
}