题意简述
维护序列, 支持以下操作:
0 l r: 将 l~r 赋为 0
1 l1 r1 l2 r2: 将 l1~r1 中的 1 替换 l2~r2 中的 0, 多余舍弃
2 l r: 询问 l~r 中最大连续 1 的长度
题解思路
珂朵莉树暴力赋值, 查询
代码
- #include <set>
- #include <iostream>
- #include <algorithm>
- #define IT set<Node>::iterator
- typedef long long ll;
- using std::set;
- int n,m,op,l0,r0,l1,r1,x,y;
- struct Node {
- int l,r;
- mutable int v;
- Node(int L,int R,ll V):l(L),r(R),v(V) {}
- bool operator<(const Node& x) const { return l<x.l; }
- };
- set<Node> s;
- inline void print() {
- for (IT it=s.begin();it!=s.end();++it) {
- std::cout<<it->l<<''<<it->r<<' '<<it->v<<'\n';
- }
- }
- inline IT split(const int& pos) {
- IT it=s.lower_bound(Node(pos,0,0));
- if (it!=s.end()&&it->l==pos) return it;
- --it; int L=it->l,R=it->r; ll V=it->v; s.erase(it);
- s.insert(Node(L,pos-1,V));
- return s.insert(Node(pos,R,V)).first;
- }
- inline void assign(const int& l,const int& r,const int& va) {
- IT itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert(Node(l,r,va));
- }
- inline void modify(const int& l0,const int& r0,const int& l1,const int& r1) {
- IT itr=split(r0+1),itl=split(l0); int sum=0;
- for (IT it=itl;it!=itr;++it) if (it->v) sum+=it->r-it->l+1;
- s.erase(itl,itr); s.insert(Node(l0,r0,0));
- if (!sum) return;
- itr=split(r1+1),itl=split(l1);
- for (IT it=itl;it!=itr;++it) if (!it->v) {
- if (sum>=it->r-it->l+1) sum-=it->r-it->l+1,it->v=1;
- else assign(it->l,it->l+sum-1,1),sum=0;
- }
- }
- inline int query(const int& l,const int& r,int res=0,int xx=0) {
- for (IT itr=split(r+1),itl=split(l);itl!=itr;++itl)
- if (itl->v) res=std::max(res,xx),xx=0;
- else xx+=itl->r-itl->l+1;
- return res=std::max(res,xx);
- }
- int main() {
- std::iOS::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
- std::cin>>n>>m; s.insert(Node(1,n,1));
- for (register int i=1;i<=m;++i) {
- std::cin>>op>>l0>>r0;
- if (op==0) assign(l0,r0,0);
- else if (op==1) std::cin>>l1>>r1,modify(l0,r0,l1,r1);
- else if (op==2) std::cout<<query(l0,r0)<<'\n';
- }
- }
来源: http://www.bubuko.com/infodetail-3157002.html