小S最近学会了二分图匈牙利匹配算法。
现在二分图的X部有N个数字Ai,Y部有K个数字Ci
已知如果Ai+Cj<=Z,那么Ai和Cj之间就有一条边，求二分图（X，E，Y)的最大匹配数。
小S是初学者.所以她想多做一些练习来巩固知识。于是她找到了一个长度为M的正整数数组B[]，每次她会在B[]数组中抽取一段连续的区间[Li，Ri]，把区间[Li，Ri]的所有数字作为二分图Y部的K个数字Ci.然后重新求一次二分图最大匹配数。
小S打算一共做Q次练习.但是她不知道每次计筧出的答案对不对.你能帮帮她吗？
笫一行为三个正整数N、M、Z.
笫二行为N个正整数.笫i个正整数表示Ai。
笫三行力M个正整数，笫i个正整数表示Bi。
接下宋Q行每行两个正整数.笫i行的两个正整数分别表示Li、Ri。
对十每次练习.输出该次练习的答案。
4 10 8
1 2 4 6
6 3 6 2 8 4 9 10 6 8
4
1 4
2 5
5 6
1 6
4
3
1
4
|
测试数据编号 |
N |
M |
Q |
|
1-4 |
<50 |
<50 |
<50 |
|
5-10 |
<2501 |
<2501 |
<2501 |
|
11-14 |
< 152501 |
<45678 |
<
45678 |
|
15-16 |
<152501 |
<50 |
<52501 |
|
17-20 |
<152501 |
<52501 |
<52501 |
对于 100%的数据：1<=Ai、Bi、Z<=109,1<=Li<=Ri<=Q。
保证数据有一定梯度。
你可能潘要用到这些小S在学习匈牙利算法中査阅的资料：
【二分图】：
二分阁乂称作二部图，是图论中的一种特殊模型。设G = <V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(X.，Y）， 并且图中的每条边（i，j）所关联的两个顶
点i和j分别属于这两个不同的顶点集(i∈X，j∈Y)，则称图G为一个二分图。
【最大匹配】：
给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同—个顶点，则称M是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题。
【增广路】：
若P是图G中一条连通两个未匹配顶点的路径.并且属M的边和不属M的边（即已匹配和待匹配的边〉在P上交替出现，则称P为相对于M的一条增广路径.
【匈牙利算法】：
用增广路求最大匹配（称作匈牙利算法，匈牙利数学家Edmonds于1965年提出〉
算法轮廓：
⑴罝M为空。
⑵找出一条增广路径P，通过取反操作获得更大的匹配M'代替M。
⑶重复⑵操作直到找不出增广路径为止。