poj 3225 Help with Intervals(线段树区间更新)

By | 09月24日
Advertisement

题意:

有5种集合运输操作,问通过这些操作,最后能得到的取决是什么。

解析:

初看这题没有什么思路,参考了网络上的题解才解决了该问题。

这个题目就两个关键点,搞明白就没什么问题:

  1. 关于集合运算的推导规约,知道集合是什么东西就一定会推导!

    U:把区间[l,r]覆盖成1
    I:把[-∞,l)(r,∞]覆盖成0
    D:把区间[l,r]覆盖成0
    C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
    S:[l,r]区间0/1互换

  2. 倍化区间处理开闭区间的问题。因为普通的线段树实际处理的并非真正的区间,而是一系列点,相当于处理一个向量。这个问题需要处理的是真正的区间,所以应该有一个主导思想就是,把区间点化!不知哪位大牛搞了一个倍增区间出来,实在佩服!对于待处理区间a,b,对其边界均乘2。若区间左开则对左界值+1,若区间右开,则对右界-1!

    如:[2,3]会倍增为[4,6],[2,3)会倍增为[4,5],(2,3]会倍增为[5,6],(2,3)将倍增为[5,5],我们这时可以看到,对于普通线段树无法处理的线段如(x,x+1)将被点化为[2∗x+1,2∗x+1],这个问题得到比较完美的解决

    最后把查找出来的区间逆向倍增操作一下,就可以得到实际的区间以及起开闭情况!

    区间倍增后,就是线段树的区间更新了,这时候一定要思路清晰!

    成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作。
    很明显我们可以知道这个性质当一个区间被覆盖后,不管之前有没有异或标记都没有意义了。所以当一个节点得到覆盖标记时把异或标记清空,而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记。

注意:

题目中还要处理一些无效输入如(4,4)这种没有意义的区间,这些区间要特判。

my code

#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 MAXN = 67000 * 2;

struct Interval {
    char lch, rch;
    int a, b;
    Interval() {}
    Interval(char lch, int a, int b, char rch) : lch(lch), a(a), b(b), rch(rch) {}
} inter[MAXN];

int XOR[MAXN<<2], cover[MAXN<<2];
int total;

inline void reversal(int o) {
    if(cover[o] != -1) cover[o] ^= 1;
    else XOR[o] ^= 1;
}

inline void pushDown(int o) {
    if(cover[o] != -1) {
        cover[ls] = cover[rs] = cover[o];
        XOR[ls] = XOR[rs] = 0;
        cover[o] = -1;
    }
    if(XOR[o]) {
        reversal(ls);
        reversal(rs);
        XOR[o] = 0;
    }
}

void update(int o, int L, int R, int ql, int qr, int val) {
    if(ql > qr || ql < 0) return ;
    if(ql <= L && R <= qr) {
        if(val != -1) cover[o] = val, XOR[o] = false;
        else reversal(o);
        return ;
    }
    pushDown(o);
    int M = (L+R)/2;
    if(ql <= M) update(lson, ql, qr, val);
    if(qr > M) update(rson, ql, qr, val);
}

void query(int o, int L, int R) {
    if(cover[o] == 1) {
        char lch, rch;
        int a, b;

        lch = (L & 1) ? '(' : '[';
        a = L >> 1;

        rch = (R & 1) ? ')' : ']';
        b = (R+1) >> 1;

        inter[total++] = Interval(lch, a, b, rch);
        return ;
    }else if(cover[o] == 0) return ;
    pushDown(o);
    int M = (L+R)/2;
    query(lson);
    query(rson);
}

void printPath() {
    if(total == 0) puts("empty set");
    else {
        char lch = inter[0].lch, rch = inter[0].rch;
        int a = inter[0].a, b = inter[0].b;
        for(int i = 1; i < total; i++) {
            if(b == inter[i].a && (rch == ']' || inter[i].lch == '[')) {
                b = inter[i].b;
                rch = inter[i].rch;
            }else {
                printf("%c%d,%d%c ", lch, a, b, rch);
                lch = inter[i].lch;
                a = inter[i].a;
                b = inter[i].b;
                rch = inter[i].rch;
            }
        }
        printf("%c%d,%d%c\n", lch, a, b, rch);
    }
}

int main() {
    char oper, lchar, rchar;
    int ql, qr;

    cover[1] = XOR[1] = 0;
    while(scanf("%c %c%d,%d%c%*c", &oper, &lchar, &ql, &qr, &rchar) != EOF) {
        ql *= 2;
        qr *= 2;

        if(lchar == '(') ql++;
        if(rchar == ')') qr--;

        if(oper == 'U') {
            update(1, 0, MAXN, ql, qr, 1);
        }else if(oper == 'I') {
            update(1, 0, MAXN, 0, ql-1, 0);
            update(1, 0, MAXN, qr+1, MAXN, 0);
        }else if(oper == 'D') {
            update(1, 0, MAXN, ql, qr, 0);
        }else if(oper == 'C') {
            update(1, 0, MAXN, 0, ql-1, 0);
            update(1, 0, MAXN, qr+1, MAXN, 0);
            update(1, 0, MAXN, ql, qr, -1);
        }else {
            update(1, 0, MAXN, ql, qr, -1);
        }
    }
    query(1, 0, MAXN);
    printPath();
    return 0;
}

