首页 > 代码库 > (中等) POJ 3225 Help with Intervals , 线段树+集合。
(中等) POJ 3225 Help with Intervals , 线段树+集合。
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 A ∪ B {x : x ∈ A or x ∈ B} Intersection A ∩ B {x : x ∈ A and x ∈ B} Relative complementation A − B {x : x ∈ A but x ∉ B} Symmetric difference A ⊕ B (A − B) ∪ (B − A)
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 | S ← S ∪ T |
I T | S ← S ∩ T |
D T | S ← S − T |
C T | S ← T − S |
S T | S ← S ⊕ T |
#include<iostream>#include<cstdio>#include<cstring>#define lson L,M,po*2#define rson M+1,R,po*2+1using namespace std;const int N=65535*2;bool COL[140000*4]={0};bool XOR[140000*4]={0};bool vis[140000]={0};bool have=0;void pushDown(int po){ if(COL[po]) { COL[po*2]=COL[po*2+1]=COL[po]; COL[po]=0; XOR[po*2]=XOR[po*2+1]=0; // don‘t forget!!! } if(XOR[po]) { XOR[po*2]=!XOR[po*2]; XOR[po*2+1]=!XOR[po*2+1]; XOR[po]=0; }}void updateC(int ul,int ur,bool type,int L,int R,int po){ if(ul>ur) return; if(ul<=L&&ur>=R) { XOR[po]=0; COL[po]=type; return; } pushDown(po); int M=(L+R)/2; if(ul<=M) updateC(ul,ur,type,lson); if(ur>M) updateC(ul,ur,type,rson);}void updateX(int ul,int ur,int L,int R,int po){ if(ul>ur) return; if(ul<=L&&ur>=R) { XOR[po]=!XOR[po]; return; } pushDown(po); int M=(L+R)/2; if(ul<=M) updateX(ul,ur,lson); if(ur>M) updateX(ul,ur,rson);}void query(int L,int R,int po){ if(L==R) { vis[L]=COL[po]^XOR[po]; if(vis[L]) have=1; return; } pushDown(po); int M=(L+R)/2; query(lson); query(rson);}int main(){ char C; char t1,t2; int a,b; int x,y; while(cin>>C) { scanf(" %c%d,",&t1,&a); scanf("%d%c",&b,&t2); a*=2; b*=2; if(t1==‘(‘) ++a; if(t2==‘)‘) --b; switch(C) { case ‘U‘: updateC(a,b,1,0,N,1); break; case ‘I‘: updateC(0,a-1,1,0,N,1); updateX(0,a-1,0,N,1); updateC(b+1,N,1,0,N,1); updateX(b+1,N,0,N,1); break; case ‘D‘: updateC(a,b,1,0,N,1); updateX(a,b,0,N,1); break; case ‘C‘: updateC(0,a-1,1,0,N,1); updateX(0,a-1,0,N,1); updateC(b+1,N,1,0,N,1); updateX(b+1,N,0,N,1); updateX(a,b,0,N,1); break; case ‘S‘: updateX(a,b,0,N,1); break; } } query(0,N,1); if(!have) { printf("empty set\n"); return 0; } bool has=0; for(int i=0;i<=N+1;++i) { if(vis[i]) { if(!has) { has=1; if(i%2) printf("(%d,",(i-1)/2); else printf("[%d,",i/2); } } else { if(has) { has=0; if((i-1)%2) printf("%d) ",i/2); else printf("%d] ",(i-1)/2); } } } return 0;}
(中等) POJ 3225 Help with Intervals , 线段树+集合。