此题解使用平衡树解决。
1、原始情况
首先，我们考虑未修改的情况。设 \(L_i\) 为吃饭时间，\(a_i\) 为制作所需时间。对于 \(n\) 个居民，假设我们不对做披萨的顺序进行修改，即按照原始顺序的话，可以写出答案：
\(ans = (L_1 - a_1) + [L_2 - (a_1 + a_2] + [L_3 - (a_1 + a_2 + a_3)] ......\)
以此类推，整理后即可得到：
\(ans = (L_1 + L_2 + L_3 + ..... + L_n) - [na_1 + (n-1)a_2 + (n-2)a_3 + ...... + a_n]\)
不难看出，送披萨的先后顺序对于 \(L_i\) 来说是没有影响的。而对于后半部分，我们要想使得总答案最大，肯定要使得 \(a_1\) 最小， \(a_2\) 次大，以此类推。因此，只需要通过一次排序，我们便能轻松求出修改前最大的小费收益。
2、修改
接下来考虑每次的修改。首先，对于 \(L_i\) 的变化，我们直接加减即可。重点考虑 \(a_i\) 的变化。不妨如此假设：令 \(a_i\) 原先的排名为 \(l\), 而其修改后的排名为 \(r (l \le r)\), 可以看到，只有区间 \((l,r)\) 内部的数受到了影响，他们的系数全部减小 \(1\), 即对于该次修改，我们要减掉 \(\sum a_i (i \in (l,r))\) 。当 \(l \ge r\) 的时候同理，反过来即可。
3、具体操作
考虑到我们需要提取一定区间内部的所有数，使用 \(FHQ-Treap\) 可以很好的解决这个问题。在传统写法的基础上，记 \(w\) 为每个节点的子树大小之和，方便快速查询。 (想法来自线段树)
细节处理请见代码注释。
4、后记
- 不开 long long 见祖宗！
- 每次修改后的数据应该保留，手摸样例可以发现。
上代码（常数略大，大家可自行优化一下。）
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
#define ll long long
#define int long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n, Q;
struct people{
int L, T;
int id;
} a[N];
bool cmp1(people a, people b){
return a.T < b.T;
}
bool cmp2(people a, people b){
return a.id < b.id;
}
ll ans = 0;
/*经典 FHQ-Treap 写法，不过多解释。*/
int root = 0;
struct node{
int siz, val, ch[2];
int pri, w; // w 为总和， val 为当前点的值
} t[N];
#define lson ch[0]
#define rson ch[1]
int tot = 0;
inline int build(int x){
t[++tot].siz = 1;
t[tot].val = x;
t[tot].pri = rand();
t[tot].lson = t[tot].rson = 0;
t[tot].w = x;
return tot;
}
inline void pushup(int now){
t[0].siz = t[0].w = t[0].val = 0;
t[now].siz = t[t[now].lson].siz + t[t[now].rson].siz + 1;
t[now].w = t[t[now].lson].w + t[t[now].rson].w + t[now].val;
return ;
}
void split(int now, int key, int& x, int& y){ // 分裂
if(!now){
x = y = 0;
return ;
}
if(t[now].val <= key){
x = now;
split(t[now].rson, key, t[now].rson, y);
}
else {
y = now;
split(t[now].lson, key, x, t[now].lson);
}
pushup(now);
return ;
}
int merge(int x, int y){
if(!x || !y) return x + y;
if(t[x].pri > t[y].pri){
t[x].rson = merge(t[x].rson, y);
pushup(x);
return x;
}
else{
t[y].lson = merge(x, t[y].lson);
pushup(y);
return y;
}
return 0;
}
void insert(int key){
int x, y;
split(root, key - 1, x, y);
root = merge(merge(x, build(key)), y);
return ;
}
void del(int key){
int x, y, z;
split(root, key, x, z);
split(x, key - 1, x, y);
if(y) y = merge(t[y].lson, t[y].rson);
root = merge(merge(x, y), z);
return ;
}
int get_ans(int ori, int key){ // 处理每次修改后 T 的变化
if(ori == key) return 0;
int x, y, z, sum = 0;
split(root, ori, x, y); /*对于大小相同的重复节点的处理：直接把当前点认作排名最后的一个点。因为他们的先后顺序不影响答案.*/
sum += (n - t[x].siz + 1) * ori;
root = merge(x, y);
del(ori);
// 消除原有影响
insert(key);
if(key > ori){ // 注意分类讨论，提取区间内的所有数，建议画图讨论
split(root, ori, x, z);
split(z, key, y, z);
sum -= t[y].w - key;
root = merge(merge(x, y), z);
}
else {
split(root, ori, x, z);
split(x, key, x, y);
sum += t[y].w;
root = merge(merge(x, y), z);
}
split(root, key, x, y); // 不要忘了这个数自己
sum -= (n - t[x].siz + 1) * key;
root = merge(x, y);
return sum;
}
signed main(){
read(n); read(Q);
for(int i = 1; i <= n; i++){
read(a[i].L), read(a[i].T);
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp1);
for(int i = 1; i <= n; i++){
ans += a[i].L;
ans -= (n - i + 1) * a[i].T;
}
cout << ans << endl;
for(int i = 1; i <= n; i++)
insert(a[i].T);
sort(a + 1, a + n + 1, cmp2);
while(Q--){
int opt, L, T;
read(opt), read(L), read(T);
ans -= a[opt].L;
ans += L;
a[opt].L = L;
ans += get_ans(a[opt].T, T);
a[opt].T = T;
printf("%lld\n", ans);
}
return 0;
}