解析
也就是说建一棵权值线段树维护这些信息。要注意的是每次的最优解必然是 (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
" , seg[1].b);
}
}