|
日歷
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 28 | 29 | 30 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | 18 | 19 | 20 | 21 | 22 | 23 | 24 | | 25 | 26 | 27 | 28 | 29 | 30 | 1 | | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
統計
- 隨筆 - 20
- 文章 - 1
- 評論 - 40
- 引用 - 0
導航
常用鏈接
留言簿(3)
隨筆檔案
文章檔案
搜索
最新評論
閱讀排行榜
評論排行榜
|
序列操作
【題目描述】
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];
12  void 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
|