【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;

}