2020-2021:teams:legal_string:jxm2001:莫队算法_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:莫队算法_1 [2021/02/03 19:52] jxm2001 |
2020-2021:teams:legal_string:jxm2001:莫队算法_1 [2021/02/07 19:17] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 141: | 行 141: | ||
| 于是总复杂度为 $O\left(\frac {n^3}{S^2}+nS\right)$，取取块的大小为 $O\left(n^{\frac 23}\right)$，则总时间复杂度为 $O\left(n^{\frac 53}\right)$。 | 于是总复杂度为 $O\left(\frac {n^3}{S^2}+nS\right)$，取取块的大小为 $O\left(n^{\frac 23}\right)$，则总时间复杂度为 $O\left(n^{\frac 53}\right)$。 | ||
| - | ==== 算法例题 ==== | + | ==== 例题 1 ==== |
| [[https://www.luogu.com.cn/problem/P1903|洛谷p1903]] | [[https://www.luogu.com.cn/problem/P1903|洛谷p1903]] | ||
| 行 224: | 行 224: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ==== 例题 2 ==== | ||
| + | |||
| + | [[https://codeforces.com/problemset/problem/940/F|CF940F]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一个长度为 $n$ 的序列，接下来两种操作。 | ||
| + | |||
| + | 操作 $1$ 给定询问区间 $[l,r]$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，$s_i$ 表示 $i$ 在 $c_0\sim c_{1e9}$ 中出现的次数，求 $\text{mex}(s)$。 | ||
| + | |||
| + | 其中 $\text{mex}(s)$ 表示没有出现在序列 $s$ 中的最小非负整数。 | ||
| + | |||
| + | 操作 $2$ 为单点修改。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 首先离散化一下原序列和修改操作的数值，这样数值范围变为 $O(n+q)$，同时也不会影响答案。 | ||
| + | |||
| + | 另外假设 $\text{mex}(s)=k+1$，则对每个 $i\in [1,k]$ 至少有一个 $j$ 满足 $c_j=i$，于是这样询问区间长度至少为 $\sum_{i=1}^k i=\frac {k(k+1)}2$。 | ||
| + | |||
| + | 于是 $\text{mem}(s)\sim O(\sqrt n)$。带修莫队维护 $c,s$ 序列，对每个询问暴力查询 $s$ 数组，时间复杂度 $O(n^{\frac 53}+m\sqrt n)$。 | ||
| + | |||
| + | ==== 例题 3 ==== | ||
| + | |||
| + | [[https://codeforces.com/contest/1476/problem/G|CF1476G]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一个长度为 $n$ 的序列，接下来两种操作。 | ||
| + | |||
| + | 操作 $1$ 给定询问区间 $[l,r]$ 和整数 $k$，设 $c_i$ 表示 $i$ 在 $a_l\sim a_r$ 中出现的次数，要求选择 $k$ 个 $c_i\gt 0$，记为 $d_{1\sim k}$，最小化 $\max (d)-\min (d)$。 | ||
| + | |||
| + | 操作 $2$ 为单点修改。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 设 $s$ 表示将 $c$ 从小到大排列的序列，于是答案变为 $\min (s_{i+k}-s_i)$。 | ||
| + | |||
| + | 有由于对于一个固定区间，$c_i$ 最多只有 $O(\sqrt n)$ 种取值(原因见例题 2)，于是 $s$ 最多仅有 $O(\sqrt n)$ 个值相同的段。 | ||
| + | |||
| + | 考虑维护 $s$ 每个段的左端点和右端点，然后双指针遍历 $s$，即可 $O(\sqrt n)$ 得到答案。 | ||
| + | |||
| + | 接下来考虑如何维护 $s$，当 $c_i$ 变为 $c_i+1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的右端点的 $c_i$ 改为 $c_i+1$ 即可。 | ||
| + | |||
| + | 当 $c_i$ 变为 $c_i-1$ 时，只需要将 $s$ 中的值等于 $c_i$ 的段的左端点的 $c_i$ 改为 $c_i-1$ 即可。 | ||
| + | |||
| + | 因为最多有 $n$ 个非 $0$ 的 $c_i$，故初始时用 $n$ 个 $0$ 填充 $s$ 即可(用 $0$ 填充可以将插入操作转化为修改操作)。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXC=2e5+5,Inf=1e9; | ||
| + | int blk_sz,a[MAXN],lst_a[MAXN],cnt[MAXC],cl[MAXN],cr[MAXN],s[MAXN]; | ||
| + | int ans[MAXN],qn,pn,lef=1,rig=0; | ||
| + | struct query{ | ||
| + | int l,r,k,t,idx; | ||
| + | bool operator < (const query &b)const{ | ||
| + | if(l/blk_sz!=b.l/blk_sz)return l<b.l; | ||
| + | if(r/blk_sz!=b.r/blk_sz)return ((l/blk_sz)&1)?(r<b.r):(r>b.r); | ||
| + | return ((r/blk_sz)&1)?(t<b.t):(t>b.t); | ||
| + | } | ||
| + | }q[MAXN]; | ||
| + | struct opt{ | ||
| + | int pos,cur,next; | ||
| + | }p[MAXN]; | ||
| + | void add(int v){ | ||
| + | int c=cnt[v]; | ||
| + | s[cr[c]]++; | ||
| + | cl[c+1]=cr[c]; | ||
| + | if(!cr[c+1])cr[c+1]=cl[c+1]; | ||
| + | cr[c]--; | ||
| + | if(cl[c]>cr[c])cl[c]=cr[c]=0; | ||
| + | cnt[v]++; | ||
| + | } | ||
| + | void del(int v){ | ||
| + | int c=cnt[v]; | ||
| + | s[cl[c]]--; | ||
| + | cr[c-1]=cl[c]; | ||
| + | if(!cl[c-1])cl[c-1]=cr[c-1]; | ||
| + | cl[c]++; | ||
| + | if(cl[c]>cr[c])cl[c]=cr[c]=0; | ||
| + | cnt[v]--; | ||
| + | } | ||
| + | void update(opt &p){ | ||
| + | if(lef<=p.pos&&p.pos<=rig){ | ||
| + | del(p.cur); | ||
| + | add(p.next); | ||
| + | } | ||
| + | a[p.pos]=p.next; | ||
| + | swap(p.cur,p.next); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | blk_sz=pow(n,2.0/3)+1; | ||
| + | _rep(i,1,n) | ||
| + | a[i]=lst_a[i]=read_int(); | ||
| + | _for(i,0,m){ | ||
| + | int op=read_int(); | ||
| + | if(op==1){ | ||
| + | qn++; | ||
| + | int l=read_int(),r=read_int(),k=read_int(); | ||
| + | q[qn].l=l,q[qn].r=r,q[qn].k=k,q[qn].t=pn,q[qn].idx=qn; | ||
| + | } | ||
| + | else{ | ||
| + | pn++; | ||
| + | int pos=read_int(),v=read_int(); | ||
| + | p[pn].pos=pos,p[pn].cur=lst_a[pos],p[pn].next=(lst_a[pos]=v); | ||
| + | } | ||
| + | } | ||
| + | sort(q+1,q+qn+1); | ||
| + | cl[0]=1,cr[0]=n; | ||
| + | _rep(i,1,n)cl[i]=cr[i]=0; | ||
| + | int tim=0; | ||
| + | _rep(i,1,qn){ | ||
| + | while(lef>q[i].l)add(a[--lef]); | ||
| + | while(rig<q[i].r)add(a[++rig]); | ||
| + | while(lef<q[i].l)del(a[lef++]); | ||
| + | while(rig>q[i].r)del(a[rig--]); | ||
| + | while(tim<q[i].t)update(p[++tim]); | ||
| + | while(tim>q[i].t)update(p[tim--]); | ||
| + | int cur=Inf,lpos=cr[0]+1,rpos=cr[0]; | ||
| + | while(lpos<=n){ | ||
| + | while(rpos<n&&rpos-lpos+1<q[i].k)rpos=cr[s[rpos+1]]; | ||
| + | if(rpos-lpos+1>=q[i].k)cur=min(cur,s[rpos]-s[lpos]); | ||
| + | lpos=cr[s[lpos]]+1; | ||
| + | } | ||
| + | ans[q[i].idx]=cur==Inf?-1:cur; | ||
| + | } | ||
| + | _rep(i,1,qn) | ||
| + | enter(ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
2020-2021/teams/legal_string/jxm2001/莫队算法_1.1612353143.txt.gz · 最后更改: 2021/02/03 19:52 由 jxm2001
