Max Matrix

刷题 atcoder

今天是CSP2024的前一天晚上，按照大佬们的说法是写题解涨rp，那就来写点套路题练练手涨涨rp把。

$\max$ 在一些时候也跟绝对值什么的一样可以考虑拆掉，就像这道题。

现在只考虑修改 $a$ 的情况看看答案有什么变化。

那不不妨看看 $a_i$ 对原答案的贡献如何吧。

提取一下就能看出 $a_i$ 的贡献就是 $\sum_{j=1}^m \max(a_i,b_j)$。

我们用艾弗森括号 $[P]$ 来改写一下这个式子（$[P]$ 在 $P$ 为真时为 $1$ 反之为 $0$），就相当于分类讨论一下，于是得出 $a_i$ 的贡献是：

前半段的含义是 $a_i$ 乘上比 $a_i$ 小或正好相等的 $b$ 的数量，可以用权值树状数组维护，当然了你非要线段树也行。

后半段的含义也是明显的，就是比 $a_i$ 大的 $b_j$ 的总和。这一部分其实也是权值树状数组可以搞掉的，区别在于前面是每次在树状数组下标为 $b_j$ 的位置加上一，而后面那个式子每次加上 $b_j$。

于是我们对 $a,b$ 各自维护两个权值树状数组，在修改的时候考虑变化量即可。

加上离散化，复杂度 $O(q\log n+n\log n)$，然后就可以A了这题了。

也是祝所有人明天比赛好运吧，希望都能取得自己想要的成绩，也说不定这就是我竞赛生涯的最后一篇题解了呢。

#include<bits/stdc++.h>
#define int long long
#define lb(x) (x&-x)
using namespace std;
const int N=6e5+5;
#define gk(x) (lower_bound(L+1,L+cnt+1,x)-L)
int bit[4][N];
int cnt;
void add(int x,int k,int th){
    for(int i=x;i<=cnt;i+=lb(i)) bit[th][i]+=k; 
}
int query(int x,int th){
    int ret=0;
    for(int i=x;i;i-=lb(i)) ret+=bit[th][i];
    return ret;
}
int n,m,q;
int a[N],b[N];
int use[N];
int p[N],X[N],xx[N],opt[N];
int L[N];
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=q;i++){
        cin>>opt[i]>>p[i]>>X[i];
        L[++cnt]=X[i];
    }
    L[++cnt]=0;
    sort(L+1,L+cnt+1);
    cnt=unique(L+1,L+cnt+1)-(L+1);
    for(int i=1;i<=q;i++) xx[i]=lower_bound(L+1,L+cnt+1,X[i])-L;
    for(int i=1;i<=n;i++) add(gk(0),1,0);
    for(int i=1;i<=m;i++) add(gk(0),1,2);
    for(int i=1;i<=q;i++){
        if(opt[i]==1){
            int rp=gk(a[p[i]]);
            ans-=a[p[i]]*query(rp,2)+query(cnt,3)-query(rp,3);//cerr<<i<<"i1:"<<ans<<"\n";
            add(rp,-1,0);
            add(rp,-a[p[i]],1);
            a[p[i]]=X[i];
            add(gk(a[p[i]]),1,0);
            add(gk(a[p[i]]),a[p[i]],1);
            ans+=a[p[i]]*query(gk(a[p[i]]),2)+query(cnt,3)-query(gk(a[p[i]]),3);
        }else{
            ans-=b[p[i]]*query(gk(b[p[i]]),0)+query(cnt,1)-query(gk(b[p[i]]),1);
            add(gk(b[p[i]]),-1,2);
            add(gk(b[p[i]]),-b[p[i]],3);
            b[p[i]]=X[i];
            add(gk(b[p[i]]),1,2);
            add(gk(b[p[i]]),b[p[i]],3);
            ans+=b[p[i]]*query(gk(b[p[i]]),0)+query(cnt,1)-query(gk(b[p[i]]),1);
        }
        cout<<ans<<"\n";
    }
}
/*
add(a[i],1,0);
add(a[i],a[i],1);
add(b[i],1,2);
add(b[i],b[i],3);
*/