【题解】[COCI2011-2012#2] RASPORED

· · 题解

评分虚高。

首先获得的小费只和考煎饼的顺序有关。我们令烤煎饼的顺序为排列 p，那么不难直接写出答案。

Ans=\sum\limits_{i=1}^n L_{p_i}-\sum\limits_{j=1}^{i}T_{p_j}

直接拆开算。

Ans=\sum\limits_{i=1}^n L_i-\sum\limits_{i=1}^{n}(n-i+1)T_{p_i}

前者可以 \mathcal{O}(1) 维护。

对于后者，如果单次查询，我们直接对 T 从小到达排序。

我们还需要支持单点修改，也就是要在线维护每个数比它小的有多少个数，和比它小的数之和。

值域很小，直接开两个树状数组维护即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
#define int long long
using namespace std;
int n,m,u[N],t[N],o[N],c[N][2],sum;
inline void add(int x,int y,int op){for(;x<=N-5;x+=x&-x)c[x][op]+=y;}
inline int ask(int x,int op){int sum=0;for(;x;x-=x&-x)sum+=c[x][op];return sum;}
signed main(){
    scanf("%lld%lld",&n,&m);
    rep(i,1,n)scanf("%lld%lld",&u[i],&t[i]),o[i]=t[i],sum+=u[i],add(t[i],1,0),add(t[i],t[i],1);
    sort(o+1,o+n+1);rep(i,1,n)sum-=o[i]*(n-i+1);
    printf("%lld\n",sum);
    while(m--){
        int x;scanf("%lld",&x);
        sum -= u[x];add(t[x],-1,0);add(t[x],-t[x],1);
        int cur = ask(t[x],0),now = ask(t[x],1);
        sum += t[x] * (n - cur) + now;
        scanf("%lld%lld",&u[x],&t[x]);
        sum += u[x];
        cur = ask(t[x],0),now=ask(t[x],1);
        sum -= t[x] * (n - cur) + now;
        add(t[x],1,0);add(t[x],t[x],1);
        printf("%lld\n",sum);
    }
    return 0;
}