3636: 牛半仙的妹子图(第三轮02)
题目描述
牛半仙有n个妹子，他把每个妹子都藏到了一座不同的房子中。 这些房子间有m条双向道路，每条道路都有一个困难程度wi 。 牛半仙对每个妹子都赋予了一个类型ci 。
牛半仙每晚都会多次从自己的家x出发，去见所有他能见到的妹子。
牛半仙每次出发见完所有妹子后的都会得到一个愉悦值v，为这次见到的妹子的 不同种类数个数。
有些道路过于困难，困难程度大于了牛半仙的困难接受程度，牛半仙因为要留尽 量多的体力给妹子，所以是不会从这些道路上经过的。
不过牛半仙每出发一次后困难接受程度也会增加 1。
然而当对困难的接受程度大于最大困难接受程度ri时，牛半仙这晚就不会再出去 了。
牛半仙第i晚的初始困难接受程度li，以及最大困难接受程度ri ，牛半仙想知道 他每晚能获得的愉悦值之和。
输入
第一行五个整数 n， m， q， x， opt， opt为 0 或 1
若 opt = 1，下一行紧跟一个整数M ，为强制在线的模数
第二行n个整数，第 i个数表示妹子 i的种类ci接下来m行，每行三个整数ui ，vi， wi，表示一条连接第ui， vi个妹子的房子，困难程度为wi的道路。
接下来q 行， 每行两个整数li， ri ， 分别表示这晚牛半仙初始的困难接受程度， 最大的困难接受程度，若opt = 1，则 li = (lixor las)mod M + 1，
ri = (ri xor las) mod M + 1，
其中las表示上一次输出的答案，初始为0 。如果li > ri ，那么交换它们。
输出
q行输出，每行表示这晚牛半仙能获得的愉悦值之和。
样例输入 复制
6 6 3 3 0
1 1 1 2 2 3
1 6 1
1 2 5
2 3 4
3 6 3
3 4 6
5 6 2
1 3
1 4
2 4样例输出 复制
5
8
7提示
【样例 1 输入】
6 6 3 3 0
1 1 1 2 2 3
1 6 1
1 2 5
2 3 4
3 6 3
3 4 6
5 6 2
1 3
1 4
2 4
【样例 1 输出】
5
8
7
【样例 1 说明】
对于询问 1， li=1， ri=3， ans=1+1+3。
困难程度为 1 和 2 时， 只能到达 3，种类数为 1 。 困难程度为 3 时，可以到达 1 3 5 6，种类数为 3。
【样例 2 输入】
6 6 3 3 1
1000007
1 1 1 2 2 3
1 6 1
1 2 5
2 3 4
3 6 3
3 4 6
5 6 2
0 2
5 6
9 11
【样例 2 输出】
5
8
7
【样例 2 说明】
前一个样例的强制在线版
【数据范围】
- 10pts n, m, q ≤ 10， ci, li, ri ≤ 10， opt = 0
- 20pts n, m, q ≤ 100， opt = 0
- 40pts n, m, q ≤ 10^3， opt = 0
- 另 15pts li = ri, ri ≤ 10^9， opt = 0
- 另 15pts li, ri, wi ≤ 10^5, ri, wi ≤ 10^5， opt = 0
- 100pts100 n, m ≤ 5 × 10^5， q ≤ 10^5， ci ≤ 500， 0 < wi, li, ri ≤ 10^9