Similar Posts:

  • POJ 2528 Mayor&#39;s posters // 线段树 区间更新 离散化

    题目描述 POJ 2528 Mayor's posters 解题思路 题目大意: 在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报? 首先数据量较大,应该进行离散化,然后进行线段树的区间更新和查询. 但这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误 给出下面两个简单的例子应该能体现普通离散化的缺陷: eg1: [1, 10] [1, 5] [6, 10] ( [1, 10] 被后两个区间完全覆盖掉了) eg2: [1, 10] [1, 4] [

  • poj 2528 Mayor&#39;s posters(线段树区间更新+离散化)经典题目,较难。。。

    1.http://poj.org/problem?id=2528 2.题目大意: 有一面墙,宽度是10000000,现在要在这面墙上贴海报,每张海报的高度都是墙的高度,但是宽度不同,现在给出各个海报的宽度,按照贴的顺序,后贴的会覆盖先贴的,求都贴完后,能看到几张海报,一张海报只要露着一部分就算是一张可以看到的 3.思路: 由于题目中wall有10000000bytes long,直接线段树无疑会MLE.所以要对其离散化,基本做法是:先对所有端点坐标进行排序,用相应序号代替端点坐标构造线段树进行计

  • POJ 1436 Horizontally Visible Segments [线段树-区间更新]【数据结构】

    题目链接:http://poj.org/problem?id=1436 -------------------------. Horizontally Visible Segments Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 5262 Accepted: 1932 Description There is a number of disjoint vertical line segments in the plane.

  • Uva 1232 - SKYLINE ( 线段树 + 区间更新 )

    Uva 1232 SKYLINE (线段树 + 区间更新) 题意: 按照顺序在地面上建造放在,每个房子的高度为h,操作 l r h 表示 在(l,r] 区间建立一个高度为h的房子.统计每次建立完房子之后的overlap值之和 overlap值表示[ 修完一座房子之后,统计它在多长的部分是最高的(可以和其他房子并列高) ]如样例图,按照灰.黒.白的顺序建立房子 ans = (11-5) + (5-1) + (5-3) + (13-11) = 6 + 4 + 4 = 14 分析: 一开始一直想不明白

  • ZOJ 1610 Count the Colors (线段树区间更新)

    题目链接 题意 : 一根木棍,长8000,然后分别在不同的区间涂上不同的颜色,问你最后能够看到多少颜色,然后每个颜色有多少段,颜色大小从头到尾输出. 思路 :线段树区间更新一下,然后标记一下,最后从头输出. //ZOJ 1610 #include <cstdio> #include <cstring> #include <iostream> using namespace std ; int p[8010*4],lz[8010*4] ,hashh[8010*4],has

  • CodeForces 46D Parking Pot(线段树区间更新)

    Parking Lot time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Nowadays it is becoming increasingly difficult to park a car in cities successfully. Let's imagine a segment of a street as long

  • HDU 3468 A Simple Problem with Integers 线段树 区间更新

    学习阶段,仿着别人的博客写了一个,感谢 notonlysuccess 大大的博文- 线段树区间更新,注意 scanf() 函数会读取缓存区的回车 贴代码(AC,2516ms) #include <cstring> #include <cstdio> #include <iostream> #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 using namespace st

  • HDU1698线段树区间更新

    原题http://acm.hdu.edu.cn/showproblem.php?pid=1698 Just a Hook Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16935 Accepted Submission(s): 8427 Problem Description In the game of DotA, Pudge's mea

  • HDU 1556 Color the ball【线段树区间更新,一次查询+数组模拟】

    Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18104    Accepted Submission(s): 9032 Problem Description N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的"小飞鸽"

  • 线段树 + 区间更新(区间增加v)模板 ---- poj 3468 - Snarl_jsb

    A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 59798 Accepted: 18237 Case Time Limit: 2000MS Description You have N integers, A 1 , A 2 , ... , A N . You need to deal with two kinds of operations. One type

  • UESTC 1425 求任意区间的LIS 线段树区间更新区间查询

    九野的博客,转载请注明出处:http://blog.csdn.net/acmmmm/article/details/11976621 Description For a sequence S1,S2,...,SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 <...< Sj-1 < Sj, then the sequence Si,Si+1,...,Sj i

Tags: