JZOJ 6404. B / BZOJ 5103.「POI2018」Różnorodność

神仙扫描线题？遵从 JZOJ 题解中的说法写了个 bitset 后来发现可以用线段树。
（JZOJ 上的只能 bitset，空间卡得紧）

维护一个宽度为的扫描线，并维护其上的个正方形。
每次只会新增一行减少一行的贡献。

由于边长是确定的，所以新增 / 减少某个位置的贡献一定是第二维的某个区间。
对于每种颜色用 bitset 维护其出现的列，则只要能求得该位置的前驱后继即可得到该区间。
于是差分 + 前缀和即可。

（话说 JZOJ 上卡得有点紧，于是特判掉了搬题人的一个 subtask

代码：

#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 3e3;
const int A = 1e5;
int n,m,k,a[N + 5][N + 5],mx;
int sum[N + 5][N + 5];
int las[A + 5],g[N + 5][N + 5],c[N + 5];
int f[N + 5];
int cur,cnt[A + 5];
bitset<N + 5> vis0[A + 5],vis1[A + 5];
int ans0;
long long ans1;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= m;++j)
            scanf("%d",a[i] + j),mx = max(mx,a[i][j]);
    if(mx <= 2)
    {
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= m;++j)
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (a[i][j] == 2);
        for(register int i = 1,cur;i + k - 1 <= n;++i)
            for(register int j = 1;j + k - 1 <= m;++j)
                cur = (bool)(sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] + sum[i - 1][j - 1]) + (bool)(k * k - (sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] - sum[i + k - 1][j - 1] + sum[i - 1][j - 1])),
                ans0 = max(ans0,cur),ans1 += cur;
        printf("%d %lld\n",ans0,ans1);
        return 0;
    }
    for(register int i = 1;i <= A;++i)
        las[i] = n + 1;
    for(register int j = 1;j <= m;++j)
    {
        for(register int i = n;i;--i)
            g[i][j] = las[a[i][j]] <= min(i + k,n),las[a[i][j]] = i;
        for(register int i = 1;i <= n;++i)
            las[a[i][j]] = n + 1;
    }
    for(register int i = 1;i <= A;++i)
        vis0[i][m + 1] = vis1[i][m + 1] = 1;
    for(register int i = 1;i <= k;++i)
        for(register int j = 1;j <= m;++j)
            vis0[a[i][j]][m - j + 1] = 1,vis1[a[i][j]][j] = 1;
    for(register int i = 1;i <= k;++i)
        for(register int j = 1;j <= k;++j)
            cur += !cnt[a[i][j]]++;
    f[1] = cur,ans0 = max(ans0,cur),ans1 += cur;
    for(register int i = 2;i + k - 1 <= m;++i)
    {
        for(register int j = 1;j <= k;++j)
            cur -= !--cnt[a[j][i - 1]],cur += !cnt[a[j][i + k - 1]]++;
        f[i] = cur,ans0 = max(ans0,cur),ans1 += cur;
    }
    for(register int i = 2;i + k - 1 <= n;++i)
    {
        memset(c,0,sizeof c);
        for(register int j = 1,prev,succ;j <= m;++j)
            if(!vis1[a[i + k - 1][j]][j])
            {
                prev = m - vis0[a[i + k - 1][j]]._Find_next(m - j + 1) + 1;
                succ = vis1[a[i + k - 1][j]]._Find_next(j);
                vis0[a[i + k - 1][j]][m - j + 1] = 1,vis1[a[i + k - 1][j]][j] = 1;
                if(prev + k <= succ)
                    ++c[max(max(prev + 1,j - k + 1),1)],--c[min(min(succ - k + 1,j + 1),m + 1)];
            }
        for(register int j = 1;j + k - 1 <= m;++j)
            c[j] += c[j - 1],f[j] += c[j];
        memset(c,0,sizeof c);
        for(register int j = 1,prev,succ;j <= m;++j)
            if(!g[i - 1][j])
            {
                prev = m - vis0[a[i - 1][j]]._Find_next(m - j + 1) + 1;
                succ = vis1[a[i - 1][j]]._Find_next(j);
                vis0[a[i - 1][j]][m - j + 1] = 0,vis1[a[i - 1][j]][j] = 0;
                if(prev + k <= succ)
                    --c[max(max(prev + 1,j - k + 1),1)],++c[min(min(succ - k + 1,j + 1),m + 1)];
            }
        for(register int j = 1;j + k - 1 <= m;++j)
            c[j] += c[j - 1],f[j] += c[j],ans0 = max(ans0,f[j]),ans1 += f[j];
    }
    printf("%d %lld\n",ans0,ans1);
}

『My guiding star.』

JZOJ 6404 B / BZOJ 5103.「POI2018」Różnorodność