[Poi2010]Monotonicity 2

发表于 | 分类于

题目

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

INPUT

第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

OUTPUT

一个正整数，表示L的最大值。

SAMPLE

INPUT

7 3
2 4 3 1 3 5 3
< > =

OUTPUT

6

解题报告

考试时连最最最简单的DP都没想出来，就打了个DFS- -
正解：
我们先考虑只有一种符号的情况，比如说考虑<，那么不就变成了求最长上升子序列吗。
同样的，我们扩展至三种符号：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++){
	f[i]=1;
	for(int j=1;j<=i-1;j++){
		int tmp(f[j]%k+1);
		if(op[tmp]=='='&&a[j]==a[i]&&f[j]+1>f[i])
			f[i]=f[j]+1;
		if(op[tmp]=='>'&&a[j]>a[i]&&f[j]+1>f[i])
			f[i]=f[j]+1;
		if(op[tmp]=='<'&&a[j]<a[i]&&f[j]+1>f[i])
			f[i]=f[j]+1;
	}
}

这就是最最最简单的DP，然而我们知道，这玩意是O(n²)的复杂度，显然会T，那么我们就需要优化一下了。
我们发现，转移时有O(n)的复杂度来找最大值，那么我们想，是否可以把这个过程优化呢？自然可以，我们的目的在于找到权值符合条件的最大f值，所以，我们需要一个新的东西来完成它：

权值线段树

