首页 > 代码库 > BZOJ 1858 SCOI 2010 序列操作
BZOJ 1858 SCOI 2010 序列操作
题目大意:维护一种01数据结构,它可以:
1.把一段区间变成0。
2.把一段区间变成1。
3.把一段区间取反。
4.查询一段区间内1的个数。
5.查询一段区间内连续的1的个数。
思路:一眼看去Splay和线段树都可以,看起来好像Splay维护起来好弄一点,就没怎么想写了Splay。写完之后才发现Splay维护的时候边界值根本没法弄(可能是我写的麻烦),就又重写线段树。啊啊啊啊现在整个人都发要疯了。。
其实线段树和Splay的思想是一样的,需要维护一下几个东西:
1.一段区间内,左边开始连续0的个数;
2.一段区间内,左边开始连续1的个数;
3.一段区间内,右边开始连续0的个数;
4.一段区间内,右边开水连续1的个数;
5.一段区间内,1的个数。
6.一段区间内,连续的1的个数。
7.一段区间内,连续的0的个数。
注意一个事情,在询问的时候,由于要返回这个区间的所有数据,要新建结构体来存储,然后再返回。但是这个题的询问十分的多,这样做会MLE。所以在全局开一个返回变量,之后不断对这个变量进行操作,返回这个变量就不会MLE了。
然后就是繁琐的合并区间的讨论了。注意两个标记都有的时候要先下传翻转标记。详情见CODE。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define LEFT (pos << 1) #define RIGHT (pos << 1|1) using namespace std; struct Complex{ int total; int l_0,l_1,r_0,r_1; int cnt,linked_0,linked_1; bool reverse,change; int change_into; }tree[MAX << 2],*re = new Complex(); int cnt,asks; int src[MAX]; inline void Combine(Complex &l,Complex &r,Complex *re); inline void PushDown(int l,int r,int pos); void BuildTree(int l,int r,int pos); void Modify(int l,int r,int x,int y,int pos,int c); void Reverse(int l,int r,int x,int y,int pos); Complex AskLinked(int l,int r,int x,int y,int pos); int main() { cin >> cnt >> asks; for(int i = 1;i <= cnt; ++i) scanf("%d",&src[i]); BuildTree(1,cnt,1); for(int flag,x,y,i = 1;i <= asks; ++i) { scanf("%d%d%d",&flag,&x,&y); x++,y++; if(!flag || flag == 1) Modify(1,cnt,x,y,1,flag); else if(flag == 2) Reverse(1,cnt,x,y,1); else if(flag == 3) printf("%d\n",AskLinked(1,cnt,x,y,1).cnt); else printf("%d\n",AskLinked(1,cnt,x,y,1).linked_1); } return 0; } inline void Combine(Complex &l,Complex &r,Complex *re) { re->total = l.total + r.total; re->cnt = l.cnt + r.cnt; re->l_0 = l.l_0; re->l_1 = l.l_1; re->r_0 = r.r_0; re->r_1 = r.r_1; if(l.l_0 == l.total) re->l_0 = l.l_0 + r.l_0; if(l.l_1 == l.total) re->l_1 = l.l_1 + r.l_1; if(r.r_0 == r.total) re->r_0 = r.r_0 + l.r_0; if(r.r_1 == r.total) re->r_1 = r.r_1 + l.r_1; re->linked_1 = max(l.linked_1,r.linked_1); re->linked_1 = max(re->linked_1,l.r_1 + r.l_1); re->linked_0 = max(l.linked_0,r.linked_0); re->linked_0 = max(re->linked_0,l.r_0 + r.l_0); } inline void PushDown(int l,int r,int pos) { int mid = (l + r) >> 1; if(tree[pos].change) { Modify(l,mid,l,mid,LEFT,tree[pos].change_into); Modify(mid + 1,r,mid + 1,r,RIGHT,tree[pos].change_into); tree[pos].change = false; } if(tree[pos].reverse) { Reverse(l,mid,l,mid,LEFT); Reverse(mid + 1,r,mid + 1,r,RIGHT); tree[pos].reverse = false; } } void BuildTree(int l,int r,int pos) { if(l == r) { if(src[l]) tree[pos].l_1 = tree[pos].r_1 = tree[pos].cnt = tree[pos].linked_1 = 1; else tree[pos].l_0 = tree[pos].r_0 = tree[pos].linked_0 = 1; tree[pos].total = 1; return ; } int mid = (l + r) >> 1; BuildTree(l,mid,LEFT); BuildTree(mid + 1,r,RIGHT); Combine(tree[LEFT],tree[RIGHT],&tree[pos]); } void Modify(int l,int r,int x,int y,int pos,int c) { if(l == x && y == r) { Complex *now = &tree[pos]; now->reverse = false; tree[pos].change = true; tree[pos].change_into = c; if(!c) { now->l_0 = now->r_0 = now->linked_0 = now->total; now->l_1 = now->r_1 = now->linked_1 = now->cnt = 0; } else { now->l_1 = now->r_1 = now->linked_1 = now->cnt = now->total; now->l_0 = now->r_0 = now->linked_0 = 0; } return ; } PushDown(l,r,pos); int mid = (l + r) >> 1; if(y <= mid) Modify(l,mid,x,y,LEFT,c); else if(x > mid) Modify(mid + 1,r,x,y,RIGHT,c); else { Modify(l,mid,x,mid,LEFT,c); Modify(mid + 1,r,mid + 1,y,RIGHT,c); } Combine(tree[LEFT],tree[RIGHT],&tree[pos]); } void Reverse(int l,int r,int x,int y,int pos) { if(l == x && r == y) { tree[pos].reverse ^= 1; swap(tree[pos].l_0,tree[pos].l_1); swap(tree[pos].r_0,tree[pos].r_1); swap(tree[pos].linked_0,tree[pos].linked_1); tree[pos].cnt = tree[pos].total - tree[pos].cnt; return ; } PushDown(l,r,pos); int mid = (l + r) >> 1; if(y <= mid) Reverse(l,mid,x,y,LEFT); else if(x > mid) Reverse(mid + 1,r,x,y,RIGHT); else { Reverse(l,mid,x,mid,LEFT); Reverse(mid + 1,r,mid + 1,y,RIGHT); } Combine(tree[LEFT],tree[RIGHT],&tree[pos]); } Complex AskLinked(int l,int r,int x,int y,int pos) { if(l == x && r == y) return tree[pos]; PushDown(l,r,pos); int mid = (l + r) >> 1; if(y <= mid) return AskLinked(l,mid,x,y,LEFT); if(x > mid) return AskLinked(mid + 1,r,x,y,RIGHT); Complex left = AskLinked(l,mid,x,mid,LEFT); Complex right = AskLinked(mid + 1,r,mid + 1,y,RIGHT); Combine(left,right,re); return *re; }
BZOJ 1858 SCOI 2010 序列操作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。