首页 > 其他 > 详细

[SCOI2010]序列操作

时间:2018-08-19 22:33:25      阅读:202      评论:0      收藏:0      [点我收藏+]

嘟嘟嘟

 

这一看都知道,肯定是线段树,只不过这个稍微有些复杂……

首先对于操作0和1都是很好办的,比较简单的区间修改。然后查询区间多少个1,就是区间和,也好办。

至于查询连续个1,做过酒店的都知道怎么办,维护一个imax[now](imax是interval‘s max,不是电影……):区间连续的1是多少个,lmax[now]:从now区间的左端点开始有多少个连续的1,rmax[now]从右端点开始有多少连续个1,这样区间合并的时候就是imax[now] = max(imax[now << 1], imax[now << 1 | 1], rmax[now << 1] + lmax[now << 1 | 1]).

查询酒店那道题没讲。对于要找的区间[L, R],如果各有一部分在当前区间的左右儿子中,那么分三种情况:1.在左儿子中,那么递归下去。1.在右儿子中,同样递归下去。3.最优解可能一部分在左儿子中,一部分在右儿子中,然而不能直接返回 t[now << 1].rmax +t[now << 1 |1].lmax,因为还有当前要找的区间的限制,因此是min(t[now << 1].rmax1, mid - L + 1) + min(t[now << 1| 1].lmax1, R - mid - 1 + 1)。然后这三种情况取max返回。

 

最后有解决的是区间反转问题,也是开一个标记(我就叫lzy_re了),他的优先级是比区间修改的优先级低的,因为若果一个区间都改成了0 / 1,那么这个区间之前的反转就没有用了,所以pushdown的时候,先把lazy往下传,再把lzy_re往下传。

这样的话要维护区间最长的1和0了,这样反转的时候只用把1和0维护的信息交换即可。

一个技巧就是在pushup的时候,可以重定义 ‘+‘ 号,这样用结构体的时候在结构体里面写就行,然后外面直接写一个 t[now] = t[now << 1] + t[now << 1 | 1] 就行了。

具体的细节看代码

 

