Ô chết tra (A Thanh)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 3e3 + 5;
int m, n, q;
int k, a[N][N];
int b[N], pos[N], last[N];
vector<int> adj[N];

void Read()
{
    cin >> m >> n >> q >> k;
    for (int i = 1; i <= q; ++i)
    {
        int u, v;
        cin >> u >> v;
        ++a[u][v];
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[j][i] += a[j - 1][i];
}

void Solve()
{
    ll ans(0);
    for (int i = 1; i <= m; ++i)
    {
        vector<int> s;
        s.push_back(0);
        int p(0);
        b[n + 1] = 11;
        ll cur(0);
        for (int j = 1; j <= n; ++j)
        {
            b[j] = a[m][j] - a[i - 1][j];
            if (b[j] != 0)
            {
                s.push_back(j);
                pos[j] = s.size() - 1;
                cur += 1ll * (s[pos[j]] - s[pos[j] - 1]) * (s[pos[j]] - s[pos[j] - 1] - 1) / 2;
                ++p;
            }
        }
        cur += 1ll * (n + 1 - s.back()) * (n + 1 - s.back() - 1) / 2;
        s.push_back(n + 1);
        for (int j = 1, t = 1, sum(0); j <= p; ++j)
        {
            sum -= b[s[j - 1]];
            t = max(t, j);
            while (t <= p && sum + b[s[t]] < k)
            {
                sum += b[s[t]];
                ++t;
            }
            last[s[j]] = s[t];
            cur += 1ll * (s[j] - s[j - 1]) * (s[t] - s[j]);
        }
        //cout << i << ":\n";
        int t = m;
        do
        {
            //cerr << t << "\n";
            ans += cur;
            for (auto j : adj[t])
            {
                int h = pos[j], sum(0), x;
                --b[j];
                while (h >= 1 && sum + b[s[h]] < k)
                {
                    sum += b[s[h]];
                    --h;
                }
                if (h != pos[j])
                    ++h;
                for (x = h, sum = 0; h <= p; ++h)
                {
                    sum -= b[s[h - 1]];
                    x = max(x, h);
                    while (x <= p && sum + b[s[x]] < k)
                    {
                        sum += b[s[x]];
                        ++x;
                    }
                    if (s[x] == last[s[h]])
                        break;
                    cur += 1ll * (s[h] - s[h - 1]) * (s[x] - s[h]) - 1ll * (s[h] - s[h - 1]) * (last[s[h]] - s[h]);
                    last[s[h]] = s[x];
                }
            }
            --t;
            //cout << ans << '\n';
        } while (t >= i);
    }
    cout << (1ll * m * n * (m + 1) * (n + 1) / 4 - ans);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}