【并查集+离散化】POJ2528

2528:Mayor’s posters

本题很多都是用的线段树,但线段树客观来说代码长,容易写错,所以并查集其实更好

先把操作离线,由于只有靠后的操作才会对区间产生影响,所以说每个点最后一次覆盖的才是最后显示的颜色

把区间抽象成节点。每个区间有一个l和r,倒着操作。每次操作就合并所有操作的区间。

如果操作的左右端点的父亲不同,那么本次操作就是合法的,说明至少有一个段是没有被合并的。还可以被涂一次颜色。

否则不合法次数 ans + 1。

最后答案就是 n – ans 。相当于问有多少次合法合并(询问)。很明显可以转化为并查集的询问条件是否成立。由于操作只有1e4次,所以不同的点不会超过2e4个点。可以把区间进行离散化。

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 10233;
pii q[100233 + 233];
int f[100233 + 233];
int ff(int x)
{
    if(f[x] == x) return x;
    return f[x] = ff(f[x]);
}
void uni(int u, int v)
{
    f[ff(u)] = ff(v);
}
int main()
{
    int tc,n;
    scanf("%d",&tc);
    for(int j = 1; j <= tc; j++)
    
Read the rest