BZOJ 1858 「SCOI2010」序列操作 发表于 2018.12.02 | 分类于 题解 | 27 区间覆盖,区间求和,区间连续值个数…… 珂朵莉树! 骗分神器珂朵莉树,懒得写线段树就用她! 出题人很良心地没有卡珂朵莉树,估计只有发明人才会卡吧…… 代码: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596#include <cstdio>#include <set>#include <algorithm>using namespace std;const int N = 1e5;int n,m;struct node{ int l,r; mutable int val; inline bool operator<(const node &a) const { return l < a.l; }};set<node> tree;typedef set<node>::iterator IT;IT split(int x){ IT it = tree.lower_bound((node){x,0,0}); if(it != tree.end() && it->l == x) return it; --it; int l = it->l,r = it->r; int v = it->val; tree.erase(it); tree.insert((node){l,x - 1,v}); return tree.insert((node){x,r,v}).first;}inline void assign(int l,int r,int val){ IT itr = split(r + 1),itl = split(l); tree.erase(itl,itr); tree.insert((node){l,r,val});}inline void flip(int l,int r){ IT itr = split(r + 1),itl = split(l); for(;itl != itr;++itl) itl->val ^= 1;}inline int query(int l,int r){ IT itr = split(r + 1),itl = split(l); int ret = 0; for(;itl != itr;++itl) ret += itl->val * (itl->r - itl->l + 1); return ret;}inline int continuity(int l,int r){ IT itr = split(r + 1),itl = split(l); int ret = 0,cur = 0; for(;itl != itr;++itl) if(itl->val) cur += itl->r - itl->l + 1; else { ret = max(ret,cur); cur = 0; } return max(ret,cur);}int main(){ scanf("%d%d",&n,&m); int x,last,cnt = 1; scanf("%d",&last); for(register int i = 2;i <= n;++i) { scanf("%d",&x); if(x == last) ++cnt; else { tree.insert((node){i - cnt,i - 1,last}); last = x; cnt = 1; } } tree.insert((node){n - cnt + 1,n,last}); int op,a,b; while(m--) { scanf("%d%d%d",&op,&a,&b); ++a,++b; if(op == 0 || op == 1) assign(a,b,op); else if(op == 2) flip(a,b); else if(op == 3) printf("%d\n",query(a,b)); else printf("%d\n",continuity(a,b)); }} 本文作者: Alpha1022 本文链接: https://www.alpha1022.me/articles/bzoj-1858.htm 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!