UVALive 4730 Kingdom

Kingdom

https://ac.nowcoder.com/acm/problem/121647

Kingdom

Kingdom - UVALive 4730 - Virtual Judge (vjudge.net)

题目描述

平面上有n个城市，初始时城市之间没有任何双向道路相连，你的任务是依次执行以下指令

road A B:在城市A和城市B之间链接一条双向道路，保证着条道路不和其他道路在非端点处相交

line C:询问一条y = C的水平线和多少个州以及这些州一共包含多少城市，每一组联通的城市形成一个州

样例

3
10
1 7
5 7
8 6
3 5
5 5
2 3
10 3
7 2
4 1
11 1
11
road 0 1
road 3 5
line 6.5
road 4 2
road 3 8
road 4 7
road 6 9
road 4 1
road 2 7
line 4.5
line 6.5
1
100 100
1
line 100.5
2
10 10
20 20
2
road 0 1
line 15.5

算法1

(线段树维护线段 + 并查集 + 区间覆盖次数)

维护联通块和联通块的城市个数我们可以用并查集维护
然后我们根据y轴建立线段树
同时我们还需要维护每一个联通块在y轴上的范围，将每一个联通块抽象成线段
某一个区间被线段覆盖多少次就意味着用一条水平线穿过该区间后能于多少个州相交
所以我们维护两个信息 $s1$ (被线段覆盖次数)， $s2$ 城市个数

时间复杂度 $O(nlogn)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100010,M = 1000010;
struct Node
{
    int l,r;
    int s1,s2;//s1州的数量,s2城市的数量
    int add1,add2;
}tr[M * 4];
int flag[M * 4];
int ks;
int p[N],sz[N];
PII range[N];
PII citys[N];
char str[10];
int n,m;

inline int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

inline void Flash(int u)
{
    if(flag[u] == ks) return;
    flag[u] = ks;
    tr[u].s1 = tr[u].s2 = tr[u].add1 = tr[u].add2 = 0;
}

inline int calc(int a,int b)
{
    return (b - a) + 1;
}

inline int calc(const PII &line)
{
    return calc(line.x,line.y);
}

inline void pushup(Node &rt,Node &left,Node &right)
{
    rt.s1 = left.s1 + right.s1;
    rt.s2 = left.s2 + right.s2;
}

inline void pushup(int u)
{
    Flash(lc);
    Flash(rc);
    pushup(tr[u],tr[lc],tr[rc]);
}

inline void pushdown(int u)
{
    if(tr[u].add1 != 0)
    {
        Flash(lc);
        Flash(rc);
        tr[lc].add1 += tr[u].add1;
        tr[rc].add1 += tr[u].add1;
        tr[lc].s1 += calc(tr[lc].l,tr[lc].r) * tr[u].add1;
        tr[rc].s1 += calc(tr[rc].l,tr[rc].r) * tr[u].add1;
        tr[u].add1 = 0;
    }
    if(tr[u].add2 != 0)
    {
        Flash(lc);
        Flash(rc);
        tr[lc].add2 += tr[u].add2;
        tr[rc].add2 += tr[u].add2;
        tr[lc].s2 += tr[u].add2;
        tr[rc].s2 += tr[u].add2;
        tr[u].add2 = 0;
    }
}

inline void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = Node({l,r,0,0,0,0});
        return;
    }
    int mid = (l + r )>> 1;
    tr[u] = Node({l,r,0,0,0,0});
    build(lc,l,mid);
    build(rc,mid + 1,r);
    pushup(u);
}

inline void modify(int u,int l,int r,int k1,int k2)
{
    Flash(u);
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add1 += k1;
        tr[u].add2 += k2;
        tr[u].s1 += calc(tr[u].l,tr[u].r) * k1;
        tr[u].s2 += k2;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if(l <= mid) modify(lc,l,r,k1,k2);
    if(r > mid) modify(rc,l,r,k1,k2);
    pushup(u);
}

inline Node query(int u,int x)
{
    Flash(u);
    if(tr[u].l == x && tr[u].r == x) return tr[u];
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if(x <= mid) return query(lc,x);
    else return query(rc,x);
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d",&citys[i].x,&citys[i].y);
        p[i] = i,sz[i] = 1;
        range[i] = make_pair(citys[i].y,citys[i].y - 1);
    }
    scanf("%d",&m);
    while(m -- )
    {
        scanf("%s",str);
        if(str[0] == 'r')
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a ++,b ++;
            int pa = find(a),pb = find(b);
            if(pa != pb)
            {
                if(calc(range[pa]) != 0) modify(1,range[pa].x,range[pa].y,-1,-sz[pa]);
                if(calc(range[pb]) != 0) modify(1,range[pb].x,range[pb].y,-1,-sz[pb]);
                p[pb] = pa;
                sz[pa] += sz[pb];
                range[pa].x = min(range[pa].x,range[pb].x);
                range[pa].y = max(range[pa].y,range[pb].y);
                if(calc(range[pa]) != 0) modify(1,range[pa].x,range[pa].y,1,sz[pa]);
                // cout << "------" << range[pa].x << " "<< range[pa].y << " "<< sz[pa] << endl;
            }
        }else
        {
            double c;
            scanf("%lf",&c);
            int t = (int)c;
            // cout <<"--"<< t << endl;
            Node tmp = query(1,t);
            printf("%d %d\n",tmp.s1,tmp.s2);
        }
    }
    ks ++;
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;
    build(1,0,M - 1);//表示线段从0开始编号
    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}