ATCoder-[ABC179F] Simplified Reversi

ATCoder-[ABC179F] Simplified Reversi

周末的赛题，然而考场上因为 E 题的一点细节没处理好，只剩下 30 min 来写 F，想到了做法后索性就没写 Code 了。

考虑到两种操作的本质相同，仔细思考一下每次操作会给状态带来的影响（默认对行的操作）：

1. 行：当我们对第 $x$ 行进行操作后，那么意味着 $x$ 行在后续的操作中不会产生任何贡献；
2. 列：当我们对第 $x$ 行进行操作后，那么意味着我们后续对于列的操作都不会影响到第 $x+1$ 行至第 $n$ 行的任意位置（因为当我们更换黑子到 $x$ 行时必然会遇到白子而结束操作）。

那么考虑用一个序列表示当前从第 $1$ 行到第 $n$ 行中第一个白子所出现的列的位置，相应地，我们也使用另一个序列表示对于列的状态。

此时我们记录操作前第 $x$ 行中第一个白子所出现的位置为 $pos$，那么此次操作所带来的贡献即 $pos-2\tag{pos $\geq$ 2}$。（注意到第一个白子如果出现在第 $1$ 个时不会产生贡献）

操作带给行的影响则是将第 $x$ 行中第一个白子所出现的位置所更改为 $1$。

当此时所修改的行是所有对于行的修改中最靠前的，我们就更新从第 $1$ 列到第 $pos-1$ 列中所有的第一个白子出现的位置为 $x$（因为在此操作之前没有任何操作使得在此位置之前的所有位置出现白子）。

考虑使用线段树或者分块实现，树状数组好像也行（因为是前缀类型修改）。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
    T x=0,f=1;char c=getchar();
    while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
    return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1,MAXSQRT=5e2;
const lint INF=1e18+1e9;

int n,q,preLine,preRow;
lint Ans=0;

struct Chunking{
    int a[MAXN],to[MAXN],sl[MAXSQRT],sr[MAXSQRT],sq[MAXSQRT],sz;

    void Init(){
        sz=sqrt(n)+1;
        for(int i=1;i<=n;i++) to[i]=i/sz;
        for(int i=1;i<n;i++) a[i]=n-1;
        for(int i=0;i<=sz;i++) sl[i]=max(i*sz,1),sr[i]=min((i+1)*sz-1,n);
        memset(sq,0,sizeof(sq));
        return;
    }

    void SqrtAssign(int T,int k){
        for(int i=sl[T];i<=sr[T];i++) a[i]=k;
        return;
    }

    void Modify(int pos,int k){
        int T=to[pos];
        if(sq[T]) SqrtAssign(T,sq[T]),sq[T]=0;
        a[pos]=k;
        return;
    }

    void Assign(int ql,int qr,int k){
        int tl=to[ql],tr=to[qr];
        if(tl==tr){
            if(sq[tl]) SqrtAssign(tl,sq[tl]),sq[tl]=0;
            for(int i=ql;i<=qr;i++) a[i]=k;
        }
        else{
            if(sq[tl]) SqrtAssign(tl,sq[tl]),sq[tl]=0;
            if(sq[tr]) SqrtAssign(tr,sq[tr]),sq[tr]=0;
            for(int i=ql;i<=sr[tl];i++) a[i]=k;
            for(int i=sl[tr];i<=qr;i++) a[i]=k;
            if(tl+1<tr) for(int i=tl+1;i<tr;i++) sq[i]=k;
        }
        return;
    }

    int Query(int pos){
        int T=to[pos];
        if(sq[T]) SqrtAssign(T,sq[T]),sq[T]=0;
        return a[pos];
    }
}Line,Row;

int main(void){

    n=readint,q=readint,preLine=preRow=n,Ans=1ll*(n-2)*(n-2);
    Line.Init(),Row.Init();
    while(q--){
        int op=readint,x=readint;
        if(op==1){
            int pos=Line.Query(x);
            Ans-=pos,Line.Modify(x,0),++Ans;
            if(x<preLine) Row.Assign(1,pos,x-1),preLine=x;
        }
        else{
            int pos=Row.Query(x);
            Ans-=pos,Row.Modify(x,0),++Ans;
            if(x<preRow) Line.Assign(1,pos,x-1),preRow=x;
        }
    }
    printf("%lld\n",Ans);

    return 0;
}