首页 > 代码库 > POJ3067 树状数组+逆序数

POJ3067 树状数组+逆序数

2024-07-05 19:47:16   229人阅读

设两线段为(x1,y1) ,(x2,y2), 若使两线段相交，需使x1<x2&&y1>y2||x1>x2&&y1<y2.

那么本题就变得很简单了，对东边点x从小到大排序，当x相等时对西边点y从小到大排序，每插入一条线段，就求一下逆序对数。总和即为答案。

代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define MAXH 1005
 5 using namespace std;
 6 
 7 int n, m, k;
 8 struct mem{
 9     int x,y;              
10 }a[MAXH*MAXH];
11 
12 int c[1005];
13 bool cmp(mem a,mem b)                            
14 {
15     if(a.x==b.x) return a.y<b.y;
16     return a.x<b.x;
17 }
18 
19 int lowbit(int x)
20 {
21     return x&(-x);
22 }
23 
24 void add(int x)
25 {
26     while(x<=m)
27     {
28         c[x]++;
29         x+=lowbit(x);
30     }
31 }
32 
33 int sum(int x)
34 {
35     int mm=0;
36     while(x>0)
37     {
38         mm+=c[x];
39         x-=lowbit(x);
40     }
41     return mm;
42 }
43 
44 main()
45 {
46     int i, j, kk=1;
47     __int64 ans;
48     int t;
49     scanf("%d",&t);
50     while(t--)
51     {
52         memset(c,0,sizeof(c));
53         scanf("%d %d %d",&n,&m,&k);
54         for(i=0;i<k;i++)
55         scanf("%d %d",&a[i].x,&a[i].y);
56         sort(a,a+k,cmp);
57         ans=0;
58         for(i=0;i<k;i++)
59         {
60             ans+=sum(m)-sum(a[i].y);
61             add(a[i].y);
62         }
63         printf("Test case %d: %I64d\n",kk++,ans);
64     }
65 }

 


联系
我们