校门三部曲，总算完结了！完结散花！
难度呈阶梯状，都可以用线段树解决。
第一部
P1047 校门外的树（线段树优化）难度⭐⭐
第二部
P1276 校门外的树（增强版）（线段树）校门三部曲难度⭐⭐⭐
第三部
P5568 [SDOI2008]校门外的区间（离散数学应用+线段树+开闭区间处理）难度⭐⭐⭐⭐★
输出
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
输入
(2,3)
0≤a,b≤65535,M≤70000
转化成线段树的区间覆盖+翻转问题
用线段树维护当前区间
并且维护两个标记 cov,tag，分别代表覆盖和翻转的标记
- U: A∪B B区间覆盖1
- I： A∩B B区间的补集覆盖0
- D： A−B B区间覆盖0
- C： B−A 全集范围内01翻转，转到II操作
- S： A⊕B B区间范围内01翻转
细节处理
输入输出细节
开闭用*2方法处理
覆盖和翻转的优先级
%%%
以上是大佬的思路
上面的各种修改操作自己想一下就懂了，实在不行就画个图看看
我做这道题的感受
- 学习到了
奇怪的输入输出 - 刚学的辣鸡离散就派上用场了
- 注意看清题目要求，少了一个空格De了半个小时的bug 艹
- 学到了处理开闭区间的方法：*2，判断边界是奇数还是偶数
开闭区间操作：
区间端点均为整数，不妨认为 （l，r）为（l+0.5,r−0.5）
乘2就可以换算成整数区间
下面的链接是具体开闭区间的解释，里面有我用ipad画的解释和样例，应该很清楚
实现选择开区间或闭区间的操作，输出开区间或闭区间 详解（线段树运用）
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll N=132010;
const ll mod=100000000;
struct segment
{
ll l,r;
ll cov;//覆盖标记
ll tag;//翻转标记
}tree[N<<2];
ll ans[N],n=N;
char s[20];
inline void get(ll &l,ll &r)
{
char c=getchar();
while(c!='('&&c!='[')c=getchar();
ll w=(c=='(');l=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))l=(l<<1)+(l<<3)+(c^48),c=getchar();
l<<=1;//乘2是为了区分开区间还是闭区间
l+=w;r=0;//是开区间说明要+1
while(!isdigit(c))c=getchar();
while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
r<<=1;
while(c!=')'&&c!=']')c=getchar();
r-=(c==')');//处理开闭区间//是开区间说明需要-1
}
inline void push_down(ll p)
{
if(tree[p].cov!=-1)
{
tree[ls].cov=tree[rs].cov=tree[p].cov;
tree[ls].tag=tree[rs].tag=0;//先都初始化为0
tree[p].cov=-1;
}
if(tree[p].tag)
{
tree[ls].tag^=1,tree[rs].tag^=1;//相同为0不同为1，把区间翻转
tree[p].tag=0;
}
}
inline void build(ll p,ll l,ll r)
{
tree[p].l=l,tree[p].r=r,tree[p].cov=-1;
if(l==r)return;
ll mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
}
inline void update(ll p,ll l,ll r,ll k)
{
if(tree[p].l>r||tree[p].r<l||l>r)return;
if(tree[p].l>=l&&tree[p].r<=r)
{
if(k!=2)tree[p].cov=k,tree[p].tag=0;
else tree[p].tag^=1;//需要的话就翻转
return;
}
push_down(p);
update(ls,l,r,k),update(rs,l,r,k);
}
inline void query(ll p)
{
if(tree[p].l==tree[p].r)
{//如果这个点没有被修改过那它一直都是0，否则就是看它当前被修改成了什么（cov），然后再异或上tag，翻转过后的值
ans[tree[p].l]=(tree[p].cov==-1)?0:tree[p].cov^tree[p].tag;
return;
}
push_down(p);
query(ls),query(rs);
}
inline void print()
{
query(1);
int flag=0,Empty=0;
for(int i=0;i<=n;++i)
{
if(ans[i]&&!flag)//遍历一遍，找到左边界
{
flag=Empty=1;
if(i&1)printf("(%d,",(i-1)>>1);//如果是奇数说明是开区间
else printf("[%d,",i>>1);
}
if(!ans[i]&&flag)
{
flag=0;
if(i&1)printf("%d]\n",(i-1)>>1);//如果是奇数说明是闭区间
else printf("%d)\n",i>>1);
}
}
if(!Empty)
puts("empty set");
}
int main()
{
build(1,0,n);
while(scanf("%s",s)!=EOF)//接受第一个字符
{
ll l,r;
get(l,r);
if(s[0]=='U')update(1,l,r,1);//U是求并集（区间内全部改为1）
else if(s[0]=='I')update(1,0,l-1,0),update(1,r+1,n,0);//I是求交集（区间以外全部为0，不相交就全为0嘛）
else if(s[0]=='D')update(1,l,r,0);//D是减去该区间，所以区间内全为0
else if(s[0]=='C')update(1,0,n,2),update(1,0,l-1,0),update(1,r+1,n,0);//全集范围内01翻转，并将区间的补集覆盖0
else update(1,l,r,2);//区间范围内01翻转
}
print();
return 0;
}
120多行的代码debug是真的累
有任何疑问欢迎评论哦虽然我真的很菜
京公网安备 11010502036488号