Ultra-QuickSort

Input

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

1. #include"iostream"
2. #include"algorithm"
3. #include"cstring"
4. #include"cstdio"
5. using namespace std;
6. structxy
7. {
8.     int x,y;
9. }a[1000010];
10. int c[1005];
11. //long long int max;
12. int cmp(const xy&a,const xy&b)
13. {
14.     if(a.x!=b.x)
15.      return a.x<b.x;
16.     else
17.      return a.y<b.y;
18. }
19. int lowbit(int x)
20. {
21.     return x&(-x);
22. }
23. void updata(int x,int d,int max)
24. {
25.     while(x<=max)
26.     {
27.         c[x]+=d;
28.         x+=lowbit(x);
29.     }
30. }
31. long long int getsum(int x)
32. {
33.     long long int res=0;
34.     while(x>0)
35.     {
36.         res+=c[x];
37.         x-=lowbit(x);
38.     }
39.     return res;
40. }
41. int main()
42. {
43.     int i,t,p=0;
44.     scanf("%d",&t);
45.     while(t--)
46.     {
47.         int n,m,k,max;
48.         memset(c,0,sizeof(c));
49.         max=0;
50.         scanf("%d%d%d",&n,&m,&k);
51.         for(i=0;i<k;i++)
52.         {
53.             scanf("%d%d",&a[i].x,&a[i].y);
54.             if(a[i].y>max)
55.              max=a[i].y;
56.         }
57.         sort(a,a+k,cmp);
58.         long long int sum=0;
59.         updata(a[0].y,1,max);
60.         for(i=1;i<k;i++)
61.         {
62.             sum+=getsum(max)-getsum(a[i].y);
63.             updata(a[i].y,1,max);
64.         }
65.         printf("Test case %d: %lld\n",++p,sum);
66.     }
67.     return 0;
68. }

Ultra-QuickSort,布布扣,bubuko.com

Ultra-QuickSort

原文：http://www.cnblogs.com/767355675hutaishi/p/3683422.html