记录编号	618818	评测结果	AAAAAAAAAA
题目名称	彩色卡牌	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	9.850 s
提交时间	2026-09-12 16:23:46	内存使用	78.12 MiB

#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
    char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
    inline char gc() {
        if (iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
        return iS == iT ? EOF : *iS++;
    }
    inline void flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
    inline void pc(char c) { if (oS == oT) flush(); *oS++ = c; }
    struct F { ~F() { flush(); } } f;
    inline int read() {
        int x = 0; char c = gc();
        while (c < '0' || c > '9') c = gc();
        while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = gc();
        return x;
    }
    inline void write(int x) {
        if (x == 0) { pc('0'); pc('\n'); return; }
        char s[12]; int n = 0;
        while (x) s[n++] = x % 10 + '0', x /= 10;
        while (n) pc(s[--n]);
        pc('\n');
    }
}
using FastIO::read;
using FastIO::write;

const int N = 5e5 + 10;
const int CN = 250010;

int r, c, q, id, rt, n, cnt, tot;
int f[N], rk[N], dfn[N], de[N], sz[N], col[N], val[N];
int st[N][21];
int fx[] = {1, 0}, fy[] = {0, 1};
struct edge { int u, v, w; } e[N];
inline bool cmp(const edge &a, const edge &b) { return a.w < b.w; }

int head[N], nxt[N], to[N], ecnt;
inline void addedge(int u, int v) {
    to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt;
}

set<int> stc[CN];

int bc[N];
inline void badd(int x, int y) {
    for (; x <= id; x += x & -x) bc[x] += y;
}
inline int bask(int x) {
    int y = 0;
    for (; x > 0; x -= x & -x) y += bc[x];
    return y;
}

int uf[N];
inline int found(int x) {
    while (uf[x] != x) x = uf[x] = uf[uf[x]];
    return x;
}

int stk[N], idxs[N];
void dfs_iter(int root) {
    int top = 0;
    stk[++top] = root;
    st[root][0] = 0;
    for (int i = 1; i <= 20; i++) st[root][i] = 0;
    de[root] = 1, dfn[root] = ++cnt, rk[cnt] = root, sz[root] = 1;
    idxs[top] = head[root];
    while (top) {
        int x = stk[top];
        int &i = idxs[top];
        if (i) {
            int y = to[i];
            i = nxt[i];
            stk[++top] = y;
            de[y] = de[x] + 1;
            st[y][0] = x;
            for (int j = 1; j <= 20; j++) st[y][j] = st[st[y][j - 1]][j - 1];
            dfn[y] = ++cnt, rk[cnt] = y, sz[y] = 1;
            idxs[top] = head[y];
        } else {
            top--;
            if (top) sz[stk[top]] += sz[x];
        }
    }
}

inline int LCA(int a, int b) {
    if (de[a] < de[b]) swap(a, b);
    for (int i = 20; i >= 0; i--)
        if (de[st[a][i]] >= de[b]) a = st[a][i];
    if (a == b) return a;
    for (int i = 20; i >= 0; i--)
        if (st[a][i] != st[b][i]) a = st[a][i], b = st[b][i];
    return st[a][0];
}

inline void ins(int x) {
    badd(dfn[x], 1);
    int pre = 0, nxt = 0, z;
    auto &S = stc[col[x]];
    auto it = S.upper_bound(dfn[x]);
    if (it != S.end()) {
        nxt = rk[*it];
        z = LCA(x, nxt);
        badd(dfn[z], -1);
    }
    if (it != S.begin()) {
        --it; pre = rk[*it];
        z = LCA(x, pre);
        badd(dfn[z], -1);
    }
    if (nxt && pre) {
        z = LCA(nxt, pre);
        badd(dfn[z], 1);
    }
    S.insert(dfn[x]);
}

inline void del(int x) {
    badd(dfn[x], -1);
    int pre = 0, nxt = 0, z;
    auto &S = stc[col[x]];
    S.erase(dfn[x]);
    auto it = S.upper_bound(dfn[x]);
    if (it != S.end()) {
        nxt = rk[*it];
        z = LCA(x, nxt);
        badd(dfn[z], 1);
    }
    if (it != S.begin()) {
        --it; pre = rk[*it];
        z = LCA(x, pre);
        badd(dfn[z], 1);
    }
    if (nxt && pre) {
        z = LCA(nxt, pre);
        badd(dfn[z], -1);
    }
}

inline int query(int p, int v) {
    if (val[p] > v) return 0;
    for (int i = 20; i >= 0; i--)
        if (val[st[p][i]] <= v) p = st[p][i];
    return bask(dfn[p] + sz[p] - 1) - bask(dfn[p] - 1);
}

inline int ID(int x, int y) { return (x - 1) * c + y; }

int main() {
    r = read(), c = read(), q = read();
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            val[ID(i, j)] = read();
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            col[ID(i, j)] = read();
    n = r * c;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            for (int k = 0; k < 2; k++) {
                int x = i + fx[k], y = j + fy[k];
                if (x < 1 || x > r || y < 1 || y > c) continue;
                e[++tot] = {ID(i, j), ID(x, y), max(val[ID(i, j)], val[ID(x, y)])};
            }
    sort(e + 1, e + 1 + tot, cmp);
    id = n;
    for (int i = 1; i <= n; i++) uf[i] = i;
    for (int i = 1; i <= tot; i++) {
        int u = found(e[i].u), v = found(e[i].v);
        if (u == v) continue;
        ++id;
        uf[u] = id, uf[v] = id, uf[id] = id;
        addedge(id, u), addedge(id, v);
        val[id] = e[i].w;
    }
    rt = id, val[0] = 1e9 + 1;
    dfs_iter(rt);
    for (int i = 1; i <= n; i++) ins(i);
    while (q--) {
        int o = read(), x = read(), y = read(), cc = read();
        int u = ID(x, y);
        if (o == 1) {
            del(u), col[u] = cc, ins(u);
        } else {
            write(query(u, cc));
        }
    }
    return 0;
}