1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=3005;
int r,c,n,k,x[N],y[N],sum[N],a[N],pos[N],cnt,L[N],R[N];
vector<int> vec[N];
ll ans,s,val[N];
inline void del(int x)
{
sum[a[x]]--;
int le=x,ri;
s-=val[x]; val[x]=0;
fo(i,1,k) if(L[le]) le=L[le],s-=val[le],val[le]=0;
int t=R[x];
if(!sum[a[x]])
{
L[R[x]]=L[x],R[L[x]]=R[x];
s-=val[t],val[t]=0; t=R[t];
if(le==x) le=R[le];
}
if(le==cnt+1) return;
ri=le;
int now=sum[a[le]];
fo(i,1,k) if(now<k) ri=R[ri],now+=sum[a[ri]];
if(ri==cnt+1) return;
for(;le!=t&&ri!=cnt+1;)
{
s+=(val[le]=1ll*(c-a[ri]+1)*(a[le]-a[L[le]]));
now-=sum[a[le]]; le=R[le];
for(;now<k&&ri<=cnt;ri=R[ri],now+=sum[a[ri]]);
if(ri==cnt+1) break;
}
}
int main()
{
r=read(); c=read(); n=read(); k=read();
fo(i,1,n) x[i]=read(),y[i]=read(),vec[x[i]].pb(y[i]);
fo(l,1,r)
{
cnt=0; s=0;
fo(i,1,n) if(x[i]>=l) sum[y[i]]++;
fo(i,1,c) if(sum[i]) a[++cnt]=i,pos[i]=cnt;
fo(i,1,cnt) L[i]=i-1,R[i]=i+1;
R[0]=1; R[cnt+1]=cnt+1;
int ri=0,le=1,now=0;
fo(i,1,k) if(now<k) ri=R[ri],now+=sum[a[ri]];
if(now>=k&&ri!=cnt+1)
{
fo(i,1,cnt)
{
s+=(val[le]=1ll*(c-a[ri]+1)*(a[le]-a[L[le]]));
now-=sum[a[le]]; le=R[le];
for(;now<k&&ri<=cnt;ri=R[ri],now+=sum[a[ri]]);
if(ri==cnt+1) break;
}
fd(d,r,l)
{
ans+=s;
for(auto v:vec[d]) del(pos[v]);
}
}
fo(i,0,cnt+1) L[i]=R[i]=a[i]=val[i]=0;
fo(i,1,c) sum[i]=pos[i]=0; cnt=0;
}
printf("%lld",ans);
return 0;
}
|