FHC 2021 R2 C2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 2000006;
const int maxtreesize = 1 << 21;

pair2<int> tree[2 * maxtreesize];
char s[maxn];
vector<int> wh[maxn];
set<int> setik[maxn];
int kth[maxn];
int answer[maxn];
int n, m, k, nq;
int treesize;
int xq[maxn], yq[maxn];

inline int getans(int cur)
{
    return tree[cur].fi + tree[cur].se;
}

void add(int cur, int cl, int cr, int l, int r, int t)
{
    if (cl > r || cr < l) return;
    if (cl >= l && cr <= r)
    {
        tree[cur].se += t;
        return;
    }
    int cm = (cl + cr) / 2;
    add(cur * 2, cl, cm, l, r, t);
    add(cur * 2 + 1, cm + 1, cr, l, r, t);
    tree[cur].fi = min(getans(cur * 2), getans(cur * 2 + 1));
}

void add(int mxpos, int idx, int t)
{
    //cout << "add " << mxpos << ' ' << idx << ' ' << t << endl;
    if (mxpos >= k && idx < k) add(1, 0, treesize - 1, mxpos - k, mxpos - k, t);
    if (mxpos >= k && idx == k) add(1, 0, treesize - 1, mxpos - k, n - 1, t);
}

void solveoneway()
{
    treesize = 1;
    while (treesize < n) treesize *= 2;
    for (int i = 0; i < 2 * treesize; i++)
    {
        tree[i] = {0, 0};
    }
    for (int i = 1; i < n; i++) add(1, 0, treesize - 1, i, i, i);
    add(1, 0, treesize - 1, n, treesize - 1, m + 1);

    for (int i = 0; i < m; i++) setik[i].clear();
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < (int)wh[i].size(); j++)
        {
            add(wh[i][j], j, 1);
            setik[i].insert(wh[i][j]);
        }
        if ((int)wh[i].size() <= k) kth[i] = n;
        else kth[i] = wh[i][k];
    }

    for (int q = 0; q < nq; q++)
    {
        int i = yq[q];
        int x = xq[q];
        //cout << "solve q = " << q << endl;

        auto it = setik[i].lower_bound(x);
        if (it != setik[i].end() && *it == x)
        {
            if (x < kth[i])
            {
                add(x, k - 1, -1);
                if (kth[i] != n)
                {
                    add(kth[i], k, -1);
                    add(kth[i], k - 1, 1);
                    auto y = setik[i].upper_bound(kth[i]);
                    if (y != setik[i].end())
                    {
                        kth[i] = *y;
                        add(kth[i], k, 1);
                    } else kth[i] = n;
                }
            } else if (x == kth[i])
            {
                add(kth[i], k, -1);
                auto y = setik[i].upper_bound(kth[i]);
                if (y != setik[i].end())
                {
                    kth[i] = *y;
                    add(kth[i], k, 1);
                } else kth[i] = n;
            } else {}
            setik[i].erase(it);
        } else
        {
            if (x < kth[i])
            {
                if (kth[i] != n)
                {
                    if (it != setik[i].end() && *it == kth[i])
                    {
                        add(kth[i], k, -1);
                        kth[i] = x;
                        add(kth[i], k, 1);
                    } else
                    {
                        add(x, k - 1, 1);
                        add(kth[i], k, -1);
                        auto y = prev(setik[i].lower_bound(kth[i]));
                        kth[i] = *y;
                        add(kth[i], k - 1, -1);
                        add(kth[i], k, 1);
                    }
                } else
                {
                    if ((int)setik[i].size() == k)
                    {
                        add(x, k - 1, 1);
                        int y = x;
                        if (!setik[i].empty()) y = max(y, *setik[i].rbegin());
                        add(y, k - 1, -1);
                        add(y, k, 1);
                        kth[i] = y;
                    } else
                    {
                        add(x, k - 1, 1);
                    }
                }
            }
            setik[i].insert(x);
        }
        //cout << getans(1) << endl;
        answer[q] = min(answer[q], getans(1));
    }
}

void solve()
{
    scanf("%d%d%d%d", &n, &m, &k, &nq);
    k--;
    for (int i = 0; i < m; i++) wh[i].clear();
    for (int i = 0; i < n; i++)
    {
        scanf("%s", s);
        for (int j = 0; j < m; j++) if (s[j] == 'X') wh[j].pb(i);
    }
    for (int q = 0; q < nq; q++)
    {
        scanf("%d%d", &xq[q], &yq[q]);
        xq[q]--;
        yq[q]--;
    }

    for (int i = 0; i < nq; i++) answer[i] = m;
    for (int IT = 0; IT < 2; IT++)
    {
        solveoneway();
        k = n - k - 1;
        for (int i = 0; i < m; i++)
        {
            reverse(all(wh[i]));
            for (auto &t : wh[i]) t = n - t - 1;
        }
        for (int q = 0; q < nq; q++) xq[q] = n - xq[q] - 1;
    }
    ll res = 0;
    for (int i = 0; i < nq; i++) res += answer[i];
    printf("%lld\n", res);
}

int main()
{
    int NT = 0;
    scanf("%d", &NT);
    for (int T = 1; T <= NT; T++)
    {
        printf("Case #%d: ", T);

        solve();

        fprintf(stderr, "%d/%d cases done!\n", T, NT);
    }
    return 0;
}