算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
A:
签名题 ... 任何字符串匹配算法都可以 ... 略
B:
...
C:
...
D:
...
E:
...
F:
给一个'0'-'9'的串,要求支持两种操作
1: 查询整段区间的最长不下降子串
2: 让某个区间[l,r]的所有值Si = 9-Si
可以当线段树模板题
维护最长不下降子串,需要维护下面几个值以满足“区间的和”的性质
最长不下降和最长不上升子串简称为"LIS"和"LDS",虽然不准确,但是你们忍了吧
(1) 这个区间的全局LIS长度与LDS (mx数组)
(2) 这个区间包含最左端点的LIS和LDS长,包含最右端点的LIS和LDS长 (seg数组,分别对应什么意思自己看吧 )
(3) 这个区间是否是完全不下降(上升)的 (full数组)
(4) 这个区间的最左端点和最右端点的值 (side数组)
  再来一个数组记录区间是否被修改过...
上面的这些域完全可以支持操作2(见upt函数)和维护LIS了(见sumup函数)....
询问直接返回mx[1][0]就可以了
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cassert>
 5 using namespace std;
 6 const int N = 100005;
 7 template <typename T> inline void chkmax(T &a,T b){if(a<b) a=b;}
 8 int seg[N<<2][2][2], side[N<<2][2], mx[N<<2][2], full[N<<2][2],chg[N<<2];
 9 int upt(int pos){
10     for(int i=0;i<2;i++) side[pos][i] = 9- side[pos][i];
11     swap(mx[pos][0],mx[pos][1]);
12     swap(full[pos][0],full[pos][1]);
13     for(int i=0;i<2;i++){
14         swap(seg[pos][0][i],seg[pos][1][i]);
15     }
16 }
17 void pushdown(int pos,int L,int R){
18     if(chg[pos]){
19         upt(pos);
20         chg[pos] = 0;
21         if(L==R) return ;
22         chg[pos<<1] ^=1;
23         chg[pos<<1|1]^=1;
24     }
25 }
26 void sumup(int pos,int L,int R){
27     int mid = L+R >>1;
28     pushdown(pos<<1 , L, mid);
29     pushdown(pos<<1|1,mid+1,R);
30     side[pos][0] = side[pos<<1][0];
31     side[pos][1] = side[pos<<1|1][1];
32     full[pos][0] = full[pos<<1][0] && full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0];
33     full[pos][1] = full[pos<<1][1] && full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0];
34     seg[pos][0][0] = seg[pos<<1][0][0] + (full[pos<<1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1|1][0][0] : 0);
35     seg[pos][1][0] = seg[pos<<1][1][0] + (full[pos<<1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1|1][1][0] : 0);
36     seg[pos][0][1] = seg[pos<<1|1][0][1] + (full[pos<<1|1][0] && side[pos<<1][1] <= side[pos<<1|1][0] ? seg[pos<<1][0][1] : 0);
37     seg[pos][1][1] = seg[pos<<1|1][1][1] + (full[pos<<1|1][1] && side[pos<<1][1] >= side[pos<<1|1][0] ? seg[pos<<1][1][1] : 0);
38 //    cout<<seg[pos][0][1]<<" "<<seg[pos<<1][0][1]<<" "<<seg[pos<<1|1][0][1]<<" "<<full[pos<<1|1]
39     for(int i=0;i<2;i++){
40         mx[pos][i] = max(seg[pos][i][0],seg[pos][i][1]);
41         chkmax(mx[pos][i], max(mx[pos<<1][i] , mx[pos<<1|1][i]) );
42         if( i ? side[pos<<1][1] >= side[pos<<1|1][0]:side[pos<<1][1] <= side[pos<<1|1][0])
43         chkmax(mx[pos][i], seg[pos<<1][i][1] + seg[pos<<1|1][i][0]);
44     }
45 }
46 char num[N];
47 int last;
48 void update(int l,int r,int pos,int L,int R,int flag){
49     if(l<=L && r>=R){
50         if(flag){
51             chg[pos] ^=1;
52         }
53         else {
54             side[pos][0] = side[pos][1] = num[last++] - '0';
55             mx[pos][0] = mx[pos][1] = full[pos][0] = full[pos][1] = 1;
56             for(int i=0;i<2;i++) for(int j=0;j<2;j++) seg[pos][i][j] =1;
57         }
58         return ;
59     }
60     pushdown(pos,L,R);
61     int mid = L+ R >>1;
62     if(l<=mid) update(l,r,pos<<1, L, mid, flag);
63     if(r > mid)update(l,r,pos<<1|1,mid+1,R, flag);
64     sumup(pos,L,R);
65 //    cout<<L<<" "<<R<<" "<<seg[pos][0][1]<<" "<<mx[pos][0]<<endl;
66 }
67 int main(){
68     int t;
69     scanf("%d",&t);
70     while(t--){
71         int n,m;last = 0;
72         scanf("%d%d",&n,&m);
73         scanf("%s",num);
74         memset(chg,0,sizeof(chg));
75         for(int i=0;i<n;i++){
76             update(i,i,1,0,n-1,0);
77         }
78         assert(last==n);
79         char cmd[10];
80         while(m--){
81             scanf("%s",cmd);
82             if(cmd[0]=='q'){
83                 pushdown(1,0,n-1);
84                 printf("%d\n",mx[1][0]);
85             }
86             else {
87                 int l,r;
88                 scanf("%d%d",&l,&r);
89                 l--;r--;
90                 update(l,r,1,0,n-1,1);
91             }
92         }
93         puts("");
94     }
95     return 0;
96 }
97 
G:
...
H:
...
I:
...
J:
...
posted on 2012-05-30 10:33 西月弦 阅读(316) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

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