UVALive 4730 Kingdom线段树区间修改+并查集

题意:

有T组测试数据,每组数据的N表示有N个城市,接下来的N行里每行给出每个城市的坐标<=1000000)
然后有M<200000)个操作,操作有两类:
(1)”road A B”,表示将城市A和城市B通过一条道路连接,如果A和B原来属于不同的城市群,经过这个操作,A和B就在一个城市群里了,保证每条道路不会和其他道路相交(除了端点A和B)。
(2)”line C”,表示查询当穿过y=C的直线,有多少个城市群、这几个城市群一共有多少个城市。(注意:C是一个小数位为0.5的小数)

解析:

考录到联通块,所以可以想到用并查集,并查集的根节点保存每个城市群的的最大的y值和最小的y值,以及这个城市群内有多少个点。

每次合并两个集合的时候,先把原先城市群里的东西从线段树里去掉,更新好这个城市群之后,再放下去。

注意:y的范围比较大,又有小数,所以我把y坐标乘2,我把数组开到了200万,结果超时了,后来听了帆神学长的建议,考虑到C是一个小数位为0.5的小数,于是我把所有的左边界前移一位,询问C的时候把C+0.5,这样就避免了小数带来的麻烦,数组只要开到100万就可以过了。

e

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls, L, M 
#define rson rs, M+1, R
using namespace std;
const int MAXY = (int)1e6 + 5;
const int MAXN = (int)1e5 + 5;

struct Node {
    int state, city;
    int adds, addc; //lazy
    Node() { state = city = adds = addc = 0;}
} node[MAXY * 3];

int n, q;

void build(int o, int L, int R) {
    node[o] = Node();
    if(L == R) return ;
    int M = (L + R)/2;
    build(lson);
    build(rson);
}

void pushDown(int o) {
    if(node[o].addc) {
        node[ls].addc += node[o].addc;
        node[rs].addc += node[o].addc;
        node[ls].city += node[o].addc;
        node[rs].city += node[o].addc;
        node[o].addc = 0;
    }
    if(node[o].adds) {
        node[ls].adds += node[o].adds;
        node[rs].adds += node[o].adds;
        node[ls].state += node[o].adds;
        node[rs].state += node[o].adds;
        node[o].adds = 0;
    }
}

Node query(int o, int L, int R, int pos) {
    if(L == R) return node[o];
    pushDown(o);
    int M = (L + R)/2;
    if(pos <= M) return query(lson, pos);
    else return query(rson, pos);
}

void modify(int o, int L, int R, int ql, int qr, int val, char type) {
    if(ql <= L && R <= qr) {
        if(type == 'c') {
            node[o].city += val;
            node[o].addc += val;
        }else {
            node[o].state += val;
            node[o].adds += val;
        }
        return ;
    }
    pushDown(o);
    int M = (L + R)/2;
    if(ql <= M) modify(lson, ql, qr, val, type);
    if(qr > M) modify(rson, ql, qr, val, type);
}

int fa[MAXN];
int city[MAXN], state[MAXN], low[MAXN], high[MAXN];

void init() {
    int x, y;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        fa[i] = i;
        city[i] = state[i] = 1;
        low[i] = high[i] = y;
    }
}

int find(int u) {
    return (fa[u] == u) ? fa[u] : fa[u] = find(fa[u]);
}

void Union(int u, int v) {
    int a = find(u), b = find(v);
    if(a == b) return ;
    if(low[a] < high[a]) {
        modify(1, 0, MAXY, low[a]+1, high[a], -city[a], 'c');
        modify(1, 0, MAXY, low[a]+1, high[a], -1, 's');
    }
    if(low[b] < high[b]) {
        modify(1, 0, MAXY, low[b]+1, high[b], -city[b], 'c');
        modify(1, 0, MAXY, low[b]+1, high[b], -1, 's');
    }
    if(a > b) swap(a, b);
    fa[b] = a;
    low[a] = min(low[a], low[b]);
    high[a] = max(high[a], high[b]);
    city[a] += city[b];
    state[a] = 1;
    modify(1, 0, MAXY, low[a]+1, high[a], city[a], 'c');
    modify(1, 0, MAXY, low[a]+1, high[a], state[a], 's');
}

