Description：

一个 $n\times m$ 的棋盘，每次可以把第 $L_i$ 到 $R_i$ 行或列都染成颜色 $C_i$ ，询问有多少边相邻和角相邻的格子对颜色相同。

$1\leqslant n,m,k\leqslant 10^5$

Solution：

首先我们可以对行和列染色，用并查集优化这个染色的过程就可以在 $O(n\alpha(n))$ 的时间内求出每一行和列最后一次被染的颜色以及染的时间，那么这个格子的颜色就是行或列较靠后的染的颜色。

首先计算边相邻的格子，把所有的列染色操作和行染色操作按时间从大到小排序，考虑这一列和他左边的那一个格子构成的这一对格子：如果他上一列出现了并且和他颜色相同，那么就会多一个，注意这时可能会加多，即本来这一行和上一列颜色相同，本来就有这么一个点对存在，加上这一行并不会少点对，如果某一行和这一列上一列颜色一样，那么如果这一列和上一列颜色不一样，就会少一对点对，如果颜色一样，那么不变，正好可以把刚才多加的补回来， 如果他上一列没出现，那么就会少一对点对，但是如果某一行的颜色和他相同那就不少，于是双指针记一个 $cnt$ 表示每种颜色被补回来多少就行了。

然后我们再计算角相邻的格子，我们可以先写一个暴力，就像这样：

for(int i = 1;i < n;++i)

{

	for(int j = 1;j < m;++j)

	{

		if(timn[i] > timm[j] && timn[i + 1] > timm[j + 1] && coln[i] == coln[i + 1])++res;

		if(timn[i] > timm[j + 1] && timn[i + 1] > timm[j] && coln[i] == coln[i + 1])++res;

		if(timn[i] > timm[j] && timn[i + 1] < timm[j + 1] && coln[i] == colm[j + 1])++res;

		if(timn[i] > timm[j + 1] && timn[i + 1] < timm[j] && coln[i] == colm[j])++res;

		if(timn[i] < timm[j] && timn[i + 1] > timm[j + 1] && colm[j] == coln[i + 1])++res;

		if(timn[i] < timm[j + 1] && timn[i + 1] > timm[j] && colm[j + 1] == coln[i + 1])++res;

		if(timn[i] < timm[j] && timn[i + 1] < timm[j + 1] && colm[j] == colm[j + 1])++res;

		if(timn[i] < timm[j + 1] && timn[i + 1] < timm[j] && colm[j + 1] == colm[j])++res;

	}

}

然后我们发现这其实非常像一个二维偏序问题，但是后面有一个 $col$ 的限制就很不好办，但是我们可以分两类，一是 $col$ 的等式两边都是 $i$ 或者都是 $j$ ，那么显然我们可以先把另一个的全部插入到一棵主席树中，然后把符合条件的这一个在主席树上查询，其实就是前缀数点，如果两边既有 $i$ 又有 $j$ ，那么我们就分颜色来统计贡献，即每次把所有这个颜色的 $i$ 插入，查询这个颜色的所有 $j$ 的二维前缀和，这个可以用扫描线 $+$ 树状数组。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k,w;

#define MAXN 100010

typedef long long ll;

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int coln[MAXN],timn[MAXN],colm[MAXN],timm[MAXN];

struct option{int ty,l,r,c;}o[MAXN];

struct paint{int p,t,c;}cn[MAXN],cm[MAXN];

bool paint_cmp_tim(paint a,paint b){return a.t < b.t;}

int b[MAXN];

void getcol()

