http://www.lightoj.com/volume_showproblem.php?problem=1089

题意：给出许多区间，查询某个点所在的区间个数

思路：线段树，由于给出的是区间，查询的是点，考虑将其离线并离散化，普通线段树即可。

/** @Date    : 2016-12-17-20.49  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;struct yuu{    int l, r;    int sum, add;}tt[N << 4];void pushdown(int p){	if(tt[p].add != 0)	{		tt[p << 1].sum += tt[p].add;		tt[p << 1 | 1].sum += tt[p].add;		tt[p << 1].add += tt[p].add;		tt[p << 1 | 1].add += tt[p].add;		tt[p].add = 0;	}}void pushup(int p){	tt[p].sum = tt[p << 1].sum + tt[p << 1 | 1].sum;}void build(int l, int r, int p){	tt[p].l = l;	tt[p].r = r;	tt[p].sum = 0;	tt[p].add = 0;	if(l == r)		return ;	int mid = (l + r) >> 1;	build(l, mid, p << 1);	build(mid + 1, r, p << 1 | 1);	pushup(p);}void updata(int l, int r, int v, int p){	if(l <= tt[p].l && r >= tt[p].r)    {		tt[p].sum += v;		tt[p].add += v;        return ;    }	pushdown(p);	int mid = (tt[p].l + tt[p].r) >> 1;	//cout <<mid<< endl;	if(l <= mid)		updata(l, r, v, p << 1);	if(r > mid)		updata(l, r, v, p << 1 | 1);	pushup(p);}int query(int l, int r, int p){	if(l <= tt[p].l && r >= tt[p].r)    {		return tt[p].sum;    }    pushdown(p);	int mid = (tt[p].l + tt[p].r) >> 1;	int ans = 0;	if(l <= mid)		ans += query(l, r, p << 1);	if(r > mid)		ans += query(l, r, p << 1 | 1);	return ans;}mapq;map::iterator it;int l[N], r[N];int x[N];int main(){	int T;	int cnt = 0;	cin >> T;	while(T--)	{		int n, m;		q.clear();		scanf("%d%d", &n, &m);		for(int i = 0; i < n; i++)		{			scanf("%d%d", l + i, r + i);			q[l[i]] = 1;			q[r[i]] = 1;		}		for(int i = 0; i < m; i++)		{			scanf("%d", x + i);			q[x[i]] = 1;		}		printf("Case %d:\n", ++cnt);		int ct = 0;		for(it = q.begin(); it != q.end(); it++)		{			it->se = ++ct;		}		build(0, ct, 1);		for(int i = 0; i < n; i++)		{			//cout << q[l[i]] <<"~"<<q[r[i]]<< endl;			updata(q[l[i]], q[r[i]], 1, 1);		}		for(int i = 0; i < m; i++)		{		   // cout << q[x[i]] << endl;			printf("%d\n", query(q[x[i]], q[x[i]], 1));		}	}    return 0;}

LightOJ 1089 - Points in Segments (II) 线段树区间修改+离散化