P4396
P4396 [AHOI2013] 作业
题意 给定一个序列,每次询问求: 在区间 \([l, r]\) 中,大小在 \([a, b]\) 中数的个数与种类数。 Sol 对于第一问直接离线跑树状数组二维偏序。 第二问考虑莫队,发现只需要维护莫队那个表示种类的数组的区间和就行了。 要求 \(O(1)\) 修改的话,写个值域分块? Code # ......
P4396 [AHOI2013] 作业
Link 这是一道恶心至极的莫队套分块题。 考虑维护一个莫队,维护在 \([l,r]\) 值域下的答案。 考虑维护一个值域分块,维护在只余下 \([a,b]\) 的答案。 单点修改对答案带来的变化: \(ans1\) 块:直接在 \(pos\) 位置上面做一个修改操作,然后去 \(\Theta(1) ......
P4396 [AHOI2013] 作业
经典的莫队+值域分块 虽然直接用莫队+树状数组也是能过的 贴个板子 #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<cmath ......