首页 > 代码库 > Help with Intervals（集合的交并补，线段树）

Help with Intervals（集合的交并补，线段树）

2024-07-07 00:56:20   226人阅读

很早以前做过这题，早就没印象了，估计当时也是照着某大神的代码抄过的，现在是连题意都看了好长时间。

刚开始的S集合是空集，给你一些操作和一个T集合，把操作的结果再赋给S集合。

解法：因为会有开区间和闭区间，对于一个值我拆成了两个点 比如 1,2,3, 表示的区间为[1,2] 把两个端点值分别设为2个点，把端点之间的区间也设为一个点，那么 区间就可以表示为(1,2) = 1，[1,2) = 1,2  (1,2] = 2,3   ，把这些点建成树，然后进行区间的操作，也就转换成了对点的操作。

并操作，就是直接把a-b变为1.

S-T 操作。 直接把T的区间段变为0.

T-S 操作， 这个需要特别说明一下，因为这个操作的结果是把T之外的区间清零，把T这段区间的值变为相反的，这个不能用延迟覆盖来操作，需要加一个延迟标记，表示这段区间我需要逆置。

异或操作，异或操作的结果就是 T之外的区间不变化，T这段区间逆置，跟上面类似。

如果此段已有逆置的延迟标记，再加一个的话相当于抵消。

忘记判空集 ，WA一次。

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 140000
 12 #define M 132000
 13 #define LL long long
 14 #define INF 0xfffffff
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 int s[N<<2],a[N],xlz[N<<2],lz[N<<2];
 19 struct node
 20 {
 21     int l,r,f;
 22 }p[N];
 23 void down(int w,int m)
 24 {
 25     if(lz[w]!=-1)
 26     {
 27         s[w<<1] = s[w<<1|1] = lz[w<<1] = lz[w<<1|1] = lz[w];
 28         xlz[w<<1] = xlz[w<<1|1] = 0;
 29         lz[w] = -1;
 30     }
 31     if(xlz[w])
 32     {
 33         xlz[w<<1] ^= 1;
 34         xlz[w<<1|1] ^= 1;
 35         xlz[w] = 0;
 36     }
 37 }
 38 void build(int l,int r,int w)
 39 {
 40     lz[w] = -1;
 41     xlz[w] = 0;
 42     s[w] = 0;
 43     if(l==r)
 44     {
 45         return ;
 46     }
 47     int m = (l+r)>>1;
 48     build(l,m,w<<1);
 49     build(m+1,r,w<<1|1);
 50 }
 51 void update(int a,int b,int p,int d,int l,int r,int w)
 52 {
 53     if(a<=l&&b>=r)
 54     {
 55         //cout<<l<<" "<<r<<" "<<w<<endl;
 56         if(p==1)
 57         {
 58             s[w] = d;
 59             lz[w] = d;
 60             xlz[w] = 0;
 61         }
 62         else
 63         {
 64             xlz[w] ^= 1 ;
 65         }
 66         return;
 67     }
 68     down(w,r-l+1);
 69     int m = (l+r)>>1;
 70     if(a<=m) update(a,b,p,d,l,m,w<<1);
 71     if(b>m) update(a,b,p,d,m+1,r,w<<1|1);
 72 }
 73 int query(int p,int l,int r,int w)
 74 {
 75     if(l==r)
 76     {
 77         if(xlz[w])
 78         {
 79             s[w]^=1;
 80             xlz[w] ^= 1;
 81         }
 82         return s[w];
 83     }
 84     down(w,r-l+1);
 85     int m = (l+r)>>1;
 86     if(p<=m) return query(p,l,m,w<<1);
 87     else return query(p,m+1,r,w<<1|1);
 88 }
 89 int main()
 90 {
 91     int x,y,i;
 92     char sr[5],c1,c2;
 93     build(1,M,1);
 94     while(scanf("%s",sr)!=EOF)
 95     {
 96         getchar();
 97         scanf("%c%d,%d%c",&c1,&x,&y,&c2);
 98         x = (c1==‘[‘?2*x+1:2*x+2);
 99         y = (c2==‘]‘?2*y+1:2*y);
100         if(sr[0]==‘U‘)
101         {
102             update(x,y,1,1,1,M,1);
103         }
104         else if(sr[0]==‘I‘)
105         {
106             if(x>1)
107             update(1,x-1,1,0,1,M,1);
108             update(y+1,M,1,0,1,M,1);
109         }
110         else if(sr[0]==‘D‘)
111         {
112             update(x,y,1,0,1,M,1);
113         }
114         else if(sr[0]==‘C‘)
115         {
116             if(x>1)
117             update(1,x-1,1,0,1,M,1);
118             update(y+1,M,1,0,1,M,1);
119             update(x,y,2,0,1,M,1);
120         }
121         else
122         {
123             update(x,y,2,0,1,M,1);
124         }
125     }
126     int g = 0;
127     for(i = 1; i <= M ;i++)
128     a[i] = query(i,1,M,1);
129     for(i = 1 ; i <= M ; i++)
130     {
131         if(a[i]&&a[i]!=a[i-1])
132         {
133             g++;
134             p[g].l = (i-1)/2;
135             p[g].f = (i%2?1:0);
136         }
137         else if(a[i]!=a[i-1])
138         {
139             p[g].r = (i-1)/2;
140             p[g].f+=((i-1)%2?2:0);
141         }
142     }
143     for(i = 1 ; i <= g ;i++)
144     {
145         if(p[i].f==0)
146         printf("(%d,%d)",p[i].l,p[i].r);
147         else if(p[i].f==1)
148         printf("[%d,%d)",p[i].l,p[i].r);
149         else if(p[i].f==2)
150         printf("(%d,%d]",p[i].l,p[i].r);
151         else
152         printf("[%d,%d]",p[i].l,p[i].r);
153         if(i!=g) printf(" ");
154     }
155     if(g==0) puts("empty set");
156     else
157     puts("");
158     return 0;
159 }
View Code

 

 


联系
我们