酒馆的聒噪怪

前言

二十分钟rush了个树套树，十分钟把锅调出来，结果空间炸了，这不写篇题解纪念一下？

这 T4 不A也罢。

题目

聒噪怪又泛滥成灾了。

经过多代杂交，聒噪怪们变异出了不同的种类，产生了生殖隔离。没有人会喜欢聒噪怪，除了聒噪怪们本身。现在酒馆里出现了 (n imes m) 个聒噪怪，第 (i) 行 (j) 列的聒噪怪的种类为(a_{i,j}) ，由于种类并不是很多，所以鲍勃决定让废土守望者来解决这些聒噪怪。

为了更为方便地解决这些聒噪怪，废土守望者提出了一个问题：有多少个正方形包含了恰好 (k) 种聒噪怪。鲍勃正忙于给某8位选手加油阴阳怪气，所以他没空回答问题，作为酒馆的常客，你有义务帮助鲍勃解决这个问题。

(3s,512MB.)

(1le n,mle 1500;1le kle n imes m;1le a_{i,j}le 100.)

讲解

我的做法是线段树套线段树+( t bitset)，外面是类似尺取的做法，当然你也可以认为是 ( t two-pointer)，时间复杂度 (O(frac{100}{64}n^2log^2_2n))。

题解的做法是二维 ( t st) 表+二分，据它说是 (O(n^2log_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[4091];
	
	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[4091];
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;
}