P5568 [SDOI2008] 校门外的区间 题解
曾经有位先人说过：抄题解和交题解是你学会一个东西的唯一检验方式。
所以蒟蒻就来交一发题解 水估值 巩固记忆啦。
题意
题目看起来很难操作，但是需要维护的集合其实是一段，也就是一个个权值区间。
-
操作一，区间赋值 1。
-
操作二，区间反赋值 0。也就是把除了这段区间所有地方的都赋值为 0。
-
操作三，区间赋值 0。
-
操作四，区间反赋值 0，然后区间异或。原因请配合图片食用。
- 操作五，区间异或。
如果有不理解的可以自己去百度区间运算的规则。
区间操作
题目大意理解完之后，我们再看 区间操作：
对这题来说要知道的就是：圆括号代表端点不取，方括号代表端点要包含。
我们看样例：(2,3)。这是什么？如果集合简单的只是整数集合的话，这个集合没有任何的数，也就不会被输出。那么意思就是：这道题的集合包含的范围是实数。
那么我们就要开 double 然后操作一大堆吗？不是的。我们发现输入的左右端点一定是整数，也就是说我们可以把 (2 这样的东西定义成 2.5。但是开浮点数还是会导致代码极其难调，所以我们可以把整个数列开大一倍：
图很炸裂凑合看吧，谢谢啦。
输出处理
这里蒟蒻用了一种很笨的方法：
最后统一查询一遍，如果子树的和等于子树长度，就代表子树全都在集合中。然后把这个子树的端点标记一下，如果端点是奇数代表在储存时是圆括号存的，否则是方括号存的。
因为蒟蒻太弱了解释不清就看代码吧：
#include <bits/stdc++.h>
#define int long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
const int N=65540;
int a,b;
char op,lb,rb,tc,ans[N];
struct Segt{
int l,r,sm,tgc,tgx;
}sg[N<<3];//竟然不会爆！（开心）
inline void lzdc(int p){//区间赋值懒标记下放
if(sg[p].tgc==2)return;
sg[p<<1].tgx=sg[p<<1|1].tgx=0;
sg[p<<1].tgc=sg[p<<1|1].tgc=sg[p].tgc;
sg[p<<1].sm=(sg[p<<1].r-sg[p<<1].l+1)*sg[p].tgc;
sg[p<<1|1].sm=(sg[p<<1|1].r-sg[p<<1|1].l+1)*sg[p].tgc;
sg[p].tgc=2;
return;
}
inline void lzdx(int p){//区间异或
if(!sg[p].tgx)return;
sg[p<<1].tgx^=1;
sg[p<<1|1].tgx^=1;
sg[p<<1].sm=(sg[p<<1].r-sg[p<<1].l+1)-sg[p<<1].sm;
sg[p<<1|1].sm=(sg[p<<1|1].r-sg[p<<1|1].l+1)-sg[p<<1|1].sm;
sg[p].tgx=0;
return;
}
inline void build(int l,int r,int p){//建树
sg[p].l=l;
sg[p].r=r;
sg[p].tgc=2;
if(l==r)return;
int mid=l+((r-l)>>1);
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
return;
}
inline void chg(int ql,int qr,int p,int K){//区间修改
if(ql<=sg[p].l&&sg[p].r<=qr){
sg[p].tgc=K;
sg[p].tgx=0;
sg[p].sm=(sg[p].r-sg[p].l+1)*K;
return;
}
lzdc(p);
lzdx(p);
int mid=sg[p].l+((sg[p].r-sg[p].l)>>1);
if(ql<=mid)chg(ql,qr,p<<1,K);
if(qr>mid)chg(ql,qr,p<<1|1,K);
sg[p].sm=sg[p<<1].sm+sg[p<<1|1].sm;
return;
}
inline void dox(int ql,int qr,int p){//区间异或
if(ql<=sg[p].l&&sg[p].r<=qr){
sg[p].tgx^=1;
sg[p].sm=(sg[p].r-sg[p].l+1)-sg[p].sm;
return;
}
lzdc(p);
lzdx(p);
int mid=sg[p].l+((sg[p].r-sg[p].l)>>1);
if(ql<=mid)dox(ql,qr,p<<1);
if(qr>mid)dox(ql,qr,p<<1|1);
sg[p].sm=sg[p<<1].sm+sg[p<<1|1].sm;
return;
}
inline void solve(int p){//最后统一查询一遍
if(sg[p].sm==(sg[p].r-sg[p].l+1)){
if(sg[p].l%2){
if(ans[sg[p].l>>1]!='[')ans[sg[p].l>>1]='(';
}else{
if(ans[sg[p].l>>1]==char(0))ans[sg[p].l>>1]='[';
else ans[sg[p].l>>1]='6';
}
if(sg[p].r%2){
if(ans[(sg[p].r+1)>>1]!=']')ans[(sg[p].r+1)>>1]=')';
}else ans[(sg[p].r+1)>>1]=']';
return;
}
if(sg[p].l>=sg[p].r)return;
lzdc(p);
lzdx(p);
if(sg[p<<1].sm)solve(p<<1);
if(sg[p<<1|1].sm)solve(p<<1|1);
sg[p].sm=sg[p<<1].sm+sg[p<<1|1].sm;
return;
}//这里的东西很抱歉讲不清楚，请大家自己理解吧，谢谢啦
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
build(0,65535<<1,1);
while(cin>>op>>lb>>a>>tc>>b>>rb){
a=(a<<1)+(lb=='(');
b=(b<<1)-(rb==')');
if(op=='U')chg(a,b,1,1);
else if(op=='I'){
if(a-1>=0)chg(0,a-1,1,0);
if((b+1)<=(65535<<1))chg(b+1,65535<<1,1,0);
}else if(op=='D')chg(a,b,1,0);
else if(op=='C'){
dox(a,b,1);
if(a-1>=0)chg(0,a-1,1,0);
if((b+1)<=(65535<<1))chg(b+1,65535<<1,1,0);
}else if(op=='S')dox(a,b,1);
}
solve(1);
bool hvans=0,lst=0;
for(int i=0;i<=65535;i++){
if(ans[i]=='('||ans[i]=='['){
lst=1;
hvans=1;
cout<<ans[i]<<i<<',';
}
if(ans[i]==')'||ans[i]==']'){
if(!lst){
if(ans[i]==')')cout<<'('<<i<<',';
else cout<<'['<<i<<',';
}
lst=0;
hvans=1;
cout<<i<<ans[i]<<' ';
}
}//输出答案，写得也很差，大家看情况理解吧
if(!hvans)cout<<"empty set";
return 0;
}为什么先下放区间赋值的懒标记？因为区间赋值更改时我们已经清空了区间异或的懒标记，这时的区间异或懒标记是比区间赋值更靠后的，所以先下传区间赋值。