网站开发答辩开发网站可用性监控

网站开发答辩,开发网站可用性监控,最新旅游热点,中关村在线手机频道目录*引言*题目-HH的项链离线-树状数组解法代码实现离线-线段树解法代码实现离线-莫队算法莫队优化示例代码在线-主席树(持久化线段树)代码实现引言 本问题将使用如下数据结构 数据结构时间复杂度实现难度树状数组(Fenwick-Tree)O(mlog⁡n)O(m \log n)O(mlogn)⭐ (简单)线段树…目录*引言*题目-HH的项链离线-树状数组解法代码实现离线-线段树解法代码实现离线-莫队算法莫队优化示例代码在线-主席树(持久化线段树)代码实现引言本问题将使用如下数据结构数据结构时间复杂度实现难度树状数组(Fenwick-Tree)O ( m log ⁡ n ) O(m \log n)O(mlogn)⭐ (简单)线段树(Segment-Tree)O ( m log ⁡ n ) O(m \log n)O(mlogn)⭐⭐ (中等)莫队(Mo)O ( n n ) O(n \sqrt n)O(nn​)⭐⭐ (中等)主席树(可持久化线段树)O ( ( n m ) log ⁡ n ) O((n m)\log n)O((nm)logn)⭐⭐⭐ (困难)题目-HH的项链离线-树状数组解法树状数组维护当前数组出现的位置信息, 具体的来说为了保证时间复杂度, 要求指针r rr一直单调对于当前遍历到的数字w ww, 如果出现过那么将上一次出现的位置− 1 -1−1然后将当前位置记录l a s t i j last_i jlasti​j然后j jj枚举下一个位置因为j jj指针只会走一次, 算法时间复杂度O ( m log ⁡ n ) O(m \log n)O(mlogn)核心代码sort(q1,qm1);intj1;for(inti1;im;i){intlq[i].l,rq[i].r,idq[i].id;while(jr){if(last[w[j]])add(last[w[j]],-1);add(j,1);last[w[j]]j;j;}ans[id]get(r)-get(l-1);}代码实现#includebits/stdc.husingnamespacestd;constintN50010,M2e510,S1e610;intn,m;intw[N];structAsk{intl,r,id;booloperator(constAska)const{returnra.r;}}q[M];inttr[S],last[S],ans[M];inlineintlowbit(intx){returnx-x;}voidadd(intu,intx){for(intiu;iS;ilowbit(i))tr[i]x;}intget(intu){intans0;for(intiu;i;i-lowbit(i))anstr[i];returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;for(inti1;in;i)cinw[i];cinm;for(inti1;im;i){intl,r;cinlr;q[i]{l,r,i};}sort(q1,qm1);intj1;for(inti1;im;i){intlq[i].l,rq[i].r,idq[i].id;while(jr){if(last[w[j]])add(last[w[j]],-1);add(j,1);last[w[j]]j;j;}ans[id]get(r)-get(l-1);}for(inti1;im;i)coutans[i]\n;return0;}离线-线段树解法因为树状数组维护的是位置的前缀和,线段树也可以解决代码实现#includebits/stdc.husingnamespacestd;constintN50010,M2e510,S1e610;intn,m;intw[N];structAsk{intl,r,id;booloperator(constAska)const{returnra.r;}}q[M];intlast[S],ans[M];structNode{intl,r;intsum;}tr[N2];voidpushup(intu){tr[u].sumtr[u1].sumtr[u1|1].sum;}voidbuild(intu,intl,intr){tr[u]{l,r,0};if(lr)return;intmidlr1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);}voidmodify(intu,intpos,intx){if(tr[u].ltr[u].r){tr[u].sumx;return;}intmidtr[u].ltr[u].r1;if(posmid)modify(u1,pos,x);if(posmid)modify(u1|1,pos,x);pushup(u);}intquery(intu,intql,intqr){if(tr[u].lqltr[u].rqr)returntr[u].sum;intans0;intmidtr[u].ltr[u].r1;if(qlmid)ansquery(u1,ql,qr);if(qrmid)ansquery(u1|1,ql,qr);returnans;}inlineintlowbit(intx){returnx-x;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;for(inti1;in;i)cinw[i];cinm;for(inti1;im;i){intl,r;cinlr;q[i]{l,r,i};}build(1,1,n);sort(q1,qm1);intj1;for(inti1;im;i){auto[l,r,id]q[i];while(jr){if(last[w[j]])modify(1,last[w[j]],-1);modify(1,j,1);last[w[j]]j;j;}ans[id]query(1,l,r);}for(inti1;im;i)coutans[i]\n;return0;}离线-莫队算法假设最坏情况下, 每次查询一个区间n nn, 开一个数组用于记录每个数字出现的次数, 算法时间复杂度O ( q n ) O(qn)O(qn), 无法通过莫队优化开一个c n t cntcnt数组用来记录每个数字出现的次数( 1 ) (1)(1)对查询区间进行排序假设当前查询区间是[ i , j ] [i, j][i,j]蓝色部分是下一段查询的区间( 2 ) (2)(2)对于每个区间首先移动j jj指针, 移动到下一次查询的右端点上, 同时对于当前数字x xx, 如果未出现过那么不同数字的数量 1 11, 否则不同数字的出现次数不发生变化, 同时累计c n t cntcnt数组的值再将指针i ii移动到下一次查询的左端点, 对于当前需要删除的数字x xx, 如果出现次数大于1 11, 那么c n t ( x ) − 1 cnt(x) - 1cnt(x)−1, 不对答案产生影响, 否则答案− 1 -1−1因为每次移动指针最坏情况下是O ( n ) O(n)O(n)次, 算法时间复杂度最坏O ( q n ) O(qn)O(qn), 还是没办法通过算法核心优化:因为算法瓶颈在指针会移动O ( n q ) O(nq)O(nq)次数, 尝试使得右指针是单调的(不会向回移动),左指针分块, 具体的来说区间左端点按照分块的编号排序,双关键字排序如果分块编号相同按照区间右端点从小到大排序如果分块编号不同, 块小的在前面将所有查询分为n \sqrt nn​块, 每一块长度是也是n \sqrt nn​,块内部区间的右端点是递增的对于右指针来说,块内走的次数不会超过n nn, 一共n \sqrt nn​块, 最多移动n n n \sqrt nnn​次左指针分为两种情况块内最多移动n \sqrt nn​次, 最多q qq个询问, 算法时间复杂度最差O ( q n ) O(q \sqrt n)O(qn​)块间最多移动2 n 2 \sqrt n2n​次, 最多跨越n − 1 \sqrt n - 1n​−1个块, 最差O ( 2 n ) O(2n)O(2n)因此左指针的最差时间复杂度是O ( q n ) O(q \sqrt n)O(qn​)左右时间取最大值, 因此优化后的算法时间复杂度最坏情况下是O ( q n ) O(q \sqrt n)O(qn​)假设块的大小是a aa, 右指针的移动次数是n 2 a \frac{n ^ 2}{a}an2​, 左指针的最大移动次数是m a mama, 也就是a n 2 m a \sqrt {\frac{n ^ 2}{m}}amn2​​左右指针移动的次数相当如果a n a \sqrt nan​比较慢, 尝试将a aa变为n 2 m \sqrt {\frac{n ^ 2}{m}}mn2​​核心代码// i表示左端点, j表示右端点for(intk0,i1,j0,res0;km;k){// l, r分别代表当前区间的左右端点auto[l,r,id]q[k];while(jr)add(w[j],res);while(jr)del(w[j--],res);while(il)del(w[i],res);while(il)add(w[--i],res);ans[id]res;}示例代码#includebits/stdc.husingnamespacestd;constintN50010,M2e510,S1e610;intn,m,len;intw[N],cnt[S],ans[M];structAsk{intl,r,id;}q[M];intget(inti){returni/len;}boolcmp(constAska,constAskb){intbaget(a.l),bbget(b.l);if(babb)returna.rb.r;returnbabb;}voidadd(intx,intans){if(!cnt[x])ans;cnt[x];}voiddel(intx,intans){cnt[x]--;if(!cnt[x])ans--;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;for(inti1;in;i)cinw[i];cinm;// 计算块长lensqrt(n*n/m1);for(inti0;im;i){intl,r;cinlr;q[i]{l,r,i};}sort(q,qm,cmp);for(intk0,i1,j0,res0;km;k){auto[l,r,id]q[k];while(jr)add(w[j],res);while(jr)del(w[j--],res);while(il)del(w[i],res);while(il)add(w[--i],res);ans[id]res;}for(inti0;im;i)coutans[i]\n;return0;}在线-主席树(持久化线段树)假设对于当前数字上一次出现的位置是l a s t i last_ilasti​那么当前区间[ l , r ] [l, r][l,r]内是第一次出现该数字等价于l a s t i l last_i llasti​l, 为了方便统计定义g ( i ) g(i)g(i)表示l a s t i 1 last_i 1lasti​1那么答案就是统计在区间[ l , r ] [l, r][l,r]内g ( i ) ≤ l g(i) \le lg(i)≤l的数字的个数, 可以使用主席树维护g ( i ) g(i)g(i)的取值查询的时候直接查询≤ l \le l≤l的所有g ( i ) g(i)g(i)就是答案算法时间复杂度O ( m log ⁡ n ) O(m \log n)O(mlogn)代码实现构建多个版本根节点数组r o o t [ N ] root[N]root[N]构建初始版本主席树对每个g ( i ) g(i)g(i)执行插入操作O ( n log ⁡ n ) O(n \log n)O(nlogn)计算区间和, 版本查询l − 1 , r l - 1, rl−1,r两个版本O ( m log ⁡ n ) O(m \log n)O(mlogn)#includebits/stdc.husingnamespacestd;constintN50010,M2e510,S1e610;intn,m;intw[N];structNode{intls,rs;ints;}tr[4*N17*N];intlast[S],g[N];introot[M],idx;intbuild(intl,intr){intuidx;tr[u]{0,0,0};if(lr)returnu;intmidlr1;tr[u].lsbuild(l,mid);tr[u].rsbuild(mid1,r);returnu;}intinsert(intp,intl,intr,intx){intuidx;tr[u]tr[p];tr[u].str[p].s1;if(lr)returnu;intmidlr1;if(xmid)tr[u].lsinsert(tr[p].ls,l,mid,x);if(xmid)tr[u].rsinsert(tr[p].rs,mid1,r,x);returnu;}intquery(intp,intq,intl,intr,intql,intqr){if(lqlrqr)returntr[q].s-tr[p].s;intans0;intmidlr1;if(qlmid)ansquery(tr[p].ls,tr[q].ls,l,mid,ql,qr);if(qrmid)ansquery(tr[p].rs,tr[q].rs,mid1,r,ql,qr);returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;root[0]build(1,n);for(inti1;in;i){cinw[i];g[i]last[w[i]]1;last[w[i]]i;root[i]insert(root[i-1],1,n,g[i]);}cinm;while(m--){intl,r;cinlr;// 注意这里查询的是 l的g[i]的数量intansquery(root[l-1],root[r],1,n,1,l);coutans\n;}return0;}