{

	for(int i = 1;i <= k;++i)b[i] = o[i].c;

	sort(b + 1,b + 1 + k);b[0] = unique(b + 1,b + 1 + k) - b - 1;

	for(int i = 1;i <= k;++i)o[i].c = lower_bound(b + 1,b + 1 + b[0],o[i].c) - b;

	for(int i = 1;i <= n;++i)f[i] = i;f[n + 1] = n + 1;

	for(int i = k;i >= 1;--i)if(o[i].ty == 0)

		for(int p = find(o[i].l);p <= o[i].r;p = find(p + 1))coln[p] = o[i].c,timn[p] = i,f[p] = p + 1;

	for(int i = 1;i <= m;++i)f[i] = i;f[m + 1] = m + 1;

	for(int i = k;i >= 1;--i)if(o[i].ty == 1)

		for(int p = find(o[i].l);p <= o[i].r;p = find(p + 1))colm[p] = o[i].c,timm[p] = i,f[p] = p + 1;

	for(int i = 1;i <= n;++i)cn[i] = (paint){i,timn[i],coln[i]};

	for(int i = 1;i <= m;++i)cm[i] = (paint){i,timm[i],colm[i]};

	sort(cn + 1,cn + 1 + n,paint_cmp_tim);sort(cm + 1,cm + 1 + m,paint_cmp_tim);

	return;

}

bool visn[MAXN],vism[MAXN];

int cntn[MAXN],cntm[MAXN];

ll calc1()

{

	ll res = 0;

	int mans = m - 1;

	for(int i = n,j = m;i >= 1;--i)

	{

		for(;j >= 1 && cm[j].t > cn[i].t;--j)

		{

			int p = cm[j].p;vism[p] = true;

			if(p != 1){if(vism[p - 1])mans += (colm[p - 1] == colm[p]),--cntm[colm[p - 1]];else --mans,++cntm[cm[j].c];}

			if(p != m){if(vism[p + 1])mans += (colm[p + 1] == colm[p]),--cntm[colm[p + 1]];else --mans,++cntm[cm[j].c];}

		}

		res += mans + cntm[cn[i].c];

	}

	int nans = n - 1;

	for(int i = m,j = n;i >= 1;--i)

	{

		for(;j >= 1 && cn[j].t > cm[i].t;--j)

		{

			int p = cn[j].p;visn[p] = true;

			if(p != 1){if(visn[p - 1])nans += (coln[p - 1] == coln[p]),--cntn[coln[p - 1]];else --nans,++cntn[cn[j].c];}

			if(p != n){if(visn[p + 1])nans += (coln[p + 1] == coln[p]),--cntn[coln[p + 1]];else --nans,++cntn[cn[j].c];}

		}

		res += nans + cntn[cm[i].c];

	}

	return res;

}

namespace CNT//二维数点

{

	int c[MAXN];

	int lowbit(int x){return x & (-x);}

	int stack[MAXN],top;

	void add(int p,int x){stack[++top] = p;for(int i = p;i <= k;i += lowbit(i))c[i] += x;return;}

	void erase(int p){for(int i = p;i <= k;i += lowbit(i))c[i] = 0;return;}

	int sum(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

	void reset(){while(top)erase(stack[top--]);return;}

	struct point{int x,y;bool operator < (const point &b)const{return x < b.x;}}p[MAXN];

	struct query{int x,y;bool operator < (const query &b)const{return x < b.x;}}q[MAXN];

	int pnum,qnum;

	void init(){reset();pnum = qnum = top = 0;return;}

	void addpoint(int x,int y){p[++pnum] = (point){x,y};return;}

	void addquery(int x,int y){q[++qnum] = (query){x,y};return;}

	ll calc()

	{

		ll res = 0;

		sort(p + 1,p + 1 + pnum);sort(q + 1,q + 1 + qnum);

		for(int i = 1,j = 1;i <= qnum;++i)

		{

			for(;j <= pnum && p[j].x <= q[i].x;++j)add(p[j].y,1);

			res += sum(q[i].y);

		}

		return res;

	}

}

vector<int> d[MAXN];

struct node

{

	int lc,rc;

