题目概述

有 $n$ 个任务，第 $i$ 个任务需要 $T_i$ 的时间完成，加分为 $L_i−s_i$ ，其中 $s_i$ 表示完成该任务的时间。有 $q$ 组修改，会变动 $L_i$ 和 $T_i$ ，问未修改时的最优解和每次修改之后的最优解。

解题报告

把 $s_i$ 用 $T_i$ 表示，假设完成顺序为 $\{ID_n\}$ ，那么答案就是 $\sum L_i-\sum\sum_{i=1}^{n}T_{ID_i}$ 。

$\sum L_i$ 是固定的，我们需要安排一个顺序使得后面的式子最小，最优解显然是 $T_i$ 从小到大。

多组数据用树状数组维护就行了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=200000,maxa=100001;

int n,te,a[maxn+5],b[maxn+5];LL ans,A[maxa+5],B[maxa+5];

inline void Add(LL *c,int x,int tem) {for (int i=x;i<=maxa;i+=i&-i) c[i]+=tem;}
inline LL Sum(LL *c,int x) {LL sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
inline void Insert(int x){
    ans-=Sum(B,maxa-x)*x;ans-=Sum(A,x)+x;
    Add(B,maxa-x,1);Add(A,x+1,x);
}
inline void Delete(int x){
    Add(B,maxa-x,-1);Add(A,x+1,-x);
    ans+=Sum(B,maxa-x)*x;ans+=Sum(A,x)+x;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int i=(scanf("%d%d",&n,&te),1);i<=n;i++)
        scanf("%d%d",&b[i],&a[i]),ans+=b[i],Insert(a[i]);
    printf("%lld\n",ans);
    for (int t=1;t<=te;t++){
        int x,A,B;scanf("%d%d%d",&x,&B,&A);ans-=b[x];ans+=(b[x]=B);
        Delete(a[x]);Insert(a[x]=A);printf("%lld\n",ans);
    }
    return 0;
}