前言
二十分钟rush了个树套树，十分钟把锅调出来，结果空间炸了，这不写篇题解纪念一下？
这 T4 不A也罢。
题目
聒噪怪又泛滥成灾了。
经过多代杂交，聒噪怪们变异出了不同的种类，产生了生殖隔离。没有人会喜欢聒噪怪，除了聒噪怪们本身。现在酒馆里出现了 \(n\times m\) 个聒噪怪，第 \(i\) 行 \(j\) 列的聒噪怪的种类为\(a_{i,j}\) ，由于种类并不是很多，所以鲍勃决定让废土守望者来解决这些聒噪怪。
为了更为方便地解决这些聒噪怪，废土守望者提出了一个问题：有多少个正方形包含了恰好 \(k\) 种聒噪怪。鲍勃正忙于给某8位选手加油阴阳怪气，所以他没空回答问题，作为酒馆的常客，你有义务帮助鲍勃解决这个问题。
\(1\le n,m\le 1500;1\le k\le n\times m;1\le a_{i,j}\le 100.\)
讲解
我的做法是线段树套线段树+\(\tt bitset\)，外面是类似尺取的做法，当然你也可以认为是 \(\tt two-pointer\)，时间复杂度 \(O(\frac{100}{64}n^2\log^2_2n)\)。
题解的做法是二维 \(\tt st\) 表+二分，据它说是 \(O(n^2\log_2n)\)。
代码
卡过空间的代码
//12252024832524
#include <bitset>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 1501;
int n,m,k;
int a[MAXN][MAXN];
LL ans;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
#define lc (x<<1)
#define rc (x<<1|1)
struct SegmentTree1
{
bitset<100> t[4090];
void up(int x){t[x] = t[lc] | t[rc];}
void Build(int x,int l,int r,int ql,int qr)
{
if(l == r)
{
for(int i = ql;i <= qr;++ i) t[x][a[l][i]] = 1;
return;
}
int mid = (l+r) >>1;
Build(lc,l,mid,ql,qr); Build(rc,mid+1,r,ql,qr);
up(x);
}
bitset<100> Query(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) return t[x];
int mid = (l+r) >> 1;
if(ql <= mid)
{
if(mid+1 <= qr) return Query(lc,l,mid,ql,qr) | Query(rc,mid+1,r,ql,qr);
else return Query(lc,l,mid,ql,qr);
}
else return Query(rc,mid+1,r,ql,qr);
}
}st[4090];
void Build(int x,int l,int r)
{
st[x].Build(1,1,n,l,r);
if(l == r) return;
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
}
int hang;
bitset<100> Query(int x,int l,int r,int ql,int qr)
{
if(ql <= l && r <= qr) return st[x].Query(1,1,n,hang,hang+qr-ql);
int mid = (l+r) >> 1;
if(ql <= mid)
{
if(mid+1 <= qr) return Query(lc,l,mid,ql,qr) | Query(rc,mid+1,r,ql,qr);
else return Query(lc,l,mid,ql,qr);
}
else return Query(rc,mid+1,r,ql,qr);
}
int main()
{
// freopen("matrix.in","r",stdin);
// freopen("matrix.out","w",stdout);
n = Read(); m = Read(); k = Read();
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= m;++ j)
a[i][j] = Read()-1;
Build(1,1,m);
hang = 1;
for(int i = 1;i <= n;++ i)
{
hang = i;
int l = 0,r = 0,sx = n-i+1;
for(int j = 1;j <= m;++ j)
{
while((r < j || Query(1,1,m,j,r+1).count() <= k) && r-j+1 < sx && r < m) ++ r;
while((l < j-1 || Query(1,1,m,j,l+1).count() < k) && l-j+1 < sx && l < m) ++ l;
ans += r-l;
}
}
Put(ans);
return 0;
}