2020-2021:teams:legal_string:jxm2001:contest:xiaomi_icpc_1
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:xiaomi_icpc_1 [2020/10/28 17:51] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:xiaomi_icpc_1 [2020/10/30 09:14] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| 给出长度为 $n$ 的序列 $A$，保证 $1\le a_i\le m$。对每个 $1\le i\le m$，询问保证 $1\sim i$ 的连续子序列的最小长度。 | 给出长度为 $n$ 的序列 $A$，保证 $1\le a_i\le m$。对每个 $1\le i\le m$，询问保证 $1\sim i$ 的连续子序列的最小长度。 | ||
| - | ==== 题解 ==== | + | ==== 题解1 ==== |
| 设 $R(i,l)$ 表示序列 $A$ 中以 $a_l$ 为左端点且包含 $1\sim i$ 的最短序列的右端点。 | 设 $R(i,l)$ 表示序列 $A$ 中以 $a_l$ 为左端点且包含 $1\sim i$ 的最短序列的右端点。 | ||
| 行 79: | 行 79: | ||
| return 0; | return 0; | ||
| } | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 题解2 ==== | ||
| + | |||
| + | 考虑吉司机线段树，每个结点维护未最小值的答案和总答案即可。 | ||
| + | |||
| + | 由于吉司机线段树修改时只修改最小值，而最小值的答案更新为最小值权值与最小值最右端点的差。 | ||
| + | |||
| + | 于是答案变为非最小值答案和最小值权值与最小值最右端点的差的最小值。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5,Inf1=1e9,Inf2=2e9; | ||
| + | int lef[MAXN<<2],rig[MAXN<<2],minv[MAXN<<2],secv[MAXN<<2],minp[MAXN<<2],s1[MAXN<<2],s2[MAXN<<2],lazy[MAXN<<2]; | ||
| + | void push_up(int k){ | ||
| + | s1[k]=min(s1[k<<1],s1[k<<1|1]); | ||
| + | if(minv[k<<1]==minv[k<<1|1]){ | ||
| + | minv[k]=minv[k<<1]; | ||
| + | minp[k]=minp[k<<1|1]; | ||
| + | secv[k]=min(secv[k<<1],secv[k<<1|1]); | ||
| + | s2[k]=min(s2[k<<1],s2[k<<1|1]); | ||
| + | } | ||
| + | else if(minv[k<<1]<minv[k<<1|1]){ | ||
| + | minv[k]=minv[k<<1]; | ||
| + | minp[k]=minp[k<<1]; | ||
| + | secv[k]=min(secv[k<<1],minv[k<<1|1]); | ||
| + | s2[k]=min(s2[k<<1],s1[k<<1|1]); | ||
| + | } | ||
| + | else{ | ||
| + | minv[k]=minv[k<<1|1]; | ||
| + | minp[k]=minp[k<<1|1]; | ||
| + | secv[k]=min(minv[k<<1],secv[k<<1|1]); | ||
| + | s2[k]=min(s1[k<<1],s2[k<<1|1]); | ||
| + | } | ||
| + | } | ||
| + | void push_tag(int k,int v){ | ||
| + | if(v<=minv[k])return; | ||
| + | s1[k]=min(s2[k],v-minp[k]+1); | ||
| + | minv[k]=lazy[k]=v; | ||
| + | } | ||
| + | void push_down(int k){ | ||
| + | if(lazy[k]){ | ||
| + | push_tag(k<<1,lazy[k]); | ||
| + | push_tag(k<<1|1,lazy[k]); | ||
| + | lazy[k]=0; | ||
| + | } | ||
| + | } | ||
| + | void build(int k,int L,int R){ | ||
| + | lef[k]=L,rig[k]=R,lazy[k]=0; | ||
| + | int M=L+R>>1; | ||
| + | if(L==R){ | ||
| + | minv[k]=0,minp[k]=M; | ||
| + | s1[k]=s2[k]=secv[k]=Inf2; | ||
| + | return; | ||
| + | } | ||
| + | build(k<<1,L,M); | ||
| + | build(k<<1|1,M+1,R); | ||
| + | push_up(k); | ||
| + | } | ||
| + | void update(int k,int L,int R,int v){ | ||
| + | if(minv[k]>=v)return; | ||
| + | if(L<=lef[k]&&rig[k]<=R&&secv[k]>v) | ||
| + | return push_tag(k,v); | ||
| + | push_down(k); | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=L)update(k<<1,L,R,v); | ||
| + | if(mid<R)update(k<<1|1,L,R,v); | ||
| + | push_up(k); | ||
| + | } | ||
| + | vector<int> p[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,m)p[i].push_back(0); | ||
| + | _rep(i,1,n)p[read_int()].push_back(i); | ||
| + | build(1,1,n); | ||
| + | _rep(i,1,m){ | ||
| + | _for(j,1,p[i].size()) | ||
| + | update(1,p[i][j-1]+1,p[i][j],p[i][j]); | ||
| + | if(*(--p[i].end())!=n) | ||
| + | update(1,*(--p[i].end())+1,n,Inf1); | ||
| + | space(s1[1]); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/xiaomi_icpc_1.1603878671.txt.gz · 最后更改: 2020/10/28 17:51 由 jxm2001
