企业网站空间,wordpress黑客主题,产品毕业设计作品网站,电商网站设计理念文章目录 问题引入 核心维护修改 总结Code 问题引入
洛谷P1903 嗯#xff0c;上手一个莫队 … \dots … #xff1f;还有修改操作#xff1f; 本文我们来学习带修莫队#xff0c;及支持修改的莫队。 请确保你已经学会了普通的莫队#xff0c;不会的可以看这里。
和原来的… 文章目录 问题引入 核心维护修改 总结Code 问题引入
洛谷P1903 嗯上手一个莫队 … \dots … 还有修改操作 本文我们来学习带修莫队及支持修改的莫队。 请确保你已经学会了普通的莫队不会的可以看这里。
和原来的莫队一样带修莫队仅仅是多了个修改而已废话 。 考虑暴力修改时间复杂度 O ( n 2 m ) O(n^2m) O(n2m) 显然纯粹的暴力莫队是解决不了的但我们又发现了如果修改的是1题目查询的是5至7那么我们修不修改都是可以的。
核心
所以带修莫队的本质还是莫队只是考虑在查询到区间时再改。 举个例子。 序列 1 2 3 4 5 有四次操作。
将5改成6求下标为1到3中有几个不同的数字把1改成2求下标为1到3中有几个不同的数字
我们只看查询操作对于第一次查询普通莫队可得答案为3。对于第二次查询修改后由普通莫队可得答案为2。 及用一个变量记录现在修改了几次在查询时修改或者改回去。 如现在修改了3次下次查询是在5次修改后就执行第45次修改。若下下次查询为2次修改后就撤销第345次修改。
维护
最重要的当然是排序函数了然而你会发现跟普通莫队没有什么区别只是奇偶优化就不用了改成修改次数从小到大这也很好理解。 del函数: 和普通莫队没什么区别不会的见这里。 add函数: 跟 del 函数一样。
修改
对于本题 首先修改的数得是查询区间内的否则不可能对答案有影响。 其次如果对答案有影响就是一下几种情况
sum-(--cnt[a[X]]0),sum(cnt[Y]1);当然修改用结构体来存储。 需要注意
修改时先 在改撤销是先撤在 − - −。对于修改再改一次就改回去了所以我们可以用 swap 偷个懒。即使修改的数对答案没影响也要 swap。将块的大小设置为 n 2 3 n^\frac{2}{3} n32 时更优。别问我怎么知道 。
总结
带修莫队就是在莫对队的基础上加了修改操作需分析题目给的修改操作要如何撤销。
Code
#includebits/stdc.h
using namespace std;
const int N1e61;
struct fy
{int l,r,id,t;
}L[N];
struct fy_
{int x,y;
}C[N];
int n,m,a[N],ans[N],cnt[N],pos[N],ks,gid,aid,x,y,l1,r0,t0,sum0;
char op;
bool cmp(fy x,fy y)
{return pos[x.l]pos[y.l]?pos[x.r]pos[y.r]?x.ty.t:x.ry.r:x.ly.l;
}
inline void add(int x)
{sum(cnt[a[x]]1);
}
inline void del(int x)
{sum-(--cnt[a[x]]0);
}
signed main()
{ios::sync_with_stdio(false);cin.tie(NULL),cout.tie(NULL);cinnm;kspow(n,2.0/3.0);for(int i1;in;i)cina[i],pos[i](i-1)/ks1;for(int i1;im;i){cinopxy;if(opQ)L[aid].lx,L[aid].ry,L[aid].idaid,L[aid].tgid;elseC[gid].xx,C[gid].yy;}sort(L1,Laid1,cmp);for(int i1;iaid;i){int clL[i].l,crL[i].r,jL[i].id,TL[i].t;while(lcl)del(l);while(lcl)add(--l);while(rcr)add(r);while(rcr)del(r--);while(tT){t;int XC[t].x,YC[t].y;if(XclXcr)sum-(--cnt[a[X]]0),sum(cnt[Y]1);swap(a[X],C[t].y);}while(tT){int XC[t].x,YC[t].y;if(XclXcr)sum-(--cnt[a[X]]0),sum(cnt[Y]1);swap(a[X],C[t].y); t--;}ans[j]sum;}for(int i1;iaid;i)coutans[i]\n;return 0;
}
