这个题我xio到了好多东西QAQ
线段树 染色
可以看这个大佬的题解 瓜打了一会儿 发现自己完全不会QAQ 然后学到了线段树染色这一方法
col数组表示这段区间的颜色是否相同 0为不同 1为相同
del记录这种颜色是否被删掉 然后在后面的操作中搞它！
tag记录的区间颜色
QAQ发现我基础真的不牢 啥都没搞清楚：下传操作的进行，是因为当前区间不完全在修改区间范围内((否则就直接changechange并且returnreturn了)
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std; #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) #define lson o<<1 #define rson o<<1|1 #define ll long long #define rg register const int N=200000+5,M=10000+5,inf=0x3f3f3f3f,P=99999997; int n,cnt=0,tot=0,era,s=inf,t=0; int sum[N<<1],tag[N<<1],col[N<<1],del[N<<1]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } struct node{ char a[3]; int x,y; }ask[N]; void pushdown(int o,int l,int r){ col[o]=0;//下传时 这个区间显然不同色 if(!tag[o]) return; else tag[lson]=tag[rson]=tag[o],tag[o]=0; } void change(int o,int x,int y,int k){ if(col[o]==1){//为同一个颜色 if(!del[tag[o]]&&tag[o]) --cnt,++era; //该种颜色未被删掉 del[tag[o]]=1,tag[o]=k;return;//记录为删掉 并改变颜色 } int mid=(x+y)>>1; change(lson,x,mid,k),change(rson,mid+1,y,k); tag[o]=k,col[o]=1;//覆盖 } void buildtree(int o,int l,int r){ col[o]=1;//初始都为一个未被覆盖的颜色 if(l<r){ int mid=(l+r)>>1; buildtree(lson,l,mid),buildtree(rson,mid+1,r); } } void update(int o,int l,int r,int x,int y,int k){ if(r<x||l>y) return; if(x<=l&&r<=y){ change(o,x,y,k);return; } pushdown(o,l,r);//进行下传操作 因为当前区间不完全在修改区间内 int mid=(l+r)>>1; update(lson,l,mid,x,y,k),update(rson,mid+1,r,x,y,k); } int main(){ freopen("in.txt","r",stdin); rd(n); for(int i=1,x,y;i<=n;++i){ scanf("%s",ask[i].a); if(ask[i].a[0]=='A') rd(x),rd(y),ask[i].x=x,ask[i].y=y,s=Min(s,x),t=Max(t,y); } buildtree(1,s,t); for(int i=1;i<=n;++i) if(ask[i].a[0]=='A'){ ++cnt,era=0; update(1,s,t,ask[i].x,ask[i].y,++tot); printf("%d ",era); }else printf("%d ",cnt); return 0; }
STL set
洛谷上一个大佬的做法
用一个结构体来储存预约的方案 我们知道set里不存在相同的key 可以通过s.find()来寻找
通过结构体重载运算符 重载为：bool operator <(const book &b)const{return r<b.l;}
这样a<b即为a完全在b左边 b<a即为a完全在b右边 a==b即为a和b有相交的区间
再来存一下set的用法
begin() 返回set容器的第一个元素
end() 返回set容器的最后一个元素
clear() 删除set容器中的所有的元素
empty() 判断set容器是否为空
max_size() 返回set容器可能包含的元素最大个数
size() 返回当前set容器中的元素个数
rbegin 返回的值和end()相同
rend() 返回的值和rbegin()相同
erase(iterator) 删除定位器iterator指向的值
erase(first,second) 删除定位器first和second之间的值
erase(key_value) 删除键值key_value的值
find() 返回给定值值得定位器，如果没找到则返回end()。
set<int>::iterator iter;
#include<bits/stdc++.h> using namespace std; #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) #define ll long long #define rg registerint n; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } struct book{ int l,r; bool operator <(const book &b)const{return r<b.l;} }; set<book>s; int main(){ freopen("in.txt","r",stdin); rd(n); for(int i=1;i<=n;++i){ char op[2]; scanf("%s",op); if(op[0]=='A'){ int l,r,era=0;rd(l),rd(r); book x=(book){l,r}; set<book>::iterator iter; iter=s.find(x); while(iter!=s.end()){ ++era;s.erase(iter); iter=s.find(x); } printf("%d ",era); s.insert(x); } else printf("%d ",s.size()); } return 0; }