[unknown source] 蔬菜
一、题目
二、解法
根据部分分的提示，我们可以预处理一个二维前缀和拿到 s u b t a s k 4 \tt subtask4 subtask4 的分数。
如果上述算法在某种蔬菜的出现次数较多，他的效率就比较高。那对于出现次数少的蔬菜呢？最好是无关蔬菜种类地统计，这指向了我们需要用算贡献的方法来处理这种蔬菜。
用点对贡献的方式，因为平方其实相当于求点对的数量。对于一种蔬菜我们任取两个点加入坐标
(
a
,
b
,
c
,
d
)
(a,b,c,d)
(a,b,c,d)，那么它对询问
(
x
0
,
y
0
,
x
1
,
y
1
)
(x_0,y_0,x_1,y_1)
(x0,y0,x1,y1)产生贡献当且仅当：
x
0
≤
a
,
c
≤
x
1
,
y
0
≤
b
,
d
≤
y
1
x_0\leq a,c\leq x_1,y_0\leq b,d\leq y_1
x0≤a,c≤x1,y0≤b,d≤y1显然可以通过排序去掉一维的比较，那么剩下的三维写个三维树状数组统计即可，常数小，时间复杂度
O
(
(
n
2
k
+
q
)
log
3
k
)
O((n^2k+q)\log ^3k)
O((n2k+q)log3k)，第一种的时间复杂度
O
(
n
2
k
(
n
2
+
q
)
)
O(\frac{n^2}{k}(n^2+q))
O(kn2(n2+q))
所以 k = n 2 + q log 3 k k=\sqrt\frac{n^2+q}{\log^3 k} k=log3kn2+q