小寄巧
ღꦿ࿐
·
·
休闲·娱乐
乱七八糟的问题。
。
- 1.区间出现出现的数的 \prod a_i^{c_i} ，带修
直接树状数组求区间乘积。
* 3.区间出现出现的数的 $\prod a_i$，带区间推平
势能分析发现 $pre$ 的变化量是 $O(n+m)$ 的，配合拿个ODT就行，直接暴力修改二位偏序。
洛谷上有个类似题，但是由于要YNOI卡常就没去写。
不带修可以离线单 $\log$ 解决。
* 4.区间出现的数的 $\prod a_i^{max\{c_i-1,0\}}$ ，带修
$i \in [l,r] , pre(i) \in [l,r]$ 同样二位偏序带修。
* 5.区间出现的数的 $\prod a_i^{max\{c_i-k,0\}}$ ，不带修
$i \in [l,r] , pre^k(i) \in [l,r]$ 手玩一下显然正确。
* 6.区间出现的数的 $\prod a_i^{max\{c_i-k,0\}}$ ，带修
时间复杂度瓶颈在改变 $pre^k(i)$ ，再在树套树上修改。
k较小可以用 set 暴力修改前驱后继，k较大可以使用带修莫队。
分块+根号分治应该可做吧，没有细想。
* 7.区间出现出现的数的 $\prod a_i^{[c_i=1]}$ ，不带修
离线，将询问挂在右端点，从左到右扫，线段树维护对应左端点的答案，加入右端点对 $(pre_i,i],(pre^2_i,i] $进行区间乘除就行。
另一种：
三维偏序 $pre < l,i\in[l,r],suf > r
区间出现出现的数的 \prod a_i^{[c_i=1]} ，带修
你可以试着用KDT去做上面的带修三位偏序
分块或者带修莫队，好像没别的做法了。
考虑过从 \prod a_i^{c_i} 中去除 \prod a_i^{c_i[c_i\geq 2]} ， 使用上方做法数线段，但是比较烦，每种数出来的线段+1就是答案的指数，但这又变成二维平面数颜色了，不太可做。
应该没有更优秀的做法了？有请务必告诉kk。
以后可能会更新。
写完了，还剩6分钟回寝室，开把王怒一门先。
体测完了，班上吐了几个。。。。。
upd 2020/10/20:
简简单单。
离线的话直接莫队，在线的话分块，维护整块之间的答案，然后把散块插到整块里面更改。
upd 2020/10/25:
nxt_i > r , i\ge l$ 的 $i_{\min}
分成若干段，只有两段会贴边界（散），中间部分为整。
整部分为 [i,nxt_i] \in [l,r] 的二维数点
散部分为问题 10。