网站建设生意怎么样,有很多长尾怎么做网站内容,做网站买虚拟主机,机票网站制作题目链接
Atcoder方向 Luogu方向
题目解法
先考虑一个性质#xff0c;选出的子串长度不会超过 2 n \sqrt {2n} 2n 考虑最劣的选法是选出长度为 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,... 的子串#xff08;如果后一个选出的串比前一个子串长度大超过1#xff0c;那么后…题目链接
Atcoder方向 Luogu方向
题目解法
先考虑一个性质选出的子串长度不会超过 2 n \sqrt {2n} 2n 考虑最劣的选法是选出长度为 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,... 的子串如果后一个选出的串比前一个子串长度大超过1那么后一个选出的子串一定可以将自己长度变为前一个子串的长度 1 1 1所以 m ( m 1 ) 2 ≥ n \frac{m(m1)}{2}\ge n 2m(m1)≥n 的最大的 m ≤ 2 n m\le \sqrt{2n} m≤2n 考虑用类似 t r i e trie trie 树的方式把长度 ≤ 2 n \le \sqrt{2n} ≤2n 的子串排序注意对于字典序相同的子串需要按照起点从大到小排序 然后从小到大在树状数组上修改及查询即可这都是常规操作 时间复杂度 O ( n n l o g n ) O(n\sqrt nlogn) O(nn logn)
#include bits/stdc.h
#define lowbit(x) x-x
using namespace std;
typedef pairint,int pii;
const int N(25200);
int n,m,MX230,rk[N],idx,tr[N];
char str[N];
pii b[N*250];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void solve(vectorint vec,int len){if(!vec.size()||lenMX) return;vectorint v0,v1;v0.clear(),v1.clear();for(int i0;ivec.size();i){if(vec[i]lenn) continue;if(str[vec[i]len]48) v0.push_back(vec[i]);else v1.push_back(vec[i]);}for(int iv0.size()-1;~i;i--) b[m]make_pair(v0[i],len);solve(v0,len1);for(int iv1.size()-1;~i;i--) b[m]make_pair(v1[i],len);solve(v1,len1);
}
int ask(int x){if(!x) return 0;int res0;for(;x;x-lowbit(x)) resmax(res,tr[x]);return res;
}
void upd(int x,int val){for(;xn;xlowbit(x)) tr[x]max(tr[x],val);
}
int main(){nread();scanf(%s,str1);vectorint vec;for(int i1;in;i) vec.push_back(i);solve(vec,0);
// for(int i1;im;i) coutb[i].first b[i].second\n;for(int i1;im;i){int task(b[i].first-1);upd(b[i].firstb[i].second,t1);}printf(%d,ask(n));return 0;
}
