P9917 网格题解

听取MLE声一片 · 2023-12-09 20:29:18 · 题解

注：本题解中提到的行列均指指定视图下的行列。

首先我们规定一下周长的贡献。我们正着看这个网格，如果一个格子是红的，而且这个格子往下一个是白色，那么就有一个周长贡献。再从侧面统计，加起来再乘二就是答案。

做法 1：我不会数据结构！

直接按照前面的思想模拟，时间复杂度 O(n^3)，期望得分 15。

做法 2：我会暴力维护时间戳！

发现修改一次最多影响三行或三列，维护每个地方修改时间戳，暴力维护，时间复杂度 O(n^2)，期望得分 30。

做法 3：动态二维数点

数一条边两侧分别是红色和白色的数量，分颜色记录修改时间，使用动态二维数点，时间复杂度 O(n\log^2 n)，期望得分 70。

这档部分分也是留给正解但常数太大的解法的。

做法 4：树状数组

不难看出正着看和侧着看是本质相同的，我们开一个结构体来减少代码难度。

很自然的想到把操作给拍到时间轴上，但是红白分别维护一个时间轴比较复杂，考虑把这两个时间轴合并。

考虑维护每次修改的时间戳，规定初始所有时间戳都为 0，红色的为正数，白色的为负数，其绝对值为操作时间。显然对于当前时刻的任意一整行或整列都是由最后一次修改此行或此列贡献的，所以我们只需要维护最新的即可。

修改一次只会影响相邻两行或两列的贡献。考虑记录上一次的答案，每次修改先减去原来的贡献，再修改，最后加上修改后的贡献即可。

因为上面对周长贡献的规定，所以我们得出，只有相邻两行和一列是最基础的贡献。我们简要画出这个图：

规定只有上面的点是红的，下面的点是白的才会产生贡献。

• 如果 b < 0,-b>|a|，那么 |a|< c < |b|

• 如果 a\geq 0,a>|b|，那么 -a< c < -|b|

这里把 c 都提出来了，方便维护。

不难看出 a,b 是绑定的，必须放在一起维护。

修改行的时候，需要查询 a,b 的贡献。将所有的 c 塞入权值树状数组，即单点修改，区间求和。然后查询 a,b 的范围有多少个 c 满足即可。这里应用树状数组 1。

修改列的时候，需要查询 c 的贡献。将所有的 a,b 范围塞入权值树状数组，即区间加减，单点查询。然后查询 c 对应多少个范围。这里应用树状数组 2。

一定注意查询后要修改。

注意修改列的时候要特判底层。

关于实现问题，推荐进行封装。

这里之所以用值域树状数组，是因为常数小而且好写，如果写平衡树查排名或线段树可能会被卡常。

综上，时间复杂度 O(n\log n)，期望得分 100。

注意开 long long。

顺带一提，如果令 q 是操作次数，n 是网格边长，则时间复杂度为 O(q\log q)，与 n 无关。所以理论上如果把 n,q 切割 n 的范围可以随便开大，记录某行列的时间用 umap 即可，反正这也不是瓶颈。

AC 代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=2e6+10;
const int M=1e6+5;
struct BIT{
    int n=N-1,a[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void add(int x,int y){
        for(;x<=n;x+=lowbit(x))
            a[x]+=y; 
    }
    inline void update(int x,int y,int z){
        if(x>y)
            return;
        x+=M;
        y+=M;
        add(x,z);
        add(y+1,-z);
    }
    inline int sum(int x){
        x+=M;
        int res=0;
        for(;x;x-=lowbit(x))
            res+=a[x];
        return res;
    }
};
struct Tree{
    int n=N-1,a[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void add(int x,int y){
        x+=M;
        for(;x<=n;x+=lowbit(x))
            a[x]+=y; 
    }
    inline int sum(int x){
        int res=0;
        for(;x;x-=lowbit(x))
            res+=a[x];
        return res;
    }
    inline int query(int x,int y){
        if(x>y)
            return 0;
        x+=M;
        y+=M;
        return sum(y)-sum(x-1);
    }
};
struct point{
    int n,a[M],b[M],vis[N];
    long long ans;
    BIT t;
    Tree T;
    void build(int m){
        n=m;
        ans=n;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        T.add(0,n);
        for(int i=1;i<=n;i++)
            vis[i]=1;
    }
    inline void calc(int x,int f){
        if(b[x]>=0&&b[x+1]<0){
            ans+=f*T.query(-min(b[x],-b[x+1]),min(b[x],-b[x+1]));
            t.update(-min(b[x],-b[x+1]),min(b[x],-b[x+1]),f);
        }
        if(b[x+1]<0&&-b[x+1]>abs(b[x])){
            ans+=f*T.query(abs(b[x])+1,abs(b[x+1])-1);
            t.update(abs(b[x])+1,abs(b[x+1])-1,f);
        }
        if(b[x]>=0&&b[x]>abs(b[x+1])){
            ans+=f*T.query(-b[x]+1,-abs(b[x+1])-1);
            t.update(-b[x]+1,-abs(b[x+1])-1,f);
        }
    }
    inline void line(int x,int y){
        calc(x,-1);
        calc(x-1,-1);
        b[x]=y;
        calc(x,1);
        calc(x-1,1);
    }
    inline void row(int x,int y){
        T.add(a[x],-1);
        ans-=t.sum(a[x]);
        a[x]=y;
        T.add(a[x],1);
        if(vis[x]==1)
            ans--;
        if(y<0)
            vis[x]=0;
        else vis[x]=1;
        ans+=vis[x];
    } 
}a,b;
int main()
{
    int n=read();
    a.build(n);
    b.build(n);
    for(int k=1;k<=n;k++){
        int w=read(),y=read(),x=read(),p=0;
        if(w==1)
            p=k;
        else p=-k;
        if(y==1){
            a.line(x,p);
            b.row(x,p);
        }
        else{
            a.row(x,p);
            b.line(x,p);
        }
        printf("%lld",(a.ans+b.ans)*2);
        putchar('\n');
    }
    return 0;
}