技术分享图片
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<stack>
  8 #include<queue>
  9 #include<vector>
 10 #include<cctype>
 11 using namespace std;
 12 #define enter puts("")
 13 #define space putchar(‘ ‘)
 14 #define Mem(a) memset(a, 0, sizeof(a))
 15 typedef long long ll;
 16 typedef double db;
 17 const int INF = 0x3f3f3f3f;
 18 const db eps = 1e-8;
 19 const int maxn = 1e5 + 5;
 20 inline ll read()
 21 {
 22     ll ans = 0;
 23     char ch = getchar(), last =  ;
 24     while(!isdigit(ch)) {last = ch; ch = getchar();}
 25     while(isdigit(ch)) {ans = ans * 10 + ch - 0; ch = getchar();}
 26     if(last == -) ans = -ans;
 27     return ans;
 28 }
 29 inline void write(ll x)
 30 {
 31     if(x < 0) putchar(-), x = -x;
 32     if(x >= 10) write(x / 10);
 33     putchar(x % 10 + 0);
 34 }
 35 
 36 int n, m;
 37 
 38 struct Tree
 39 {
 40     int l, r, sum, lzy, lzy_re;
 41     int lmax0, rmax0, imax0, lmax1, rmax1, imax1;
 42     Tree operator + (const Tree& other)const
 43     {
 44         Tree ret;
 45         ret.l = l; ret.r = other.r;        //这个别忘了 
 46         ret.sum = sum + other.sum;
 47         ret.lzy = -1; ret.lzy_re = 0;    //因为pushup操作在pushdown之后,所以此时所有标记已清空 
 48         ret.lmax0 = lmax0;
 49         if(lmax0 == r - l + 1) ret.lmax0 += other.lmax0;    //以下是维护区间最长的0和1,思路详见酒店那道题 
 50         ret.rmax0 = other.rmax0;
 51         if(other.rmax0 == other.r - other.l + 1) ret.rmax0 += rmax0;
 52         ret.imax0 = max(rmax0 + other.lmax0, max(imax0, other.imax0));
 53         ret.lmax1 = lmax1;
 54         if(lmax1 == r - l + 1) ret.lmax1 += other.lmax1;
 55         ret.rmax1 = other.rmax1;
 56         if(other.rmax1 == other.r - other.l + 1) ret.rmax1 += rmax1;
 57         ret.imax1 = max(rmax1 + other.lmax1, max(imax1, other.imax1));
 58         return ret;        
 59     }
 60 }t[maxn << 2];
 61 
 62 void build(int L, int R, int now)
 63 {
 64     t[now].l = L; t[now].r = R;
 65     if(L == R)
 66     {
 67         t[now].sum = read(); t[now].lzy = -1; t[now].lzy_re = 0;        //lzy初值最好设成-1,因为每一个数是0 / 1,初值为0不好判断 
 68         t[now].lmax0 = t[now].rmax0 = t[now].imax0 = t[now].sum ^ 1;     
 69         t[now].lmax1 = t[now].rmax1 = t[now].imax1 = t[now].sum;
 70         return;
 71     }
 72     int mid = (L + R) >> 1;
 73     build(L, mid, now << 1);
 74     build(mid + 1, R, now << 1 | 1);
 75     t[now] = t[now << 1] + t[now << 1 | 1];
 76 }
 77 void pushdown(int now)
 78 {
 79     if(t[now].lzy != -1)    //先传区间修改 
 80     {
 81         t[now << 1].sum = (t[now << 1].r - t[now << 1].l + 1) * t[now].lzy;    //左区间 
 82         t[now << 1].lzy = t[now].lzy;
 83         t[now << 1].lzy_re = 0;        //他的左右儿子区间的反转标记得清零 
 84         t[now << 1].lmax0 = t[now << 1].rmax0 = t[now << 1].imax0 = t[now << 1].lzy ? 0 : t[now << 1].r - t[now << 1].l + 1;
 85                                     //刚开始写成了 = t[now].sum * (t[now].lzy ^ 1),显然不对呀…… 
 86         t[now << 1].lmax1 = t[now << 1].rmax1 = t[now << 1].imax1 = t[now << 1].sum;        
 87         
 88         t[now << 1 | 1].sum = (t[now << 1 | 1].r - t[now << 1 | 1].l + 1) * t[now].lzy;    //右区间 
 89         t[now << 1 | 1].lzy = t[now].lzy;
 90         t[now << 1 | 1].lzy_re = 0;
 91         t[now << 1 | 1].lmax0 = t[now << 1 | 1].rmax0 = t[now << 1 | 1].imax0 = t[now << 1 | 1].lzy ? 0 : t[now << 1 | 1].r - t[now << 1 | 1].l + 1;
 92         t[now << 1 | 1].lmax1 = t[now << 1 | 1].rmax1 = t[now << 1 | 1].imax1 = t[now << 1 | 1].sum;
 93         t[now].lzy = -1;
 94     }
 95     if(t[now].lzy_re)
 96     {
 97         t[now << 1].sum = t[now << 1].r - t[now << 1].l + 1 - t[now << 1].sum;
 98         t[now << 1].lzy_re ^= 1;        
 99         //注意一定要 ^ 1,而不是直接 = 1,因为很显然的是反转两次就还是原状。这就体现了lzy_re初值为0而不是-1的好处 
100         swap(t[now << 1].lmax0, t[now << 1].lmax1); swap(t[now << 1].rmax0, t[now << 1].rmax1); 
101         swap(t[now << 1].imax0, t[now << 1].imax1);        //直接把维护最长的0和1这俩的信息交换就行 
102         
103         t[now << 1 | 1].sum = t[now << 1 | 1].r - t[now << 1 | 1].l + 1 - t[now << 1 | 1].sum;
104         t[now << 1  | 1].lzy_re ^= 1;        //注意不是直接等于1 
105         swap(t[now << 1 | 1].lmax0, t[now << 1 | 1].lmax1); swap(t[now << 1 | 1].rmax0, t[now << 1 | 1].rmax1); 
106         swap(t[now << 1 | 1].imax0, t[now << 1 | 1].imax1);
107         t[now].lzy_re = 0;
108     }
109 }
110 void update_all(int L, int R, int now, bool d)
111 {
112     if(t[now].l == L && t[now].r == R)
113     {
114         t[now].sum = (R - L + 1) * d;
115         t[now].lzy = d;
116         t[now].lzy_re = 0;
117         t[now].lmax0 = t[now].rmax0 = t[now].imax0 = d ? 0 : R - L + 1;
118         t[now].lmax1 = t[now].rmax1 = t[now].imax1 = t[now].sum;
119         return;
120     }
121     pushdown(now);
122     int mid = (t[now].l + t[now].r) >> 1;
123     if(R <= mid) update_all(L, R, now << 1, d);
124     else if(L > mid) update_all(L, R, now << 1 | 1, d);
125     else update_all(L, mid, now << 1, d), update_all(mid + 1, R, now << 1 | 1, d);
126     t[now] = t[now << 1] + t[now << 1 | 1];
127 }
128 void update_re(int L, int R, int now)    
129 {
130     if(t[now].l == L && t[now].r == R)
131     {
132         t[now].sum = R - L + 1 - t[now].sum;
133         t[now].lzy_re ^= 1;
134         swap(t[now].lmax0, t[now].lmax1); swap(t[now].rmax0, t[now].rmax1); 
135         swap(t[now].imax0, t[now].imax1);
136         return;
137     }                
138     pushdown(now);
139     int mid = (t[now].l + t[now].r) >> 1;
140     if(R <= mid) update_re(L, R, now << 1);
141     else if(L > mid) update_re(L, R, now << 1 | 1);
142     else update_re(L, mid, now << 1), update_re(mid + 1, R, now << 1 | 1);
143     t[now] = t[now << 1] + t[now << 1 | 1];
144 }
145 int query_sum(int L, int R, int now)
146 {
147     if(t[now].l == L && t[now].r == R) return t[now].sum;
148     pushdown(now);
149     int mid = (t[now].l + t[now].r) >> 1;
150     if(R <= mid) return query_sum(L, R, now << 1);
151     else if(L > mid) return query_sum(L, R, now << 1 | 1);
152     else return query_sum(L, mid, now << 1) + query_sum(mid + 1, R, now << 1 | 1);    
153 }
154 int query_max(int L, int R, int now)
155 {
156     if(t[now].l == L && t[now].r == R) return t[now].imax1;
157     pushdown(now);
158     int mid = (t[now].l + t[now].r) >> 1;
159     if(R <= mid) return query_max(L, R, now << 1);
160     else if(L > mid) return query_max(L, R, now << 1 | 1);
161     else            //最大值分三种情况 
162     {
163         int ret1 = max(query_max(L, mid, now << 1), query_max(mid + 1, R, now << 1 | 1));    //分别在左右区间 
164         int ret2 = min(t[now << 1].rmax1, mid - L + 1) + min(t[now << 1| 1].lmax1, R - mid - 1 + 1);    //在两区间都有
165         //刚开始写成 min(t[now << 1].rmax1, L) + min(t[now << 1| 1].lmax1, R),因为比较的是长度,而L, R是端点,自然就不对了 
166         return max(ret1, ret2);
167     }
168 }
169 
170 int main()
171 {
172     n = read(); m = read();
173     build(0, n - 1, 1);
174     for(int i = 1; i <= m; ++i)
175     {
176         int d = read(), L = read(), R = read();
177         if(d == 0) update_all(L, R, 1, 0);
178         else if(d == 1) update_all(L, R, 1, 1);
179         else if(d == 2) update_re(L, R, 1);
180         else if(d == 3) write(query_sum(L, R, 1)), enter;
181         else write(query_max(L, R, 1)), enter;
182     }
183     return 0;
184 }
View Code

 

[SCOI2010]序列操作

原文:https://www.cnblogs.com/mrclr/p/9502905.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!