POJ 3225-线段树求区间或集合的交并补、异或

By | 04月16日
Advertisement

Help with Intervals

Time Limit: 6000MS Memory Limit: 131072K
Total Submissions: 9208 Accepted: 2185
Case Time Limit: 2000MS

Description

LogLoader, Inc. is a company specialized in providing products for analyzing logs. While Ikki is working on graduation design, he is also engaged in an internship at LogLoader. Among his tasks, one is to write a module for manipulating time intervals, which have confused him a lot. Now he badly needs your help.

In discrete mathematics, you have studied several basic set operations, namely union, intersection, relative complementation and symmetric difference, which naturally apply to the specialization of sets as intervals.. For your quick reference they are summarized in the table below:

Operation Notation
Definition

Union AB {x : xA or xB}
Intersection AB {x : xA and xB}
Relative complementation AB {x : xA but xB}
Symmetric difference AB (AB) ∪ (BA)

Ikki has abstracted the interval operations emerging from his job as a tiny programming language. He wants you to implement an interpreter for him. The language maintains a set S, which starts out empty and is modified as specified by the following commands:

Command Semantics
U T SST
I T SST
D T SST
C T STS
S T SST

Input

The input contains exactly one test case, which consists of between 0 and 65,535 (inclusive) commands of the language. Each command occupies a single line and appears like

X T

where X is one of ‘U’, ‘I’, ‘D’, ‘C’ and ‘S’ and T is an interval in one of the forms (a,b), (a,b], [a,b) and [a,b] (a, bZ, 0 ≤ ab ≤ 65,535), which take their usual meanings. The commands are executed in the order they appear in the input.

End of file (EOF) indicates the end of input.

Output

Output the set S as it is after the last command is executed as the union of a minimal collection of disjoint intervals. The intervals should be printed on one line separated by single spaces and appear in increasing order of their endpoints. If S is empty, just print “empty set” and nothing else.

Sample Input

U [1,5] D [3,3] S [2,4] C (1,5) I (2,3]

Sample Output

(2,3)

Source

PKU Local 2007 (POJ Monthly--2007.04.28), frkstyc

[Submit] [Go Back] [Status] [Discuss]

POJ 3225-线段树求区间或集合的交并补、异或
Home Page POJ 3225-线段树求区间或集合的交并补、异或
Go Back POJ 3225-线段树求区间或集合的交并补、异或
To top



All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator

