用dw做网站怎么给链接,重庆市建设工程造价信息网站,网站上传不了图片不显示不出来,免费ftp网站题目:
蒜头君想泡咖啡喝。现在他得到了 nn 份菜谱#xff0c;每个菜谱上都给了两个数l,rl,rl,r代表温度区间在[l,r][l,r][l,r] 度泡出来的咖啡会很好喝。
可是菜谱太多了#xff0c;蒜头君一度感到疑惑。经过思考之后他得出了一个结论#xff1a;某个温度只要有 k 份或者更…题目:
蒜头君想泡咖啡喝。现在他得到了 nn 份菜谱每个菜谱上都给了两个数l,rl,rl,r代表温度区间在[l,r][l,r][l,r] 度泡出来的咖啡会很好喝。
可是菜谱太多了蒜头君一度感到疑惑。经过思考之后他得出了一个结论某个温度只要有 k 份或者更多菜谱推荐那么这个温度下泡出来的咖啡会很好喝。
现在他给出了 m 个温度区间同样还是用 [l,r][l,r][l,r]表示现在求问每个区间里面有多少个整数使得咖啡在这个温度下泡出来会很好喝
输入格式 第一行为三个整数 n,k,m。
第 2∼n12\sim n12∼n1 行每行两个整数代表菜谱里面的 l,r。
第 n2∼nm1n2\sim nm1n2∼nm1 行每行两个整数代表待询问温度区间里面的 l,r。
输入的所有数都是正整数且不超过 2×1052\times 10^52×105 且满足 l≤rk≤nl\le rk\le nl≤rk≤n。
输出格式 对于每个询问输出一行为一个整数表示有多少可用的温度。
输出时每行末尾的多余空格不影响答案正确性
要求使用「文件输入输出」的方式解题输入文件为 coffee.in输出文件为 coffee.out
样例输入1
3 2 4 91 94 92 97 97 99 92 94 93 97 95 96 90 100
样例输出1
3 3 0 4
样例输入2
2 1 1 1 1 200000 200000 90 100
样例输出2
0
分析
前缀和优化
AC代码
#include bits/stdc.h
using namespace std;
typedef long long ll;const int N2e510;int a[N],sum[N];int main()
{freopen(coffee.in, r, stdin);freopen(coffee.out, w, stdout);int n,m,k;scanf(%d%d%d,n,k,m);for(int i0; in; i){int t1,t2;scanf(%d%d,t1,t2);a[t1]; --a[t21];}for(int i1; iN; i){a[i]a[i]a[i-1];if(a[i]k) sum[i];sum[i]sum[i-1];}while(m--){int l,r;scanf(%d%d,l,r);printf(%d\n,sum[r]-sum[l-1]);}return 0;
}
