【离线并查集】问题集合
- 有 N 个数,初始均为 0。有 Q 个操作,第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问,所有操作结束后,每个数的值
并查集维护每个点右边最近的未修改的点,把操作全部读入以后倒序处理,因为是倒着处理所以每个点只能被修改一次,直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩,当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点
#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
if(f[x]==x) return x;
else return f[x]=ff(f[x]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n+2;i++) f[i]=i;
for(int i=q;i>0;i--)
{
scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
}
for(int i=1;i<=q;i++)
{
int l=qm[i][1],r=qm[i][2],v=qm[i][0];
while(l<=r)
{
l=ff(l);
if(l<=r)
{
a[l]=v;
f[l]=l+1;
l+=1;
}
else
{
break;
}
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
发表评论