bzoj 1858 序列操作

• 带有随机多个区间单值覆盖的区间操作题,可考虑用珂朵莉树解决.

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mp make_pair

#define pii pair<int,int>

inline int read()

{

	int x=0;

	bool pos=1;

	char ch=getchar();

	for(;!isdigit(ch);ch=getchar())

		if(ch=='-')

			pos=0;

	for(;isdigit(ch);ch=getchar())

		x=x*10+ch-'0';

	return pos?x:-x;

}

const int MAXN=1e5+10;

int n,m;

struct node{

	int l,r;

	mutable int val;

	bool operator < (const node &rhs) const

		{

			return l<rhs.l;

		}

	node(int L,int R,int Val):l(L),r(R),val(Val) {}

	node(int L):l(L){}

};

typedef set<node> ChthollyTree;

typedef set<node>::iterator sit;

ChthollyTree T;

sit split(int pos)//[l,pos-1],return [pos,r]

{

	sit it=T.lower_bound(node(pos));

	if(it!=T.end() && pos==it->l)

		return it;

	--it;

	int l=it->l,r=it->r,val=it->val;

	T.erase(it);

	T.insert(node(l,pos-1,val));

	return T.insert(node(pos,r,val)).first;

}

void assign(int l,int r,int v)

{

	sit it2=split(r+1),it1=split(l);

	T.erase(it1,it2);//[it1,it2)

	T.insert(node(l,r,v));

}

void inverse(int l,int r)

{

	sit it2=split(r+1),it1=split(l);

	for(sit it=it1;it!=it2;++it)

		{

			it->val^=1;

		}

}

int tot(int l,int r)

{

	sit it2=split(r+1),it1=split(l);

	int res=0;

	for(sit it=it1;it!=it2;++it)

		{

			if(it->val==1)

				{

					int L=it->l,R=it->r;

					res+=R-L+1;

				}

		}

	return res;

}

int adj(int l,int r)

{

	sit it2=split(r+1),it1=split(l);

	int res=0;

	int cur=0;

	for(sit it=it1;it!=it2;++it)

		{

			if(it->val==1)

				{

					int L=it->l,R=it->r;

					cur+=R-L+1;

					res=max(res,cur);

				}

			else

				cur=0;

		}

	return res;

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;++i)

		{

			int x=read();

			T.insert(node(i,i,x));

		}

	T.insert(node(n+1,n+1,-1));

	while(m--)

		{

			int op=read();

			int l=read(),r=read();

			++l,++r;

			if(op==0)

				assign(l,r,0);

			else if(op==1)

				assign(l,r,1);

			else if(op==2)

				inverse(l,r);

			else if(op==3)

				printf("%d\n",tot(l,r));

			else if(op==4)

				printf("%d\n",adj(l,r));

		}

	return 0;

}