V
主页
【算法强化】【较难数据结构题目】三道高质量分块与莫队难题精讲-信息学竞赛
发布人
不要吝惜您的赞，留一个在走呗 #include<bits/stdc++.h> using namespace std;const int N=1e5+2; int n,m,S,a[N],h,L,R,cnt[N],ans1[N],ans2[N],p[22],sz;char c; struct Node{ int l,r,a,b,id; bool operator <(const Node b){ if(l/S!=(b.l)/S)return l<b.l; return ((l/S)&1?r>b.r:r<b.r); } }q[N]; struct BIT{ int r=1e5,c[N],res; inline int lowbit(const int x){return (x&(-x));} inline void add(int x,int k){ if(!k||!x)return; for(;x<=r;x+=lowbit(x))c[x]+=k; } inline int sum(int x){ res=0; for(;x;x-=lowbit(x))res+=c[x]; return res; } }b1,b2; inline int read(){ h=0,c=getchar(); while(!(c>='0'&&c<='9'))c=getchar(); while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+(c^48),c=getchar(); return h; } inline void write(int x){ if(x==0){putchar('0');return;} while(x)p[++sz]=x%10,x/=10; while(sz)putchar(p[sz]^48),sz--; } int main(){ n=read(),m=read(),S=sqrt(n); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(), q[i].a=read(),q[i].b=read(),q[i].id=i; sort(q+1,q+m+1); for(int i=1;i<=m;i++){ while(L>q[i].l)L--,cnt[a[L]]++, b1.add(a[L],1),b2.add(a[L],(cnt[a[L]]==1)); while(R<q[i].r)R++,cnt[a[R]]++, b1.add(a[R],1),b2.add(a[R],(cnt[a[R]]==1)); while(L<q[i].l)cnt[a[L]]--, b1.add(a[L],-1),b2.add(a[L],-(cnt[a[L]]==0)),L++; while(R>q[i].r)cnt[a[R]]--, b1.add(a[R],-1),b2.add(a[R],-(cnt[a[R]]==0)),R--; ans1[q[i].id]=b1.sum(q[i].b)-b1.sum(q[i].a-1), ans2[q[i].id]=b2.sum(q[i].b)-b2.sum(q[i].a-1); } for(int i=1;i<=m;i++)write(ans1[i]),putchar(' '), write(ans2[i]),putchar('\n'); return 0; }
打开封面
下载高清视频
观看高清视频
视频下载器
【算法强化】【省选根号数据结构（三）】分块、莫队、根号分治的技巧-信息学竞赛
【算法强化】【动态规划-6动态动态规划】ddp动态动态规划，树形动态规划，树链剖分，广义矩阵乘法-信息学竞赛
【算法强化】【省选根号数据结构】分块、莫队、根号分治讲解与经典例题-信息学竞赛
取值范围是难题？这两道题让你掌握怎么求直线斜率的取值范围！！！！！
【算法强化】【整体二分】整体二分的基本思想与实战练习-信息学竞赛
【算法进阶】【树链剖分】树链剖分（重链剖分）精讲-信息学竞赛
【算法强化】【斜率优化动态规划】动态规划的优化之斜率优化DP-信息学竞赛
【算法强化】【省选根号数据结构（二）】分块、莫队与根号分治经典例题讲解-信息学竞赛
【算法强化】【综合性杂题选讲-2】Kruskal重构树+可持久化线段树 P7834[ONTAK2010]Peaks加强版-信息学竞赛
【算法进阶】【分块算法】分块实战，loj.ac6277~6281 数列分块入门1~5 - 信息学竞赛
kmp算法，我愿称之为，闲鱼封神时刻
【算法进阶】【点分治】图解点分治模板及例题讲解-信息学竞赛
【算法进阶】【高级数据结构-替罪羊树】平衡树解法之一替罪羊树讲解-信息学竞赛
【算法强化】【AC自动机的应用】AC自动机与动态规划题目详解-信息学竞赛
【算法强化】【线段树与矩阵乘法（一）】数据结构与线性代数的结合-信息学竞赛
【算法进阶】【数论-组合初步】排列组合二项式定理Lucas定理P1350车的放置精讲-信息学竞赛
【选择排序】大家都能学会的选择排序，会做题，会写代码，搞定
【算法进阶】【AtCoder Beginner Contest简单题选讲】历次abc简单题讲解-信息学竞赛
【算法进阶】【数据结构-树状数组】树状数组及二维树状数组讲解-信息学竞赛
物理差？看它！动态平衡白捡6分，四大方法助你成功解决动态平衡的所有难题！【高考物理晴姐】
【算法进阶】【字符串-AC自动机】AC自动机算法原理及实现精讲+代码 - 信息学奥赛
【算法进阶】【贪心-过河问题】更复杂的贪心，过河问题情况详解-信息学竞赛
【算法进阶】【简单线段树题目】线段树简单练习题P2787 语文1（chin1）- 理理思维-信息学竞赛
【算法进阶】【带修莫队】莫队算法与时间戳技术的精妙结合-信息学竞赛
【算法进阶】【严格次小生成树】Kruskal最小生成树+树上倍增详解-信息学竞赛
【算法进阶】【数论分块（整除分块）】数论分块与经典例题讲解-信息学竞赛
【算法进阶】【动态规划百练-IOI1998 Polygon】上古IOI动态规划题目讲解-信息学竞赛
【算法进阶】【动态规划-7数位动态规划】最简单的dp-数位dp！数位dp知识点与例题Segment Sum详解-信息学竞赛
【算法进阶】【codeforces杂题选讲（一）】codeforces经典题目讲解-信息学竞赛
【算法强化】【codeforces杂题选讲（二）】codeforces3000难度好题选讲-信息学竞赛
【算法进阶】【动态规划百练】思维与线段树优化动态规划[ARC159D] LIS 2-信息学竞赛
【算法进阶】【线段树的合并与分裂】合并与分裂：均摊复杂度之美-信息学竞赛
【算法进阶】【字符串-哈希算法】哈希算法、哈希加密算法及哈希例题讲解-信息学竞赛
【算法进阶】【动态规划百练】状态压缩动态规划+BFS P2622 关灯问题II-信息学竞赛
【算法进阶】【树上技巧】一些比较常见的树上trick-信息学竞赛
动态区间查询问题（前缀和 分块 线段树 树状数组）
【算法进阶】【动态规划百练】简单数位dp题目P2188 小Z的 k 紧凑数-信息学竞赛
【算法进阶】【动态规划百练】简单状压dp与滚动数组优化 P5005 中国象棋 - 摆上马 -信息学竞赛
【算法进阶】【带权并查集/并查集复习】最后一次学习简单并查集！学不会以后各种算法都听不懂！ - 信息学竞赛
【算法进阶】【线段树的应用】线段树维护动态区间最大子段和P4513 小白逛公园-信息学竞赛
