记录编号	426610	评测结果	AAAAAAATTT
题目名称	凯伦和咖啡	最终得分	70
用户昵称	JustWB	是否通过	未通过
代码语言	C++	运行时间	9.144 s
提交时间	2017-07-18 11:12:51	内存使用	20.91 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#include<cmath>
using namespace std;
struct stree
{
	int l,r;
	int ls,rs;
	int fre,lazy;
	stree(){l=0,r=0,ls=0,rs=0,fre=0;}
}tree[900000];
int n,k,q,tl,tr;
void build(int l,int r,int now)
{
	tree[now].l=l;tree[now].r=r;
	if(l==r)return;
	tree[now].ls=2*now;tree[now].rs=2*now+1;
	int mid=(l+r)>>1;
	build(l,mid,2*now);
	build(mid+1,r,2*now+1);
}
void pushd(int now)
{
	if(tree[now].l==tree[now].r)return;
	tree[tree[now].ls].lazy+=tree[now].lazy;
	tree[tree[now].rs].lazy+=tree[now].lazy;
	tree[now].lazy=0;
}
void push(int nl,int nr,int now)
{
	if(tree[now].lazy)pushd(now);
	if(nl==tree[now].l&&nr==tree[now].r)
	{
		tree[now].lazy++;
		return;
	}
	int mid=tree[tree[now].ls].r;
	if(nr<=mid)
	{
		push(nl,nr,tree[now].ls);
		return;
	}
	if(nl>mid)
	{
		push(nl,nr,tree[now].rs);
		return;
	}
	push(nl,mid,tree[now].ls);
	push(mid+1,nr,tree[now].rs);
}
void pusha(int now)
{
	if(tree[now].l==tree[now].r)
	{
		if(tree[now].lazy>=k)tree[now].fre++;
		return;
	}
	pushd(now);
	pusha(tree[now].ls);
	pusha(tree[now].rs);
	tree[now].fre=tree[tree[now].ls].fre+tree[tree[now].rs].fre;
}
int search(int nl,int nr,int now)
{
	if(nl==tree[now].l&&nr==tree[now].r)return tree[now].fre;
	int mid=tree[tree[now].ls].r;
	if(nr<=mid)return search(nl,nr,tree[now].ls);
	if(nl>mid)return search(nl,nr,tree[now].rs);
	return search(nl,mid,tree[now].ls)+search(mid+1,nr,tree[now].rs);
}
int main()
{
	freopen("coffee.in","r",stdin);
	freopen("coffee.out","w",stdout);
	scanf("%d%d%d",&n,&k,&q);
	build(1,200000,1);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&tl,&tr);
		push(tl,tr,1);
	}
	pusha(1);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&tl,&tr);
		printf("%d\n",search(tl,tr,1));
	}
	return 0;
}