解析

也就是说建一棵权值线段树维护这些信息。要注意的是每次的最优解必然是 \(b\) 小的先做，故离线排序确定离散后的下标再依次求解

\(Code\)

#include<cstdio>

#include<algorithm>

#define ls (k << 1)

#define rs (ls | 1)

#define LL long long

using namespace std;

const int N = 200005;

int n , m , rd[N];

struct node{

	int a , b , id , k;

}e[N] , ind[N];

struct segment{

	LL a , b;

}seg[N << 2];

inline bool cmp1(node x , node y){return x.b < y.b;}

inline void insert(int l , int r , int k , int x , segment y)

{

	if (l == r)

	{

		seg[k].a = y.a , seg[k].b = y.b;

		return;

	}

	int mid = (l + r) >> 1;

	if (x <= mid) insert(l , mid , ls , x , y);

	else insert(mid + 1 , r , rs , x , y);

	seg[k].a = seg[ls].a + seg[rs].a;

	seg[k].b = max(seg[ls].b , seg[rs].b - seg[ls].a);

}

int main()

{

	scanf("%d%d" , &n , &m);

	for(register int i = 1; i <= n; i++) scanf("%d%d" , &e[i].a , &e[i].b) , e[i].id = i , ind[i] = e[i];

	for(register int i = 1; i <= m; i++)

		scanf("%d%d%d" , &e[i + n].k , &e[i + n].a , &e[i + n].b) , e[i + n].id = i + n , ind[i + n] = e[i + n];

	sort(ind + 1 , ind + n + m + 1 , cmp1);

	for(register int i = 1; i <= n + m; i++) rd[ind[i].id] = i;

	for(register int i = 1; i <= n; i++) insert(1 , n + m , 1 , rd[e[i].id] , segment{e[i].a , e[i].b});

	for(register int i = 1; i <= m; i++)

	{

		insert(1 , n + m , 1 , rd[e[i + n].k] , segment{0 , 0});

		insert(1 , n + m , 1 , rd[e[i + n].id] , segment{e[i + n].a , e[i + n].b});

		rd[e[i + n].k] = rd[e[i + n].id];

		printf("%d\n" , seg[1].b);

	}

}

巴特西

JZOJ 3571. 【GDKOI2014】内存分配

解析

也就是说建一棵权值线段树维护这些信息。要注意的是每次的最优解必然是 \(b\) 小的先做，故离线排序确定离散后的下标再依次求解

\(Code\)

最新文章

热门文章