#1890. problem

    ID: 1890 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1859来源:qoj.ac数据:公开样例线段树数学

problem

problem

题目描述

标题: problem - Problem - QOJ.ac

#9649. problem

Statistics

The problem was used in the following contests:

题目描述

给定 n 个区间 [li,ri] 和一个常数 k。

对两个区间 [l,r] 和 [l′,r′],定义函数 f([l,r],[l′,r′]) 为区间 [l,r] 和 [l′,r′] 的交集长度。

更形式化地,我们有:

f([l,r],[l′,r′])={0if r′<l or l′>rmin(r,r′)−max(l,l′)+1otherwise

给定 m 组询问,每次给出区间 [L,R],你需要求出 ∑i=1nf([L,R],[li,ri])k,对 109+7 取模。

输入格式

第一行包含三个整数 n,k,m。

接下来的 n 行每行包含两个整数 li,ri。

接下来的 m 行每行包含两个整数 L,R。

输出格式

输出 m 行,每行一个整数表示 ∑i=1nf([L,R],[li,ri])k,对 109+7 取模。

样例

样例 1 输入

3 1 2
1 1
1 2
1 3
1 2
1 3

样例 1 输出

5
6

样例 1 解释

对于第一个询问,答案为 f([1,1],[1,2])+f([1,2],[1,2])+f([1,3],[1,2])=1+2+2=5。

对于第二个询问,答案为 f([1,1],[1,3])+f([1,2],[1,3])+f([1,3],[1,3])=1+2+3=6。

样例 2 输入

4 2 4
1 4
2 3
1 3
2 4
1 4
2 3
1 3
2 4

样例 2 输出

38
16
26
26

样例 2 解释

对于第一个询问,答案为 f([1,4],[1,4])2+f([2,3],[1,4])2+f([1,3],[1,4])2+f([2,4],[1,4])2=16+4+9+9=38。

数据范围

对于所有数据,保证:1≤n,m≤105,1≤k≤14,1≤li≤ri≤n,1≤L≤R≤n。

测试点编号 n,m≤ k ri,R≤ 特殊性质 1∼2 2×103 ≤14 n 无 3∼4 105 =1 n 无 5∼10 105 =2 n 无 11∼12 105 ≤8 minn,600 无 13∼20 105 ≤8 n A 21∼23 105 ≤8 n 无 24∼25 105 ≤14 n 无

特殊性质 A:保证所有给出的区间两两之间要么相等,要么不存在包含关系。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 1 2
1 1
1 2
1 3
1 2
1 3
5
6

样例 2

4 2 4
1 4
2 3
1 3
2 4
1 4
2 3
1 3
2 4
38
16
26
26