Tim's Programming Space  
Tim's Programming Space
日历
<2010年4月>
日一二三四五六
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678
统计
  • 随笔 - 20
  • 文章 - 1
  • 评论 - 40
  • 引用 - 0

导航

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
SCTSC2010-序列操作

序列操作

 

【题目描述】

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：

0 a b 把[a, b]区间内的所有数全变成0

1 a b 把[a, b]区间内的所有数全变成1

2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0

3 a b 询问[a, b]区间内总共有多少个1

4 a b 询问[a, b]区间内最多有多少个连续的1

对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？

【输入】

   输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目

   第二行包括n个数，表示序列的初始状态

   接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作

【输出】

   对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

【样例输入】

   10 10

   0 0 0 1 1 0 1 0 1 1

   1 0 2

   3 0 5

   2 2 2

   4 0 4

   0 3 6

   2 3 7

   4 2 8

   1 0 5

   0 5 6

   3 3 9

【样例输出】

   5

   2

   6

   5

【数据范围】

   对于30%的数据，1<=n, m<=1000

   对于100%的数据，1<=n, m<=100000

 

 ======================================================
其实就是道裸题。。。线段树要维护区间0和1的：左边开始最长连续串，右边开始最长连续串，中间最长连续串，和。。。
考场上写了9kb。。调了N久终于还是过了。。。
回来重写写的到顺畅了，最后一个点WA了。。调试不能。。杯具。。。。
下面的代码90分。。最后一个点219行出错。。有神牛能看出来哪儿错了请告诉我！！感激不尽。。。

  1#include <iostream>
  2#define MAXN 100100
  3#define MAX(a,b) ((a) > (b) ? (a) : (b))
  4#define NOSIGN -1
  5#define ZERO 0
  6#define ONE 1
  7#define REVERSE 2
  8using namespace std;
  9
 10int n,m;
 11int a[MAXN+1];
 12void Init(){
 13     scanf("%d%d",&n,&m);
 14     for (int i = 0; i<n; i++)
 15         scanf("%d",&a[i]);
 16}
 17
 18class Node{
 19      private:
 20      public:
 21             int lt,rt,l,r,len,t;
 22             int lmax[2],rmax[2],mmax[2], sum[2];
 23             void Reverse(){
 24                  int tmp = lmax[0]; lmax[0] = lmax[1]; lmax[1] = tmp;
 25                  tmp = rmax[0], rmax[0] = rmax[1], rmax[1] = tmp;
 26                  tmp = mmax[0], mmax[0] = mmax[1], mmax[1] = tmp;
 27                  tmp = sum[0], sum[0] = sum[1], sum[1] = tmp;
 28             }
 29             void Modify(int v){
 30                  if ((t == 0 && v == 0) || (t == 1 && v == 1)) return;
 31                  if ((t == 2 && v == 2)){
 32                     Reverse();
 33                     t = -1;
 34                  }else{
 35                        if (v == 0 || v == 1){ // t == 0 || t == 1 || t == 2 || t == -1
 36                           lmax[v] = rmax[v] = mmax[v] = sum[v] = len;
 37                           lmax[!v] = rmax[!v] = mmax[!v] = sum[!v] = 0;
 38                           t = v;
 39                        }else if (v == 2){ // t == 0 || t == 1 || t == -1
 40                              Reverse();
 41                              if (t == 0 || t == 1)
 42                                 t = !t;
 43                              else
 44                                  t = 2;
 45                        }
 46                  }
 47             }
 48}node[MAXN*2+1];
 49int cntNode = 0;
 50class LST{
 51private:
 52        Node Combine(Node lc, Node rc){
 53             Node x;
 54             int v1, v2;
 55             for (int t = 1; t<=1; t++){
 56                 x.lmax[t] = MAX(lc.lmax[t], (lc.sum[t] == lc.len) ? (lc.len + rc.lmax[t]) : 0);
 57                 x.rmax[t] = MAX(rc.rmax[t], (rc.sum[t] == rc.len) ? (rc.len + lc.rmax[t]) : 0);
 58                 x.sum[t] = lc.sum[t] + rc.sum[t];
 59                 v1 = MAX(lc.mmax[t], rc.mmax[t]);
 60                 v2 = MAX(x.lmax[t], x.rmax[t]);
 61                 v1 = MAX(v1, v2);
 62                 v1 = MAX(v1, lc.rmax[t] + rc.lmax[t]);
 63                 x.mmax[t] = v1;
 64             }
 65             return x;
 66        }
 67        void Renew(Node &x){
 68             Node &lc = node[x.lt], &rc = node[x.rt];
 69             int v1, v2;
 70             for (int t = 0; t<=1; t++){
 71                 x.lmax[t] = MAX(lc.lmax[t], (lc.sum[t] == lc.len) ? (lc.len + rc.lmax[t]) : 0);
 72                 x.rmax[t] = MAX(rc.rmax[t], (rc.sum[t] == rc.len) ? (rc.len + lc.rmax[t]) : 0);
 73                 x.sum[t] = lc.sum[t] + rc.sum[t];
 74                 v1 = MAX(lc.mmax[t], rc.mmax[t]);
 75                 v2 = MAX(x.lmax[t], x.rmax[t]);
 76                 v1 = MAX(v1, v2);
 77                 v1 = MAX(v1, lc.rmax[t] + rc.lmax[t]);
 78                 x.mmax[t] = v1;
 79             }
 80        }
 81        void Down(Node &x){
 82             if (x.t == -1) return;
 83             node[x.lt].Modify(x.t), node[x.rt].Modify(x.t);
 84             x.t = -1;
 85        }
 86        void Modify(Node &x, int l, int r, int v){
 87             if (x.l >= l && x.r <= r)
 88                x.Modify(v);
 89             else{
 90                  Down(x);
 91                  int mid = (x.l + x.r) >> 1;
 92                  if (r<=mid) Modify(node[x.lt], l, r, v);
 93                  else if (l > mid) Modify(node[x.rt], l, r, v);
 94                  else Modify(node[x.lt], l, r, v), Modify(node[x.rt], l, r, v);
 95                  Renew(x);
 96             }
 97        }
 98        int AskSum(Node &x, int l, int r){
 99            if (x.l >= l && x.r <= r) return x.sum[1];
100            Down(x);
101            int mid = (x.l + x.r) >> 1;
102            if (r <= mid) return AskSum(node[x.lt], l, r);
103            if (l > mid) return AskSum(node[x.rt], l, r);
104            return AskSum(node[x.lt], l, r) + AskSum(node[x.rt], l, r);
105        }
106        Node AskContinous(Node &x, int l, int r){
107             if (x.l >= l && x.r <= r) return x;
108             Down(x);
109             int mid = (x.l + x.r) >> 1;
110             if (r <= mid) return AskContinous(node[x.lt], l, r);
111             if (l > mid) return AskContinous(node[x.rt], l, r);
112             return Combine(AskContinous(node[x.lt], l, r), AskContinous(node[x.rt], l, r));
113        }
114public:
115      void Build(int l, int r){
116           int x = ++ cntNode;
117           Node &now = node[x];
118           now.l = l, now.r = r, now.len = r - l + 1, now.t = NOSIGN;
119           if (l == r){
120              int t = a[l];
121              now.lmax[t] = now.rmax[t] = now.mmax[t] = now.sum[t] = 1;
122           }else{
123                 int mid = (l + r) >> 1;
124                 now.lt = cntNode + 1, Build(l, mid);
125                 now.rt = cntNode + 1, Build(mid + 1, r);
126                 Renew(now);
127           }
128      }
129      void Modify(int l, int r, int v){
130           Modify(node[1], l, r, v);
131      }
132      int AskSum(int l, int r){
133          return AskSum(node[1], l, r);
134      }
135      int AskContinous(int l, int r){
136          return AskContinous(node[1], l, r).mmax[1];
137      }
138};
139LST T;
140void Solve(){
141     T.Build(0, n - 1);
142     int cmd, l, r;
143     for (int i = 1; i<=m; i++){
144           scanf("%d%d%d", &cmd, &l, &r);
145           switch (cmd){
146                  case 0:
147                       T.Modify(l, r, 0); break;
148                  case 1:
149                       T.Modify(l, r, 1); break;
150                  case 2:
151                       T.Modify(l, r, 2); break;
152                  case 3:
153                       printf("%d\n",T.AskSum(l, r)); break;
154                  case 4:
155                       printf("%d\n",T.AskContinous(l, r)); break;
156           }
157     }
158}
159
160int main(){
161    freopen("operation.in", "r", stdin);
162    freopen("operation.out", "w", stdout);
163    Init();
164    Solve();
165    return 0;
166}
167
posted on 2010-04-08 10:17 TimTopCoder 阅读(397) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


 
Copyright © TimTopCoder Powered by: 博客园 模板提供：沪江博客