Description
Input
Output
输出m行，每行一个整数，代表输入中每次程序变化后系统所需要的空闲内存单位数。
Sample Input
2 31 41 42 2 12 1 11 1 1
Sample Output
231
Data Constraint
对于30%的数据，有1<=n,m<=1000
对于100%的数据，有1<=n,m<=100000
Hint
Solution
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define ls x<<1
#define rs ls|1
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 200005
using namespace std;
I n,m,x,y,z,now[N],f[N];
ll a1,a2,b1,b2;
struct seg{ll x,y;}t[N<<2];
struct qry{ll x,y,k,id;}a[N];
I cmp(qry x,qry y){return x.y<y.y;}
void update(I x){t[x]=seg{t[ls].x+t[rs].x,max(t[ls].y,t[rs].y-t[ls].x)};}
void build(I x=1,I l=1,I r=n){if(l==r){if(!a[l].k) t[x]=seg{a[l].x,a[l].y};return;}I M=l+r>>1;build(ls,l,M),build(rs,M+1,r);update(x);
}
void cge(I k,I A,I B,I x=1,I l=1,I r=n){if(l==r){t[x]=seg{A,B};return;}I M=l+r>>1;if(k<=M) cge(k,A,B,ls,l,M);else cge(k,A,B,rs,M+1,r);update(x);
}
I main(){freopen("allocate.in","r",stdin);freopen("allocate.out","w",stdout);scanf("%d%d",&n,&m);F(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].id=i;F(i,n+1,n+m) scanf("%lld%lld%lld",&a[i].k,&a[i].x,&a[i].y),a[i].id=i-n;n+=m;sort(a+1,a+1+n,cmp);F(i,1,n){if(!a[i].k) now[a[i].id]=i;else f[a[i].id]=i;}build();F(i,1,m){cge(now[a[f[i]].k],0,0);now[a[f[i]].k]=f[i];cge(f[i],a[f[i]].x,a[f[i]].y);printf("%lld\n",t[1].y);}return 0;
}