这题好弱智啊
裸的珂朵莉树
前置芝士: 珂朵莉树
窝博客里对珂朵莉树的介绍
没什么好说的自己看看吧
操作 1: 把区间内所有数推平成 0, 珂朵莉树基本操作
操作 2: 把区间内所有数推平成 1, 珂朵莉树基本操作
操作 3: 把区间内所有数取反 (异或 1),split 后扫描一遍, 值域取反
操作 4: 区间和, 珂朵莉树基本操作
操作 5: 区间最长连续的 1, 暴力扫描累加
就是这样简单
好像跑的比线段树还快??? 喵喵喵
- #pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- #define IT set<node>::iterator
- using namespace std;
- inline int read()
- {
- register int x=0,f=1;register char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- inline int Max(register int a,register int b)
- {
- return a>b?a:b;
- }
- struct node
- {
- int l,r;
- mutable bool v;
- node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
- bool operator<(const node& o) const
- {
- return l <o.l;
- }
- };
- set<node> s;
- inline IT split(register int pos)
- {
- IT it = s.lower_bound(node(pos));
- if (it != s.end() && it->l == pos)
- return it;
- --it;
- int L = it->l, R = it->r;
- bool V = it->v;
- s.erase(it);
- s.insert(node(L, pos-1, V));
- return s.insert(node(pos, R, V)).first;
- }
- inline void assign_val(register int l,register int r,register bool val)
- {
- IT itr = split(r+1),itl = split(l);
- s.erase(itl, itr);
- s.insert(node(l, r, val));
- }
- inline void rev(register int l,register int r)
- {
- IT itr = split(r+1),itl = split(l);
- for(; itl != itr; ++itl)
- itl->v ^= 1;
- }
- inline int sum(register int l,register int r)
- {
- IT itr = split(r+1),itl = split(l);
- int res = 0;
- for (; itl != itr; ++itl)
- res += itl->v ? itl->r - itl->l + 1 : 0;
- return res;
- }
- inline int count(register int l,register int r)
- {
- int res=0,temp=0;
- IT itr = split(r+1),itl = split(l);
- for(; itl != itr; ++itl)
- {
- if(itl->v == false)
- {
- res = Max(res, temp);
- temp=0;
- }
- else
- temp += itl->r - itl->l + 1;
- }
- return Max(res, temp);
- }
- int main()
- {
- int n=read(),m=read();
- for(register int i=0;i<n;++i)
- s.insert(node(i,i,read()));
- s.insert(node(n,n,0));
- while(m--)
- {
- int op=read(),a=read(),b=read();
- if(op==0)
- assign_val(a,b,0);
- else if(op==1)
- assign_val(a,b,1);
- else if(op==2)
- rev(a,b);
- else if(op==3)
- printf("%d\n",sum(a,b));
- else
- printf("%d\n",count(a,b));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2800849.html