这是一个神奇的数据结构- -，好吧，也不怎么神奇，它在这道题里是以权值为下标，存入该点最优解的一种线段树，它就可以完成这个伟大的任务啦。
我们需要3棵树（其实2棵也可以，相等的那个用数组模拟即可实现，只是我比较懒- -），每一棵树存以该符号为后面所接符号的权值的最优解（好绕啊- -），这样我们在找的时候，取出每棵树中符合权值条件的最优解，三解进行比较，选出最优以确定符号，继续转移并更新相应的线段树即可。
（我语文表达能力好弱啊）

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
inline char init(){
    char ch(getchar());
    for(;ch!='='&&ch!='>'&&ch!='<';ch=getchar());
    return ch;
}
inline int my_max(int a,int b){
    return a>b?a:b;
}
int n,k;
int a[500001],op[500001];
int tr_d[4000001],tr_x[4000001],tr_e[4000001];
int ad_d[4000001],ad_x[4000001],ad_e[4000001];
inline void pushup_d(int i){
    tr_d[i]=my_max(tr_d[i<<1],tr_d[i<<1|1]);
}
inline void pushup_x(int i){
    tr_x[i]=my_max(tr_x[i<<1],tr_x[i<<1|1]);
}
inline void pushup_e(int i){
    tr_e[i]=my_max(tr_e[i<<1],tr_e[i<<1|1]);
}
inline void pushdown_d(int i){
    if(ad_d[i]){
        ad_d[i<<1]=ad_d[i];
        ad_d[i<<1|1]=ad_d[i];
        tr_d[i<<1]=ad_d[i];
        tr_d[i<<1|1]=ad_d[i];
        tr_d[i]=ad_d[i];
        ad_d[i]=0;
    }
}
inline void pushdown_x(int i){
    if(ad_x[i]){
        ad_x[i<<1]=ad_x[i];
        ad_x[i<<1|1]=ad_x[i];
        tr_x[i<<1]=ad_x[i];
        tr_x[i<<1|1]=ad_x[i];
        tr_x[i]=ad_x[i];
        ad_x[i]=0;
    }
}
inline void pushdown_e(int i){
    if(ad_e[i]){
        ad_e[i<<1]=ad_e[i];
        ad_e[i<<1|1]=ad_e[i];
        tr_e[i<<1]=ad_e[i];
        tr_e[i<<1|1]=ad_e[i];
        tr_e[i]=ad_e[i];
        ad_e[i]=0;
    }
}
inline void update_d(int ll,int rr,int c,int l,int r,int i){
    if(ll<=l&&r<=rr){
        ad_d[i]=c;
        tr_d[i]=c;
        return;
    }
    pushdown_d(i);
    int mid((l+r)>>1);
    if(ll<=mid)
        update_d(ll,rr,c,l,mid,i<<1);
    if(rr>mid)
        update_d(ll,rr,c,mid+1,r,i<<1|1);
    pushup_d(i);
}
inline void update_x(int ll,int rr,int c,int l,int r,int i){
    if(ll<=l&&r<=rr){
        ad_x[i]=c;
        tr_x[i]=c;
        return;
    }
    pushdown_x(i);
    int mid((l+r)>>1);
    if(ll<=mid)
        update_x(ll,rr,c,l,mid,i<<1);
    if(rr>mid)
        update_x(ll,rr,c,mid+1,r,i<<1|1);
    pushup_x(i);
}
inline void update_e(int ll,int rr,int c,int l,int r,int i){
    if(ll<=l&&r<=rr){
        ad_e[i]=c;
        tr_e[i]=c;
        return;
    }
    pushdown_e(i);  
    int mid((l+r)>>1);
    if(ll<=mid)
        update_e(ll,rr,c,l,mid,i<<1);
    if(rr>mid)
        update_e(ll,rr,c,mid+1,r,i<<1|1);
    pushup_e(i);
}
inline int query_d(int ll,int rr,int l,int r,int i){
    if(ll>rr)
        return 0;
    if(ll<=l&&r<=rr)
        return tr_d[i];
    pushdown_d(i);
    int mid((l+r)>>1);
    int ret(0);
    if(ll<=mid)
        ret=my_max(ret,query_d(ll,rr,l,mid,i<<1));
    if(rr>mid)
        ret=my_max(ret,query_d(ll,rr,mid+1,r,i<<1|1));
    return ret;
}
inline int query_x(int ll,int rr,int l,int r,int i){
    if(ll>rr)
        return 0;
    if(ll<=l&&r<=rr)
        return tr_x[i];
    pushdown_x(i);  
    int mid((l+r)>>1);
    int ret(0);
    if(ll<=mid)
        ret=my_max(ret,query_x(ll,rr,l,mid,i<<1));
    if(rr>mid)
        ret=my_max(ret,query_x(ll,rr,mid+1,r,i<<1|1));
    return ret;
}
inline int query_e(int ll,int rr,int l,int r,int i){
    if(ll>rr)
        return 0;
    if(ll<=l&&r<=rr)
        return tr_e[i];
    pushdown_e(i);
    int mid((l+r)>>1);
    int ret(0);
    if(ll<=mid)
        ret=my_max(ret,query_e(ll,rr,l,mid,i<<1));
    if(rr>mid)
        ret=my_max(ret,query_e(ll,rr,mid+1,r,i<<1|1));
    return ret;
}
int f[500001];
int mx(0);
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),mx=my_max(mx,a[i]);
    for(int i=1;i<=k;i++){
        char ch(init());
        if(ch=='>')
            op[i]=1;
        if(ch=='<')
            op[i]=2;
        if(ch=='=')
            op[i]=3;
    }
    f[1]=1;
    if(op[1]==1)
        update_d(a[1],a[1],f[1],1,mx,1);
    if(op[1]==2)
        update_x(a[1],a[1],f[1],1,mx,1);
    if(op[1]==3)
        update_e(a[1],a[1],f[1],1,mx,1);
    for(int i=2;i<=n;i++){
        int now(a[i]);
        int ans_d(query_d(now+1,mx,1,mx,1));
        int ans_x(query_x(1,now-1,1,mx,1));
        int ans_e(query_e(now,now,1,mx,1));
        int ans(my_max(my_max(ans_d,ans_x),ans_e));
        f[i]=ans+1;
        int o(op[ans%k+1]);//cout<<i<<' '<<f[i]<<' '<<o<<endl;
        if(o==1)
            update_d(now,now,f[i],1,mx,1);
        if(o==2)
            update_x(now,now,f[i],1,mx,1);
        if(o==3)
            update_e(now,now,f[i],1,mx,1);
    }
    int mxx(0);
    for(int i=1;i<=n;i++)
        mxx=my_max(mxx,f[i]);
    printf("%d",mxx);
}

写的极其丑- -，毕竟三颗线段树乱搞
凑合着看吧，其实理解了之后，一颗线段树，加不同的域，对传的参数进行处理，就可以达到三颗线段树的效果