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 ...
一周排行
  • struts2 表单的多重递交(Annotation方式) 假设一个form表单有几个操作(update,delete,create etc.),可以通过method的方式递交到action.网上有很多资料,讲述了通 ...
  • Nginx高性能HTTP和反向代理服务器 局限:只支持HTTP和Mail两种 Nginx使用高效的网络I/O模型,针对不同的Linux 发布版      epoll(Linux 2.6内核)      kqueue( ...
  • 在局域网中部署Web服务器进行信息的发布,建立统一的办公和财务系统,这是很多企业采用的方案.但通常情况下单位不见得会购买大量安全设备或软件,那么如何加强企业内网的Web服务器的安全呢?其实Windows提供了一个足以 ...
  • 总结一下,下午半天进行的MP3播放器的开发:  首先,新建一个解决方案:命名MP3solution,设置FormBorderStyle为None,即上面的图标,最大化最小化按钮隐藏,但如图所示还有最大化关闭按钮,这时 ...
  • 由于逐渐面临高频数据的问题,所以计划正式启用hadoop分布式计算, 去年10月份研究过一段时间hadoop的部署情况,确定使用CDH版本的hadoop(最新5.4.0), 主要是考虑维度是减少运维难度以及快速部署上 ...
  • Discuz!第七年了 说起来,从我第一次建立一个个人主页(叫做"超人软件工作室",是个盗链别人网站软件的小网站 ^_^)到现在,也有9年的时间了.在1998年,互联网对于大多数人来说,还显得太陌 ...
  • <script language=javascript> // cookie其实是一个key=value就是一个cookie而不是 //获得coolie 的值 function cookie(name){ ...
  •  EnvMapping.h   /*-----------------------------------------------------------------------------This source f ...
  •   G 文化.科学.教育.体育     G0 文化理论       G02 文化哲学       G03 文化的民族性       G04 比较文化学       G05 文化与其他学科的关系       G07 文 ...
  • groovy的保留字: abstractasassertbooleanbreakbytecasecatchcharclassconstcontinuedefdefaultdodoubleelseenumextends ...