D
一个 \(n\times m\) 的网格图，一开始所有格子颜色都是 \(0\)。有 \(k\) 次染色操作，每次把第 \(l\sim r\) 行或第 \(l\sim r\) 列中的格子全都染成颜色 \(c\)。在所有染色操作完成后，设 $c_{i, j} 为格子 \((i, j)\) 的颜色，求 \(\sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m ([i < n \land c_{i, j} = c_{i + 1, j}] + [j < m \land c_{i, j} = c_{i, j + 1}])\) 以及 \(\sum\limits_{i = 1} ^ {n - 1} \sum\limits_{j = 1} ^ m ([j < m \land c_{i, j} = c_{i + 1, j + 1}] + [j > 1 \land c_{i, j} = c_{i + 1, j - 1}])\)。
\(1\le n, m, k\le 10^5\)
对于每一行求出其最晚染色时间 \(xt_i\) 以及染的颜色 \(x_i\)，同理求出 \(yt_i\) 和 \(y_i\)，那么格子 \((i, j)\) 的颜色只可能出自 \(x_i, y_j\)。
考虑第一个答案，行和列分别做一次。考虑每一行的答案，我们把该行格子分为 A（\(xt_i \ge yt_j\) 的格子）类和 B（\(xt_i > yt_j\)）类，我们需要统计 AA 的数量，AB 和 BB 的贡献。
按时间顺序依次加入，加入一列时更新一下 AB 和 BB 的贡献，可以使用桶，并实时更新 AA 的数量。
考虑第二个答案，我们分为 AA , BB , AB 三种贡献。
对于 AA，枚举列 \(j\)，由于两个格子 \((i, j), (i + 1, j + 1)\) 都不能被列染色，所以 \(xt_i \ge yt_j, \ xt_{i + 1} \ge yt_{j + 1}\)，可以二维数点。
对于 BB，枚举列 \(j\)，若 \(y_j = y_{j + 1}\) 则可能有贡献，对 \(xt_i < yt_j, \ xt_{i + 1} < yt_{j + 1}\) 做二维数点。
对于 AB，需要匹配对应的颜色，容易想到对每种颜色分别做一遍，同样是二维数点。
时间复杂度 \(\mathcal O((n + m) \log k)\)。
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
template <class T>
void rd(T &x) {
char ch;
while(!isdigit(ch = getchar())) ;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
}
void write(const ll x, const char str[] = "") {
if(x > 9) write(x / 10);
putchar(x % 10 + '0'), printf("%s", str);
}
const ll maxn = 1e5 + 10, inf = 1e18, mod = 1e9 + 7;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
ll n, m, k, tp, x[maxn], xti[maxn], y[maxn], yti[maxn], ans;
vector <ll> t_x[maxn], t_y[maxn];
namespace Get_Time {
vector <pir> vec_x[maxn], vec_y[maxn];
ll vis[maxn];
void solve() {
rd(n), rd(m), rd(k), rd(tp);
for(ll i = 1; i <= k; i++) {
ll op, l, r, c; rd(op), rd(l), rd(r), rd(c);
if(op == 0) vec_x[l].pb(mkp(i, c)), vec_x[r + 1].pb(mkp(-i, c));
else vec_y[l].pb(mkp(i, c)), vec_y[r + 1].pb(mkp(-i, c));
} priority_queue <pir> q;
for(ll i = 1; i <= n; i++) {
for(pir t: vec_x[i])
if(t.fi > 0) q.push(t), vis[t.fi] = 1;
else vis[-t.fi] = 0;
while(!q.empty() && vis[q.top().fi] == 0) q.pop();
if(!q.empty()) x[i] = q.top().se, xti[i] = k - q.top().fi;
else xti[i] = k;
t_x[xti[i]].pb(i);
} while(!q.empty()) q.pop();
for(ll i = 1; i <= m; i++) {
for(pir t: vec_y[i])
if(t.fi > 0) q.push(t), vis[t.fi] = 1;
else vis[-t.fi] = 0;
while(!q.empty() && vis[q.top().fi] == 0) q.pop();
if(!q.empty()) y[i] = q.top().se, yti[i] = k - q.top().fi;
else yti[i] = k;
t_y[yti[i]].pb(i);
}
}
}
namespace FFB {
ll cnt[maxn], kk, sp, bin[maxn];
vector <ll> vec_x[maxn], vec_y[maxn];
void solve() {
memset(cnt, 0, sizeof cnt), kk = 0, sp = m - 1;
memset(bin, 0, sizeof bin);
for(ll i = 0; i <= k; i++) {
for(ll j: t_y[i]) {
bin[j] = 1;
if(j < m && !bin[j + 1]) ++cnt[y[j]], --sp;
if(j > 1 && !bin[j - 1]) ++cnt[y[j]], --sp;
if(j < m && bin[j + 1]) --cnt[y[j + 1]];
if(j > 1 && bin[j - 1]) --cnt[y[j - 1]];
kk += (bin[j + 1] && y[j + 1] == y[j])
+ (bin[j - 1] && y[j - 1] == y[j]);
}
for(ll j: t_x[i])
ans += cnt[x[j]] + kk + sp;
}
}
}
ll tree[maxn], used[maxn];
void add(ll x, ll v) {
for(; x <= k + 1; x += x & -x) tree[x] += v;
}
ll ask(ll x) {
ll v = 0;
for(; x; x -= x & -x) v += tree[x];
return v;
}
namespace AA_BB {
vector <pir> vec, _vec;
void solve() {
vec.clear(), _vec.clear();
for(ll i = 1; i <= m; i++) {
if(i < m && y[i] == y[i + 1]) vec.pb(mkp(yti[i], yti[i + 1]));
if(i > 1 && y[i] == y[i - 1]) vec.pb(mkp(yti[i], yti[i - 1]));
}
for(ll i = 1; i < n; i++)
_vec.pb(mkp(xti[i], xti[i + 1]));
sort(vec.begin(), vec.end()), sort(_vec.begin(), _vec.end());
for(ll i = 0, j = 0; i < _vec.size(); i++) {
while(j < vec.size() && vec[j].fi <= _vec[i].fi)
add(vec[j++].se + 1, 1);
ans += ask(_vec[i].se + 1);
}
vec.clear(), _vec.clear();
for(ll i = 1; i <= m; i++) {
if(i < m) vec.pb(mkp(yti[i] - 1, yti[i + 1] - 1));
if(i > 1) vec.pb(mkp(yti[i] - 1, yti[i - 1] - 1));
} memset(tree, 0, sizeof tree);
for(ll i = 1; i < n; i++)
if(x[i] == x[i + 1]) _vec.pb(mkp(xti[i], xti[i + 1]));
sort(vec.begin(), vec.end(), greater <pir> ());
sort(_vec.begin(), _vec.end(), greater <pir> ());
for(ll i = 0, j = 0; i < _vec.size(); i++) {
while(j < vec.size() && _vec[i].fi <= vec[j].fi)
add(k + 1 - vec[j++].se, 1);
ans += ask(k + 1 - _vec[i].se);
}
}
}
namespace AB {
vector <pir> vec[maxn], _vec[maxn];
void solve() {
memset(tree, 0, sizeof tree);
for(ll i = 0; i <= k; i++) vec[i].clear(), _vec[i].clear();
for(ll i = 1; i <= m; i++) {
if(i < m) vec[y[i]].pb(mkp(yti[i], yti[i + 1] - 1));
if(i > 1) vec[y[i]].pb(mkp(yti[i], yti[i - 1] - 1));
}
for(ll i = 1; i <= n; i++) {
if(i < n) _vec[x[i]].pb(mkp(xti[i + 1], xti[i]));
if(i > 1) _vec[x[i]].pb(mkp(xti[i - 1], xti[i]));
}
for(ll c = 0; c <= k; c++) {
if(vec[c].empty() || _vec[c].empty()) continue;
sort(vec[c].begin(), vec[c].end());
sort(_vec[c].begin(), _vec[c].end());
for(ll i = 0, j = 0; i < _vec[c].size(); i++) {
ll lim = _vec[c][i].fi;
while(j < vec[c].size() && vec[c][j].fi <= lim)
add(k + 1 - vec[c][j++].se, 1);
ans += ask(k + 1 - _vec[c][i].se);
if(i + 1 == _vec[c].size())
while(j--) add(k + 1 - vec[c][j].se, -1);
}
}
}
}
int main() {
freopen("painting.in", "r", stdin);
freopen("painting.out", "wb", stdout);
Get_Time::solve();
FFB::solve();
if(tp) AB::solve(), AA_BB::solve();
swap(n, m), swap(x, y), swap(xti, yti);
swap(t_x, t_y), FFB::solve();
write(ans, "\n");
return 0;
}