浙江建设职业技术学院门户网站,wordpress怎么作模版,大连企业网站建站,深圳罗湖区住房和建设局网站解析
预处理
用pre[i]表示以i结尾的最长完美序列起始点#xff0c;用last[i]表示数字i最后出现的位置 那么可以得到递推式#xff1a;
pre[i]max(pre[i-1],last[x[i]]1);也就是说这个pre要么是受前一位一样的限制#xff0c;要么是受自己的限制 用f[i]表示以i结尾的最长完…
解析
预处理
用pre[i]表示以i结尾的最长完美序列起始点用last[i]表示数字i最后出现的位置 那么可以得到递推式
pre[i]max(pre[i-1],last[x[i]]1);也就是说这个pre要么是受前一位一样的限制要么是受自己的限制 用f[i]表示以i结尾的最长完美序列长度那么显然
f[i]i-pre[i]1;以上可以用On完成预处理
询问
接下来对于每次询问区间 [l,r] 中的每一位只有两种可能 1.pre在l左侧或l上 2.pre在l右侧 根据之前的递推式pre显然单调不减。 因此这两种情况的分布具有单调性,我们就可以二分找出一个结点mid使左侧及本身的pre均l称为A右侧pre均l称为B A对于A的每一个元素其在区间内可以达到的长度应该为i-l1;那么显然让iA中最大的值——mid时取到最大值 B对与B中的每一个元素以其结尾的最大长度就是f[i]因此B的最优就是f在[now1,r]中的最大值用st表维护即可 A和B各自的最优取max就是答案 单次询问时间复杂度Ologn
代码
#include cstdio
#include cstring
#include cmath
#include algorithm
#include iostream
#include string
#include queue
#include string
#includemap
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
const int N2e5100;
const int M2e6100;
int n,m,mod,ask;
int a,b,c;
int x[N],pre[N],last[M],f[N];
int dp[N][30],q[N];
int maxx(int a,int b){int kq[(b-a)1];int ansmax(dp[a][k],dp[b-(1k)1][k]);return ans;
}
void Dp(){int o0;for(int i1;in;i){if(1oi) o;q[i]o-1;}for(int i1;in;i) dp[i][0]f[i];for(int k1;kq[n];k){for(int i1;i(1k)-1n;i) dp[i][k]max(dp[i][k-1],dp[i(1(k-1))][k-1]);}
}
int find(int l,int r){int stl,edr;while(sted){int mid(sted1)1;if(pre[mid]l) stmid;else edmid-1;}return st;
}
int query(int l,int r){int nowfind(l,r);int ansnow-l1;
// int ans0;
// for(int il;ir;i){
// if(pre[i]l) ansmax(ans,i-l1);
// else ansmax(ans,f[i]);
// }//ansmax(ans,maxx(now1,r));
// for(int inow1;ir;i) ansmax(ans,f[i]);ansmax(ans,maxx(now1,r));return ans;
}
void read(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,x[i]);
}
void solve(){for(int i1;in;i){pre[i]max(pre[i-1],last[x[i]]1);last[x[i]]i;f[i]i-pre[i]1;
// printf(%d ,pre[i]);}
// printf(\n);Dp();
}
void putout(){for(int i1;im;i){scanf(%d%d,a,b);a;b;if(pre[b]a){printf(%d\n,b-a1);continue;}printf(%d\n,query(a,b));}
}
int main(){read();solve();putout();return 0;
}
/*
9 15
1 2 3 4 5 6 7 8 9
*/
疑问
仔细看代码的童鞋会发现我的数组都开了2e6但除了last之外应该开到2e5n的范围就够了 但一开始开2e5wa掉了。。。 期待看破其中玄机的dl评论区指点迷津awa 谢谢