题意:区间操作,交,并,补等
思路:
我们一个一个操作来分析:(用0和1表示是否包含区间,-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互换

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

开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
线段树功能:update:成段替换,区间异或 query:简单hash

代码:

#include <cstdio> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1   const int maxn = 131072; bool hash[maxn+1]; int cover[maxn<<2]; int XOR[maxn<<2]; void FXOR(int rt) {  if (cover[rt] != -1) cover[rt] ^= 1;    else XOR[rt] ^= 1; } void PushDown(int rt) {    if (cover[rt] != -1) {      cover[rt<<1] = cover[rt<<1|1] = cover[rt];      XOR[rt<<1] = XOR[rt<<1|1] = 0;      cover[rt] = -1;     }   if (XOR[rt]) {      FXOR(rt<<1);      FXOR(rt<<1|1);        XOR[rt] = 0;    } } void update(char op,int L,int R,int l,int r,int rt) {   if (L <= l && r <= R) {       if (op == 'U') {            cover[rt] = 1;          XOR[rt] = 0;        } else if (op == 'D') {             cover[rt] = 0;          XOR[rt] = 0;        } else if (op == 'C' || op == 'S') {            FXOR(rt);       }       return ;    }   PushDown(rt);   int m = (l + r) >> 1;     if (L <= m) update(op , L , R , lson);   else if (op == 'I' || op == 'C') {      XOR[rt<<1] = cover[rt<<1] = 0;  }   if (m < R) update(op , L , R , rson);    else if (op == 'I' || op == 'C') {      XOR[rt<<1|1] = cover[rt<<1|1] = 0;  } } void query(int l,int r,int rt) {    if (cover[rt] == 1) {       for (int it = l ; it <= r ; it ++) {             hash[it] = true;        }       return ;    } else if (cover[rt] == 0) return ; //  if (l == r) return ; // the leaf node never be -1   PushDown(rt);   int m = (l + r) >> 1;     query(lson);    query(rson); } int main() {     cover[1] = XOR[1] = 0;  char op , l , r;    int a , b;  while ( ~scanf("%c %c%d,%d%cn",&op , &l , &a , &b , &r) ) {         a <<= 1 , b <<= 1;      if (l == '(') a ++;         if (r == ')') b --;         if (a > b) {             if (op == 'C' || op == 'I') {               cover[1] = XOR[1] = 0;          }       } else update(op , a , b , 0 , maxn , 1);   }   query(0 , maxn , 1);    bool flag = false;  int s = -1 , e;     for (int i = 0 ; i <= maxn ; i ++) {         if (hash[i]) {          if (s == -1) s = i;             e = i;      } else {            if (s != -1) {              if (flag) printf(" ");              flag = true;                printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']');                s = -1;             }       }   }   if (!flag) printf("empty set");     puts("");   return 0; }

http://www.notonlysuccess.com/index.php/segment-tree-complete/

Similar Posts:

  • hdu 1754 I Hate It (线段树求区间最值)

    HDU1754 I Hate It Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Description 很多学校流行一种比较的习惯.老师们很喜欢询问,从某某到某某当中,分数最高的是多少. 这让很多学生很反感. 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问.当然,老师有时候需要更新某位同学的成绩. Input 本题目包含多组测试,请处理到文件结束. 在每个测试的第一行,

  • POJ2823 - 线段树求区间的最值..

    本来想搞单调队列的....结果网上搜单调队你列的题...一搜搜到这道...一看...果断敲线段树..还没写过线段树求最值的....在求和上稍微修改下就可以了...而且这个题目没有修改的...所以一开始建好树后...不需要Updata...只要寻找答案就可以了...这个程序的主心部分就是如何用线段树求最值... 首先来看初始化的问题....既然我们要求一段区间的最大值和最小值...那就在初始化时构造两棵树好了...一颗TreeMin存最小值...一颗TreeMax存最大值...TreeMin的非叶

  • POJ 3264 Balanced Lineup 线段树求区间最大最小(普通线段树,ZKW线段树)

    Balanced Lineup Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 30604 Accepted: 14431 Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John de

  • poj 3225 线段树 经典题

    泪奔... 终于A拉. 网上已经有很多的题解了... 就不详细描述了. 集合的操作还是蛮有趣的. 线段树原来可以这么灵活啊 0 1 的覆盖即使有区间操作也用不着重新写个标记 还有 线段树 中 如果操作的是区间的话 (端点和内部的点都有意义) 那么点的数量扩大两倍. 经过一题..感觉线段树的 level 又提升了呢.. #include <stdio.h> #include <iostream> #include <queue> #include <algorith

  • 线段树求区间和(单点更新)

    题目1:敌兵布阵 线段树的主要操作:(1)建立线段树(Build) (2)更新区间值 (Update) (3)查询区间(Query) 写法一: #include <stdio.h> #define maxn 55555 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[maxn<<2]; void PushUP(int rt) { sum[rt]=sum[rt<<1]+sum[rt

  • poj3225Help with Intervals(线段树求区间交并补)

    http://poj.org/problem?id=3225 先贴代码 有空再解释 View Code 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define N 140000 7 int s[N<<2],kc[N<<2],hash[N]; 8 void bui

  • Codeforces VK Cup 2015 - Qualification Round 1 D. Closest Equals 离线线段树 求区间相同数的最小距离

    D. Closest Equals Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php?id=3224 Description You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum

  • ZOJ 题目3911 Prime Query(线段树求区间素数个数)

    Prime Query Time Limit: 1 Second Memory Limit: 196608 KB You are given a simple task. Given a sequence A[i] with N numbers. You have to perform Q operations on the given sequence. Here are the operations: A v l, add the value v to element with index

  • |poj 2528|线段树|Mayor&#39;s posters

    poj传送门 线段树离散化区间后区间染色,注意离散化问题 #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define ms(i,j) memset(i,j, sizeof i); using namespace std; const int MAXN = 10000 + 5; const int LEFT = 0, RIGHT = 1; struct poi

  • poj 3667 线段树-区间的前缀和后缀

    // // main.cpp // poj 3667 线段树-区间的前缀和后缀 // // Created by XD on 15/9/13. // Copyright (c) 2015年 XD. All rights reserved. // /* 线段树的区间更新 这里需要注意的是线段树的每个节点应该保存什么样的属性. 这里是要找到一个区间使得其长度为d,且左边的值最小.我们保持线段树的节点的sum属性,pre属性,和suffix属性. 这里的pre,和suffix的更新是关键的地方,得注意

Tags: