题目:题目链接
题意:有两排城市,这两排之间有一些城市之间有连接的道路,给出所有道路,问有多少道路是相交的。
分析:求逆序数。我们先把所有的道路按照a升序,a相同时b升序的方法排列。这样从头至尾便利,对于每条道路,
我们只需要知道它之前有多少道路的b大于它的b就可以了,所以我们只要知道前面有多少b小于等于它的再用下标减
去就可以了。而这个求有多少小于等于的过程就用树状数组来实现。我们每看到一条边,就把它的b作为下标,把树
状数组对应位进行修改。这样一来,树状数组所有下标小于等于该道路的b的数的总和就是我们要求的b小于等于该道
路的道路数。
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } #define maxn 2005 struct node { int a, b; } way[maxn * maxn]; int n, m, k, c[maxn]; __int64 ans; bool cmp(const node &a, const node &b) { if (a.a != b.a) return a.a < b.a; return a.b < b.b; } __int64 cal(int a) { __int64 sum = 0; while (a > 0) { sum += c[a]; a -= (a&-a); } return sum; } void modify(int a, int x) { while (a <= m) { c[a] += x; a += (a & -a); } } void work() { ans = 0; for (int i = 0; i < k; i++) { ans += i - cal(way[i].b); modify(way[i].b, 1); } } int main() { int t; scanf("%d", &t); for (int i = 0; i < t; i++) { memset(c, 0, sizeof(c)); scanf("%d%d%d", &n, &m, &k); for (int j = 0; j < k; j++) scanf("%d%d", &way[j].a, &way[j].b); sort(way, way + k, cmp); work(); printf("Test case %d: %I64d\n", i + 1, ans); } return 0; }