题解：AT_abc461_e [ABC461E] E-liter

YHW12345 · 2026-06-07 22:00:35 · 题解

思路

因为是覆盖操作，所以每个格子的颜色只与该行该列最后一次涂的颜色有关，因此我们可以设最后一次涂黑时间恰好等于 i 的行有 r_i 行，最后一次涂白时间恰好等于 i 的列有 c_i 列，这 r_i 行中每个格子为黑格的条件为：该格所在列最后一次涂白时间在 i 之前，也就是时间在 [0,i-1] 中。而对于第 j 次操作 Q_j，黑格的总量即为 \sum\limits_{i=0}^{Q_j}(r_i*\sum\limits_{k=0}^{i-1}c_k)。那么我们就可以维护两棵线段树，一棵维护行的最后一次涂黑时间，一棵维护列的最后一次涂白时间。对于每次操作 Q_i：

• 如为操作一，设该行原来的最后涂黑时间是 t，那么该行贡献了 \sum\limits_{j=0}^{t-1}c_j 个黑格，需减去；这次涂黑后将贡献 \sum\limits_{j=0}^{Q_i-1}c_j 个黑格，需加上。
• 如为操作二，设该列原来的最后涂白时间是 t，那么所有涂黑时间在 (t,Q_i] 的行在这一列会从黑变白，所以答案会减去 \sum\limits_{j=t+1}^{Q_i}r_j。

而最后涂黑涂白时间用两个原生数组就能实现。

submission

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define elif else if
using namespace std;
const int maxn=3e5+5;
int a[maxn],b[maxn],n,q;
struct node{
    int l,r,sum,lazy;
}t1[maxn<<2],t2[maxn<<2];
void build(int p,int l,int r){
    t1[p].l=t2[p].l=l,t1[p].r=t2[p].r=r;
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t1[p].sum=t1[p<<1].sum+t1[p<<1|1].sum;
    t2[p].sum=t2[p<<1].sum+t2[p<<1|1].sum;
}
void add1(int p,int x,int k){
    if(t1[p].l==t1[p].r){
        t1[p].sum+=k;
        return;
    }
    int mid=t1[p].l+t1[p].r>>1;
    if(x<=mid)add1(p<<1,x,k);
    else add1(p<<1|1,x,k);
    t1[p].sum=t1[p<<1].sum+t1[p<<1|1].sum;
}
void add2(int p,int x,int k){
    if(t2[p].l==t2[p].r){
        t2[p].sum+=k;
        return;
    }
    int mid=t2[p].l+t2[p].r>>1;
    if(x<=mid)add2(p<<1,x,k);
    else add2(p<<1|1,x,k);
    t2[p].sum=t2[p<<1].sum+t2[p<<1|1].sum;
}
int query1(int p,int l,int r){
    if(l<=t1[p].l&&t1[p].r<=r)return t1[p].sum;
    int mid=t1[p].l+t1[p].r>>1,res=0;
    if(l<=mid)res+=query1(p<<1,l,r);
    if(r>mid)res+=query1(p<<1|1,l,r);
    return res;
}
int query2(int p,int l,int r){
    if(l<=t2[p].l&&t2[p].r<=r)return t2[p].sum;
    int mid=t2[p].l+t2[p].r>>1,res=0;
    if(l<=mid)res+=query2(p<<1,l,r);
    if(r>mid)res+=query2(p<<1|1,l,r);
    return res;
}
void solve(){
    cin>>n>>q;
    build(1,0,q);
    add1(1,0,n),add2(1,0,n);
    int ans=0;
    for(int i=1,op,x;i<=q;i++){
        cin>>op>>x;
        if(op==1){
            int cnt=a[x];
            if(cnt>0)ans-=query2(1,0,cnt-1);
            add1(1,cnt,-1);
            a[x]=i;
            add1(1,i,1);
            ans+=query2(1,0,i-1);
            cout<<ans<<"\n";
        }else{
            int cnt=b[x];
            ans-=query1(1,cnt+1,i);
            add2(1,cnt,-1);
            b[x]=i;
            add2(1,i,1);
            cout<<ans<<"\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int Case=1;
//  cin>>Case;
    while(Case--)solve();
}