POJ 3067 Japan (树状数组求逆序对）

题意：有（1-n）个城市自上到下在左边，另有（1-m）个城市自上到下在右边，共有m条高速公路，现求这m条直线的交点个数，交点不包括在城市处相交。

题解：先将高速公路读入，然后按照左边城市序号小的在前，左边序号相同的按照右边城市序号小的在前，然后根据右边的城市序号求逆序数就可以解决了。因为当处理一条边的时候，这条边一定会和左边序号小于它的且右边序号大于它的边有一个交点。

代码：

没想到cin, cout 关了同步流也T了，然后答案应该是爆int了，平常不怎么用printf 导致答案改成ll之后还是用%d输出，检查了好久才发现输出写错了，改成%lld就A了，气！

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #define ll long long
 6 #define fi first
 7 #define se second
 8 using namespace std;
 9 const int N = 1000+5;
10 ll tree[N];
11 int n, m, T, q;
12 pair<int, int> P[N*N];
13 int lowbit(int x)
14 {
15     return x&(-x);
16 }
17 void Add(int x)
18 {
19     while(x <= m)
20     {
21         tree[x]++;
22         x += lowbit(x);
23     }
24 }
25 ll Query(int x)
26 {
27     ll ret = 0;
28     while(x > 0)
29     {
30         ret += tree[x];
31         x -= lowbit(x);
32     }
33     return ret;
34 }
35 int main()
36 {
37     scanf("%d",&T);
38     for(int Case = 1; Case <= T; Case++)
39     {
40         scanf("%d%d%d",&n,&m,&q);
41         //cin >> n >> m >> q;
42         for(int i = 0; i < q; i++)
43             scanf("%d%d",&P[i].fi, &P[i].se);
44             //cin >> P[i].fi >> P[i].se;
45         sort(P, P+q);
46         memset(tree, 0, sizeof(tree));
47         ll ans = 0;
48         for(int i = 0; i < q; i++)
49         {
50             ans += Query(m) - Query(P[i].se);
51             Add(P[i].se);
52         }
53         printf("Test case %d: %lld
",Case, ans);
54         //cout << "Test case " << Case << ": " << ans << endl;
55     }
56     return 0;
57 }