	int sum;

}t[MAXN * 30];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void insert(int &rt,int p,int l,int r)

{

	int k = newnode();t[k] = t[rt];rt = k;

	++t[rt].sum;

	if(l == r)return;

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	int res = 0;

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

ll calc2()

{

	ll res = 0;

	build(root[0],1,k);

	for(int i = 1;i < m;++i)d[timm[i]].push_back(timm[i + 1]);

	vector<int>::iterator it;

	for(int i = 1;i <= k;++i)

	{

		root[i] = root[i - 1];

		for(it = d[i].begin();it != d[i].end();++it)insert(root[i],*it,1,k);

	}

	for(int i = 1;i < n;++i)if(coln[i] == coln[i + 1])res += query(root[timn[i]],1,timn[i + 1],1,k);

	for(int i = 1;i < n;++i)if(coln[i] == coln[i + 1])res += query(root[timn[i + 1]],1,timn[i],1,k);

	ptr = 0;

	for(int i = 1;i <= k;++i)d[i].clear();

	build(root[0],1,k);

	for(int i = 1;i < n;++i)d[timn[i]].push_back(timn[i + 1]);

	for(int i = 1;i <= k;++i)

	{

		root[i] = root[i - 1];

		for(it = d[i].begin();it != d[i].end();++it)insert(root[i],*it,1,k);

	}

	for(int i = 1;i < m;++i)if(colm[i] == colm[i + 1])res += query(root[timm[i]],1,timm[i + 1],1,k);

	for(int i = 1;i < m;++i)if(colm[i] == colm[i + 1])res += query(root[timm[i + 1]],1,timm[i],1,k);

	for(int i = 1;i <= k;++i)d[i].clear();

	for(int i = 1;i < n;++i)d[coln[i]].push_back(i);

	for(int i = 1;i < m;++i)d[colm[i + 1]].push_back(-i);

	for(int i = 1;i <= k;++i)

	{

		CNT::init();

		for(it = d[i].begin();it != d[i].end();++it)

		{

			if(*it > 0)CNT::addquery(timn[*it],k - timn[*it + 1] + 1);

			else CNT::addpoint(timm[-*it],k - timm[-*it + 1] + 1);

		}

		res += CNT::calc();

	}

	for(int i = 1;i <= k;++i)d[i].clear();

	for(int i = 1;i < n;++i)d[coln[i]].push_back(i);

	for(int i = 1;i < m;++i)d[colm[i]].push_back(-i);

	for(int i = 1;i <= k;++i)

	{

		CNT::init();

		for(it = d[i].begin();it != d[i].end();++it)

		{

			if(*it > 0)CNT::addquery(timn[*it],k - timn[*it + 1] + 1);

			else CNT::addpoint(timm[-*it + 1],k - timm[-*it] + 1);

		}

		res += CNT::calc();

	}

	for(int i = 1;i <= k;++i)d[i].clear();

	for(int i = 1;i < n;++i)d[coln[i + 1]].push_back(i);

	for(int i = 1;i < m;++i)d[colm[i]].push_back(-i);

	for(int i = 1;i <= k;++i)

	{

		CNT::init();

		for(it = d[i].begin();it != d[i].end();++it)

		{

			if(*it > 0)CNT::addpoint(timn[*it],k - timn[*it + 1] + 1);

			else CNT::addquery(timm[-*it],k - timm[-*it + 1] + 1);

		}

		res += CNT::calc();

	}

	for(int i = 1;i <= k;++i)d[i].clear();

	for(int i = 1;i < n;++i)d[coln[i + 1]].push_back(i);

	for(int i = 1;i < m;++i)d[colm[i + 1]].push_back(-i);

	for(int i = 1;i <= k;++i)

	{

		CNT::init();

		for(it = d[i].begin();it != d[i].end();++it)

		{

			if(*it > 0)CNT::addpoint(timn[*it],k - timn[*it + 1] + 1);

			else CNT::addquery(timm[-*it + 1],k - timm[-*it] + 1);

		}

		res += CNT::calc();

	}

	return res;

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&k,&w);

	o[1] = (option){0,1,n,0};o[2] = (option){1,1,m,0};k += 2;

	for(int i = 3;i <= k;++i)scanf("%d%d%d%d",&o[i].ty,&o[i].l,&o[i].r,&o[i].c);

	getcol();

	cout << calc1() + (w == 1 ? calc2() : 0) << endl;

	return 0;

}