char oper[10];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);

        init();
        build(1, 0, MAXY);

        scanf("%d", &q);
        int u, v;
        double pos;
        while(q--) {
            scanf("%s", oper);
            if(oper[0] == 'r') {
                scanf("%d%d", &u, &v);
                Union(u, v);
            }else {
                scanf("%lf", &pos);
                Node ret = query(1, 0, MAXY, (int)(pos + 1));
                printf("%d %d\n", ret.state, ret.city);
            }
        }
    }
    return 0;
}
更多相关文章
  • 在<通过扩展让ASP.NET Web API支持W3C的CORS规范>中我们通过自定义的HttpMessageHandler为ASP.NET Web API赋予了跨域资源共享的能力,具体来讲,这个自定义的CorsMessageHandler的自由主要体现在如下两个方面:其一,为简单跨域请 ...
  • if (/(iPhone|iPad|iPod)/ig.test(navigator.userAgent)){ var str1 = ''; var str2 = ' 您的浏览器暂时无法播放此视频.';document.getElementById("FPlayer1395756683760 ...
  • 易网科技讯 8月7日消息,华为与中国电信集团公司在2015年中国电信云数据中心发展高峰论坛期间,正式签署云计算及大数据战略合作协议.中国电信副总经理高同庆.中国电信云公司副总经理黄礼莲,华为运营商BG总裁邹志磊.华为中国电信系统部部长曹既斌等出席战略合作签约,华为IT产品线副总裁郑殿海进行了题为&q ...
  • 首先使用sina进行登入,在个人简介那里写入恶意代码,如图:   保存,未弹窗...   退出,然后重新使用sina登入,弹框了,..     本来以为就这样完了,[email protected],发现它没有token的,所以还可以做其他邪恶的事..       首先给其他的用户发带有诱惑信息的私信 ...
  • 文/陈敏国内电信运营商终于迈出了与互联网公司联手进军移动互联网领域的实质性一步.8月19日,中国电信与易网公司共同宣布合资成立浙江翼信科技有限公司(以下简称"翼信公司"),并发布新一代移动即时通讯社交产品"易信".当天,易信1.0版本正式登陆各大手机应用商店供 ...
  •     据国外媒体报道,最近一段时间,IT管理者一直在不断地迅速学习,服务器虚拟化.桌面VDI.Exchange.SharePoint,微软不断地在企业中注入新鲜的元素.在这么多新产品的围攻之下,管理者很难空出时间去学习Windows 7的相关小技巧.     下面,就为大家总结了Windows 7 ...
一周排行
  • >> 读古龙的岁月(二) 目录(展开<读古龙的岁月>系列文章)   P.S. 本来呢,是想给亲爱的老婆写一封英文情书的.但是写着写着就没得灵感啦.早晨去军俱一趟,骑车在路上突然很想写写古龙.于 ...
  • 读完<编程之美>后,我觉得这并不是简简单单的一本有关于编程的书,本书强调的不仅仅是程序或者考题本身,而是思维.这就和小学时看到数学奥林匹克竞赛的题一样,重要的不是套路或者定式,而在于独立思考时被自己激活的 ...
  • 学习多态的时候,遇到了这样一个问题,一开始,我认为答案会是"seven dwarft","DisneyMovie",“seven dwarfts”,“Miki Mouse” 随 ...
  • 关键字:model属性,序列化,反射 正文         model是数据库的映射,在.net web开发中,作为程序的最底层.web开发的一切都是基于数据库的,分了层之后,就基于model了. 为什么要将mode ...
  •  表操作的重要内容:   表操作重要内容:# 查看表                                 # 添加数据                                 # 删除数据     ...
  • import java.util.ArrayList; import android.app.Activity; import android.content.Context; import android.os.B ...
  • 现在已经使用GET_DESCRIPTOR请求取到了包含一个配置里所有相关描述符内容的一堆数据,这些数据是raw的,即原始的,所有数据不管是配置描述符.接口描述符还是端点描述符都挤在一起,所以得想办法将它们给分开.,于 ...
  • 当初觉得DX中设备丢失很讨厌,差点就投奔OpenGL了. 不过现在发现其实也没那么麻烦啦,写点东西,给不清楚 设备丢失怎么处理的同学参考下. 在创建时使用D3DPOOL_MANAGED标志的资源可以不需要重新载入,但 ...
  • 前言:搜了半天,各种推荐,什么十大工具啦.优秀工具集合啦之类的咸淡文章,就是没有一个讲怎么弄的.配合官网的article自己研究了半天总算配置好了.顺便吐槽下官网关于sass/less设置这块说的模糊不清的.写个教程 ...
  • #include <stdio.h> int main() { puts("转载请注明出处[vmurder]谢谢"); puts("网址:blog.csdn.net/vmur ...