公主的朋友(friend.*) 分块

发布于 2017-08-10  4.57k 次阅读


[toggle hide="yes" title="题目" color=""]

公主的朋友

出题人:Wulala

时间限制:1s 空间限制:256MB

由于 Wulala 在上个问题中的精彩表现,公主认为 Wulala 是一个很棒的人,就把 Wulala 留在了 X 国。这时正好公主的一位传教士朋友来拜访公主,于是想找 wulala 帮忙X 国如同一条直线,其中有 n 个城市,从东向西分别编号为 1~n。而他的国家中有 m 种宗教,每个城市一定会有一种信仰的宗教。

有时候有些城市为了获得更多的认可,会派出信仰本城市宗教的传教士前往其他国家。X 国

的传教士都十分厉害,只要是他途经的地方都会改信他所传播的宗教。

传教士们在路上碰到自己宗教的城市自然就不用传教了,可以停下来看看里番啥的,所以每

一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。

而传教士们都是文科僧,数学是很差的,所以他希望 Wulala 能帮他计算。可 Wulala 数学也不好,但他又不想在公主面前丢脸,你能帮帮他吗?

Input

第一行两个整数 n,m

第二行 n 个整数第 i 个整数代表第 i 各城市信仰的宗教

第三行一个整数 T 代表传教士的个数

接下来 T 行每行两个整数 x,y 代表 x 城向 y 城派遣了一个传教士(保证 x < y)

Output

输出 T 行,第 i 行代表第 i 个传教士询问的答案

Sample Input

2 2

1 2

2

1 2

1 2

Sample Output

0

1

Hint

对于 30%的数据 n <= 100000, m <= 10, T <= 100

对于 60%的数据 n <= 100000, m <= 10, T <= 100000

对于 100%的数据 n <= 100000, m <= 300, T <= 100000
[/toggle]

分块大法好,修改操作打标记,零散的块暴力重构。查询时遇到散块而且还有标记的时候也需要重构,整块直接加长度,非常简单。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974