题意简述：
给定 \(n\) 个互不相交，可以重叠的矩阵，对某些点染色，这个点上的所有矩阵会被染上这个颜色，求最后每个矩阵会有多少种颜色。
解：
我们可以先把矩阵拆成上下两条水平线段，然后离线将染色与线段横坐标离散化，以纵坐标将矩阵将线段与染色一起处理。
维护一棵线段树，对于一个矩阵的下方线段加入，直接在线段树对应节点将其入栈，对于上方线段，直接在对应节点弹出栈顶即可，因为矩阵无相交，所以栈顶一定是需要弹出的线段。
对于染色操作，我们找到线段树对应的栈顶元素，用 set 记录一下。
由于若将大矩阵覆盖小矩阵看成大矩阵为小矩阵的父亲节点，那么不难发现这是棵森林，所以我们对于染色的节点，它们父亲也需要染这个颜色，这个就遍历一遍树用启发式合并即可。
时间复杂度：\(O(n\times \log_2^2(n))\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
const int N=8e4+5;
int n,m,cnt,ans[N],cnp,ru[N],len1[12*N],len2[12*N];
set<int>num[N];
vector<int>b[N];
struct node
{
int name,x,y,h,k,flag;
}a[3*N];
struct node2
{
int name,data;
bool flag;
}t[3*N];
int cmp(node2 fi,node2 se)
{
return fi.data<se.data;
}
int cmp2(node fi,node se)
{
if(fi.h==se.h)return fi.flag<se.flag;
return fi.h<se.h;
}
vector<int>f[12*N];
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
void update(int x,int l,int r,int nl,int nr,int id,bool flag)
{
if(l>=nl&&r<=nr)
{
if(flag==0)
{
if(len1[x]==len2[x])f[x].push_back(id),len1[x]++,len2[x]++;
else f[x][len1[x]++]=id;
}
else len1[x]--;
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid,nl,nr,id,flag);
if(mid<nr)update(rs(x),mid+1,r,nl,nr,id,flag);
}
int search(int x,int l,int r,int nl)
{
int ans=0;
if(len1[x]>0)ans=f[x][len1[x]-1];
if(l==r)return ans;
int mid=(l+r)>>1;
if(mid>=nl)ans=max(ans,search(ls(x),l,mid,nl));
else ans=max(ans,search(rs(x),mid+1,r,nl));
return ans;
}
void dfs(int x)
{
int len=b[x].size();
for(int i=0;i<len;i++)
{
dfs(b[x][i]);
if(num[b[x][i]].size()>num[x].size())swap(num[x],num[b[x][i]]);
for(set<int>::iterator j=num[b[x][i]].begin();j!=num[b[x][i]].end();j++)num[x].insert(*j);
}
ans[x]=num[x].size();
}
int main()
{
//freopen("plahteplahte.in","r",stdin);
//freopen("Plahte.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&a[i*2-1].x,&a[i*2-1].h,&a[i*2].y,&a[i*2].h);
a[i*2-1].name=a[i*2].name=i;
a[i*2-1].y=a[i*2].y;
a[i*2].x=a[i*2-1].x;
t[++cnp]={i,a[i*2-1].x,0};
t[++cnp]={i,a[i*2-1].y,1};
a[i*2-1].flag=0;
a[i*2].flag=2;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i+2*n].x,&a[i+2*n].h,&a[i+2*n].k);
t[++cnp]={i+2*n,a[i+2*n].x,0};
a[i+2*n].flag=1;
}
sort(t+1,t+1+cnp,cmp);
t[0].data=-1;
for(int i=1;i<=cnp;i++)
{
if(t[i].data!=t[i-1].data)cnt++;
if(t[i].flag==0)
{
if(t[i].name<=2*n)a[t[i].name*2-1].x=a[t[i].name*2].x=cnt;
else a[t[i].name].x=cnt;
}
else a[t[i].name*2-1].y=a[t[i].name*2].y=cnt;
}
sort(a+1,a+1+2*n+m,cmp2);
for(int i=1;i<=2*n+m;i++)
{
//cout<<a[i].name<<" "<<a[i].x<<" "<<a[i].y<<" "<<a[i].flag<<endl;
if(a[i].flag==0)
{
int x=search(1,1,cnt,a[i].x);
if(x)b[a[x].name].push_back(a[i].name),ru[a[i].name]++;
update(1,1,cnt,a[i].x,a[i].y,i,0);
}
else if(a[i].flag==1)
{
int x=search(1,1,cnt,a[i].x);
if(x)num[a[x].name].insert(a[i].k);
}
else update(1,1,cnt,a[i].x,a[i].y,i,1);
}
for(int i=1;i<=n;i++)if(!ru[i])dfs(i);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}