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登入,弹框了,..     本来以为就这样完了,后来在@magerx大牛的指导下,发现它没有token的,所以还可以做其他邪恶的事..       首先给其他的用户发带有诱惑信息的私信 ...
  • 文/陈敏国内电信运营商终于迈出了与互联网公司联手进军移动互联网领域的实质性一步.8月19日,中国电信与易网公司共同宣布合资成立浙江翼信科技有限公司(以下简称"翼信公司"),并发布新一代移动即时通讯社交产品"易信".当天,易信1.0版本正式登陆各大手机应用商店供 ...
  •     据国外媒体报道,最近一段时间,IT管理者一直在不断地迅速学习,服务器虚拟化.桌面VDI.Exchange.SharePoint,微软不断地在企业中注入新鲜的元素.在这么多新产品的围攻之下,管理者很难空出时间去学习Windows 7的相关小技巧.     下面,就为大家总结了Windows 7 ...
一周排行
  •   svn(subversion)是近年来崛起的版本管理工具,是cvs的接班人.目前,绝大多数开源软件都使用svn作为代码版本管理软件.     svn服务器有2种运行方式:独立服务器和与apache整合.2种方式各 ...
  • Java 开源博客 -- B3LOG Solo 0.6.1 正式版发布了!欢迎大家下载.该版本主要是改善细节体验,并加入了一款 Metro 风格的皮肤. 特性基于标签的文章分类Ping Google Blog Sea ...
  • vTag,untag以及交换机的各种端口模式是网络工程技术人员调试交换机时接触最多的概念了,然而笔者发现在实际工作中技术人员往往对这些概念似懂非懂,笔者根据自己的理解再结合一个案例,试图向大家阐明这些概念 h3C u ...
  •  中国信息安全专家俞晓秋28日告诉<环球时报>记者,从名称上看,2001年成立了“国家信息化领导小组”, 而这次成立的是“中央网络安全与信息化领导小组”,机构的层级提到最高.同时该名称不但新增了“网络安全 ...
  • int超内存 要用short或者滚动数组 滚动数组 #include #include #include #include #include #include #include #include #include # ...
  • 需求:开发一个metro应用,因为要给平面设计师参谋, 需要将软件安装在win8平板上. 环境:开发机是win8,  win8平板是win8.1rtm , 是用老的win7平板改装的. 步骤: 1:拷贝开发机中C:\ ...
  • 哎,安装个apt-get install scim-tables-js后发现很难用,首先是不能够打出同音字其次是每次在平假名,片假名和汉字之间转化很麻烦要在3中之间转化,而且没有快捷键,这次安装了anthy,,方便多 ...
  • 如果说cfs是linux的一个很有创意的机制的话,那么linux中另一个创意就是nohz,我在前面已 经写了好几篇关于nohz的文章了,因此本文就不再阐述代码细节了,linux的创意在于设计而不在代码,代码主要解决的 ...
  • 机房收费系统代码全部实现完成,接下来就是打包.远程发布测试.本来以为打包是个很简单的事却错误百出.下面做一下打包总结. vb.net打包完全可以用vs自带的打包工具打包: 首先打开Vs新建项目,在"已安装模 ...
  • 为大家介绍的就是大地图辐射云的过法,供大家参考 <废土2>中大地图辐射云怎么过,有些玩家不是很清楚,下面为大家介绍的就是大地图辐射云的过法,供大家参考. 问题详述: 大地图的辐射云如何过?我见有些地点都在 ...