CS48 D BIT

统计一个点对应的和它严格右下方的点，点对数量。由于数据规模很大，不能直接上二维的前缀和，先排一维序，然后用BIT维护前缀和即可。

/** @Date    : 2017-09-14 20:17:30

  * @FileName: D.cpp

  * @Platform: Windows

  * @Author  : Lweleth ([email protected])

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#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;

const LL mod = 1e9+7;

struct yuu

{

	int x, y;

};

yuu p[N];

int cmp(yuu a, yuu b)

{

	if(a.x != b.x)

	{

		return a.x < b.x;

	}

	return a.y < b.y;

}

LL t[N];

void add(int x, int v)

{

	while(x)

	{

		t[x] += v;

		t[x] %= mod;

		x -= x & (-x);

	}

}

LL sum(int x)

{

	LL res = 0;

	while(x <= N)

	{

		res += t[x];

		res %= mod;

		x += x & (-x);

	}

	return res;

}

int main()

{

	int n;

	while(cin >> n)

	{

		MMF(t);

		for(int i = 0; i < n; i++)

		{

			scanf("%d%d", &p[i].x, &p[i].y);

		}

		sort(p, p + n, cmp);

		LL ans = 0;

		for(int i = 0; i < n; i++)

		{

			int y = p[i].y;

			int x = sum(y + 1) + 1;

			ans += x % mod;

			add(y, x);

		}

		printf("%lld\n", ans % mod);

	}

    return 0;

}