题干：

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called AtCoder Express possesses Mtrains, and the train i runs from City Li to City Ri (it is possible that Li=Ri). Takahashi the king is interested in the following Q matters:

  • The number of the trains that runs strictly within the section from City pi to City qi, that is, the number of trains j such that pi≤Lj and Rj≤qi.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

 

  • N is an integer between 1 and 500 (inclusive).
  • M is an integer between 1 and 200 000 (inclusive).
  • Q is an integer between 1 and 100 000 (inclusive).
  • 1≤Li≤Ri≤N (1≤i≤M)
  • 1≤pi≤qi≤N (1≤i≤Q)

Input

 

Input is given from Standard Input in the following format:

N M Q
L1 R1
L2 R2
:
LM RM
p1 q1
p2 q2
:
pQ qQ

Output

 

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City pi to City qi.

Sample Input 1

 

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

 

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

 

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

 

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1. The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

 

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

 

7
9
10
6
8
9
6
7
8
10

解题报告：

     这题区间dp乱搞一下就可以了。

AC代码1：（区间dp）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 500 + 5;
int a[MAX][MAX],n,m,q; 
ll dp[MAX][MAX];
int main()
{
	cin>>n>>m>>q;
	int l,r;
	while(m--) {
		scanf("%d%d",&l,&r);
		a[l][r]++;
	}
	for(int len = 1; len<=n; len++) {
		for(int l = 1; l+len-1<=n; l++) {//每一个起点 
			int r = l+len-1;
			if(l == r) dp[l][r]=a[l][r];
			else if(r-l==1) dp[l][r] = dp[l][l] + dp[r][r] + a[l][r];
			else dp[l][r] = dp[l][r-1] + dp[l+1][r] - dp[l+1][r-1]+a[l][r];
		}
	}
	while(q--) {
		ll ans = 0;
		scanf("%d%d",&l,&r);
		printf("%lld\n",dp[l][r]);
	}
	return 0 ;
 }

AC代码2：（区间dp）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 500 + 5;
int a[MAX][MAX],n,m,q; 
ll dp[MAX][MAX];
int main()
{
	cin>>n>>m>>q;
	int l,r;
	while(m--) {
		scanf("%d%d",&l,&r);
		a[l][r]++;
	}
	for(int l = n; l>0; l--) {
		for(int r = 1; r<=n; r++) {
			dp[l][r] = a[l][r] + dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1];
		}
	}
	while(q--) {
		ll ans = 0;
		scanf("%d%d",&l,&r);
		printf("%lld\n",dp[l][r]);
	}
	return 0 ;
 }

AC代码3：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 500 + 5;
int a[MAX][MAX],n,m,q; 
int main()
{
	cin>>n>>m>>q;
	int maxx = -1,l,r;
	while(m--) {
		scanf("%d%d",&l,&r);
		maxx = max(maxx,r);
		a[l][r]++;
	}
	for(int i = 1; i<=maxx; i++) {
		for(int j = 1; j<=maxx; j++) {
			a[i][j] += a[i][j-1];
		}
	}
	while(q--) {
		ll ans = 0;
		scanf("%d%d",&l,&r);
		for(int i = l; i<=r; i++) {
			ans += a[i][r];
		}
		printf("%lld\n",ans);
	}
	

	return 0 ;
 }