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 ...
一周排行
  •        随着移动互联网用户井喷式的增长,web前端开发中的HTML5在近几年备受瞩目,越来越多的人从事html5开发相关工作.今天小编也来凑个热闹,和大家一起来谈谈HTML5中<a>标签的ping属 ...
  • 面向对象的思想中存在如下几种关系,一般为了方便交流都使用UML的类图来展现类之间的关系.所以了解类图中符号的含义对看懂类图,尤其是用类图展示的设计模式很有帮助.下面依次介绍这几种关系   类继承关系 继承关系使用空心 ...
  • CSS框架通常指的是一些CSS文件的集合,这些文件包括网页的基本布局.表单样式.网格或简单结构.以及样式重置.例如,typography.css是基本排版规.grid.css是基于网格的布局.layout.css通常 ...
  •     我相信,绝大多数人都听过田忌赛2马的故事,讲述的是一个人通过自己的智慧帮助原本处劣势或者平等的一方获得一场马匹比赛的胜利,让我们回顾下这个有意思的故事          齐国使者到大梁来,孙膑以刑徒的身份秘密 ...
  • 当今世界正在经历一场超级名模的复兴.自上世纪80年代以来,模特界还从未享受过当下这般广泛性.世界性的认可,以及由此而来的名气和财富--想想凯特·莫斯(Kate Moss).纳奥米·坎贝尔(Naomi Campbell ...
  • 硕鼠硕鼠,无食我黍!三岁贯女,莫我肯顾.逝将去女,适彼乐土.乐土乐土,爰得我所.硕鼠硕鼠,无食我麦!三岁贯女,莫我肯德.逝将去女,适彼乐国.乐国乐国,爰得我直.硕鼠硕鼠,无食我苗!三岁贯女,莫我肯劳.逝将去女,适彼乐 ...
  • 易网科技讯 9月4日消息,据国外媒体报道,在亚马逊周二意外上线新款Kindle Paperwhite官方网页数小时之后,公司正式宣布了该新产品的发布.亚马逊周二早些时候意外将新款Kindle Paperwhite的介 ...
  • 最新的iOS 7.1.1系统中的锁屏功能还是存在有一定的漏洞,这种漏洞的存在可以让别人在锁屏的情况下,无需密码就能看到你的整个联络人清单和资料,还可以直接致电.传送讯息或电邮,影响所有运行 iOS 7.1.1 的 i ...
  • 2012年度IT博客大赛50强 张善友(张善友) 参赛感言: 我的博客能从100强进入50强,都排在第5位,无论是否能够进行进入前10强.首先感谢各位评委和众多网友的大力支持和51CTO提供的这个平台. 我的博客始于 ...
  • dialog消费掉返回键 有些时候当dialog弹出的时候 ,我们按一下返回键,当dialog消失的时候,我们还想做一些处理,这时候我们自然想到在onkeydown里面写,但是你却发现onkeydown里面根本监听不 ...