【GDKOI2014】JZOJ2020年8月13日提高组T4 内存分配

【GDKOI2014】JZOJ2020年8月13日提高组T4 内存分配

题目

Description

Input

Output

输出m行，每行一个整数，代表输入中每次程序变化后系统所需要的空闲内存单位数。

Sample Input

2 3
1 4
1 4
2 2 1
2 1 1
1 1 1

Sample Output

2
3
1

Data Constraint

对于30%的数据，有1<=n,m<=1000
对于100%的数据，有1<=n,m<=100000

Hint

题解

题意

有 $n$个点
每个点有两个值 $a$, $b$
当节点 $i$加上 $b_i$时它就会消失，贡献 $a_i+b_i$
每秒都会有个点的 $a_i$和 $b_i$改变
问最小初始费用

分析

发现有修改
易想到线段树
设 $sum[l][r]$表示 $\sum_{i=l}^{r}a[i]$
$ans[l][r]$表示 $l$~ $r$的最小答案
那么可以用线段树维护
顺便把 $ans$和 $sum$改为一维
动态开点

Code

#include<bits/stdc++.h>
#define inf 2147483647
#define rg register
using namespace std;
struct node
{long long size,rs,ls,val;
}tree[4000005];
long long n,m,j,tot,a[1000005],b[1000005],ans[4000005];
void ins(long long now,long long l,long long r,long long p,long long q)
{if (l==r){tree[now].val+=p;tree[now].size++;ans[now]=q;return;}long long mid=(l+r)>>1;if (q<=mid){if (tree[now].ls==0) tree[now].ls=++tot;ins(tree[now].ls,l,mid,p,q);}else{if (tree[now].rs==0) tree[now].rs=++tot;ins(tree[now].rs,mid+1,r,p,q);}tree[now].val=tree[tree[now].ls].val+tree[tree[now].rs].val;ans[now]=max(ans[tree[now].ls],ans[tree[now].rs]-tree[tree[now].ls].val);
}
void del(long long now,long long l,long long r,long long p,long long q)
{if (l==r){tree[now].val-=p;tree[now].size--;if (tree[now].size==0) ans[now]=0;return;}long long mid=(l+r)>>1;if (q<=mid){if (tree[now].ls==0) tree[now].ls=++tot;del(tree[now].ls,l,mid,p,q);}else{if (tree[now].rs==0) tree[now].rs=++tot;del(tree[now].rs,mid+1,r,p,q);}tree[now].val=tree[tree[now].ls].val+tree[tree[now].rs].val;ans[now]=max(ans[tree[now].ls],ans[tree[now].rs]-tree[tree[now].ls].val);
}
int main()
{freopen("test.in","r",stdin);freopen("test.out","w",stdout);scanf("%lld%lld",&n,&m);tot=1;for (rg long long i=1;i<=n;++i){scanf("%lld%lld",&a[i],&b[i]);ins(1,0,inf,a[i],b[i]);}for (rg long long i=1;i<=m;i++){scanf("%lld",&j);del(1,0,inf,a[j],b[j]);scanf("%lld%lld",&a[j],&b[j]);ins(1,0,inf,a[j],b[j]);printf("%lld\n",ans[1]);}return 0;
}