逆序數對
題目連結
這是要求逆序數對的兩個數字的和，總共卡了兩個地方：
- TLE 計算和的複雜度爆了
- WA 數字溢位後爆了
第一點的解決方式：對於每一層利用O(N)的時間算前墜和
第二點的解決方式：每做完一個運算就mod 一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int ans = 0,n,arr[N],pre[N];
void merge_sort(int l,int r){
if(r-l<=1)return;
int mid = (l+r)/2;
merge_sort(l,mid);
merge_sort(mid,r);
int nl = l,nr = mid,ind = 0,temp[r-l];
pre[l-1] = 0;
for(int i=l;i<=mid;++i)pre[i] = pre[i-1]+arr[i];
for(;nl<mid;nl++,ind++){
while(arr[nr]<arr[nl] && nr<r){
int times = mid-nl;
ans+=pre[mid-1]-pre[nl-1];
ans+=arr[nr]*times;
ans = ans%10000019;
temp[ind] = arr[nr];
nr++;ind++;
}
temp[ind] = arr[nl];
}
while(nr<r){
temp[ind] = arr[nr];
nr++;ind++;
}
for(int i=0;i<r-l;++i)arr[i+l] = temp[i];
}
signed main(){
cin>>n;
memset(arr, 0, sizeof(arr));
for(int i=1;i<=n;++i)scanf("%lld",&arr[i]);
merge_sort(1,n+1);
printf("%lld\n",ans%10000019);
}
|