首页 > 代码库 > HDU 4417 类似求逆序数的树状数组

HDU 4417 类似求逆序数的树状数组

2024-07-12 23:38:15   229人阅读

Super Mario

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2250    Accepted Submission(s): 1092


Problem Description
Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.
 

 

Input
The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)
 

 

Output
For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.
 

 

Sample Input
1
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3
 

 

Sample Output
Case 1:
4
0
0
3
1
2
0
1
5
1
 
 
 
 
题目大意：
给定两个数n, m分别为数组长度，操作次数。给定长度n的数组序列，然后m次操作，每次操作输入l  r  v   分别代表查询数组l---r区间段中比v小的数的数目。
 
先说说逆序数，在数组a中若有i<j&&a[i]>a[j] 则称之为逆序数对。求的方法是数组从左到右依次插入树状数组中，到第i个元素时，第i个元素前面的数和a[i]构成的逆序对数目为
sum[MAX]-sum[i],其中sum[MAX]为i前面数组元素>0&&<=MAX数的数目，sum[i]为前面数组元素>0&&<=i的数目，两者相减不就是i前面数组中大于a[i]的数的数目了吗，
对数组所有元素进行上述操作相加即为该数组逆序对总数。
 
 
对于本题，假设某次操作中输入l、r、v。  有种方法，先找出所有小于v的元素，然后找出这些元素中id在[l,r]中的元素，其数目即为答案，找小于v的元素时很容易吧，但是怎么找这些元素中id在[l,r]区间里的元素呢？就用到前面所说的知识了，每找一个小于v的元素，就把其在数组中的位置即id插入树状数组中，找完后，在[l,r]中元素的数目即为sum[r]-sum[r-1]。
 
运用这些知识就能写代码了 ，为了代码时间复杂度降低一些，代码中运用了一些排序小技巧，详见代码：
 
 
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 #define N 100005 7  8 int c[N]; 9 int ans[N];10 11 struct mem{12     int l, r;13     int val;14     int id;15 }a[N];16 17 struct node{18     int num;19     int id;20 }b[N];21 22 bool cmp1(mem a,mem b){23     return a.val<b.val;24 }25 26 bool cmp2(node a,node b){27     return a.num<b.num;28 }29 30 int lowbit(int x){31     return x&(-x);32 }33 34 void update(int x){35     while(x<N){36         c[x]++;37         x+=lowbit(x);38     }39 }40 41 int get_sum(int x){42     int ans=0;43     while(x>0){44         ans+=c[x];45         x-=lowbit(x);46     }47     return ans;48 }49 50 main()51 {52     int i, j, k, kase=1;53     int t;54     int n, m;55     cin>>t;56     while(t--){57         cin>>n>>m;58         memset(c,0,sizeof(c));59         for(i=1;i<=n;i++){60             scanf("%d",&b[i].num);61             b[i].id=i;62         }63         for(i=1;i<=m;i++){64             scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].val);65             a[i].l++;66             a[i].r++;67             a[i].id=i;68             ans[i]=0;69         }70         sort(a+1,a+m+1,cmp1);71         sort(b+1,b+n+1,cmp2);72         k=1;73         for(i=1;i<=m;i++){74             while(k<=n&&a[i].val>=b[k].num){75                 update(b[k].id);76                 k++;77             }78             ans[a[i].id]=get_sum(a[i].r)-get_sum(a[i].l-1);79         }80         printf("Case %d:\n",kase++);81         for(i=1;i<=m;i++)82         printf("%d\n",ans[i]);83     }84 }

 


联系
我们