Program match;
Const
nn = 100001;
standard = 99999997;
Var
a, b, c, hash, ha, hb, s: Array [1..nn] of Longint;
i, n, x, ans: Longint;
Procedure qsort(l, r: Longint);
Var
i, j, x, t: Longint;
Begin
i:= l; j:= r; x:= a[(i+j) Div 2];
Repeat
While a[i] < x Do Inc(i);
While a[j] > x Do Dec(j);
If i <= j Then Begin
t:= a[i]; a[i]:= a[j]; a[j]:= t;
Inc(i); Dec(j);
End;
Until i > j;
If l < j Then qsort(l, j);
If i < r Then qsort(i, r);
End;
Procedure add(x, y: Longint);
Begin
While x <= n Do Begin
Inc(s[x], y);
Inc(x, x And -x);
End;
End;
Function check(x: Longint): Longint;
Var
sum: Longint;
Begin
sum:= 0;
While x > 0 Do Begin
Inc(sum, s[x]);
Dec(x, x And -x);
End;
Exit(sum);
End;
Begin
Fillchar(s, Sizeof(s), 0);
ReadLn(n);
For i:= 1 To n Do Begin
Read(a[i]);
b[i]:= a[i];
End;
Readln;
qsort(1, n);
For i:= 1 To n Do hash[a[i]]:= i;
For i:= 1 To n Do ha[i]:= hash[b[i]];
For i:= 1 To n Do Begin
Read(a[i]);
b[i]:= a[i];
End;
qsort(1, n);
For i:= 1 To n Do hash[a[i]]:= i;
For i:= 1 To n Do hb[i]:= hash[b[i]];
For i:= 1 To n Do hash[ha[i]]:= i;
For i:= 1 To n Do c[i]:= hash[hb[i]];
For i:= 1 To n Do Begin
add(c[i], 1);
Inc(ans, i-check(c[i]));
ans:= ans Mod standard;
End;
WriteLn(ans);
End.
2 条评论
-
hzfsbit_noip LV 8 @ 2014-06-18 08:11:31
//{HEADS
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <string>
#define REP(i,j) for(int i=1;i<=j;++i)
#define REPI(i,j,k) for(int i=j;i<=k;++i)
#define REPD(i,j) for(int i=j;0<i;--i)
#define STLR(i,con) for(int i=0,sz=con.size();i<sz;++i)
#define STLRD(i,con) for(int i=con.size()-1;0<=i;--i)
#define CLR(s) memset(s,0,sizeof s)
#define SET(s,v) memset(s,v,sizeof s)
#define mp make_pair
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef double DB;
typedef pair<int,int> i_pair;
const int INF = 0x3f3f3f3f;
const long long INFL = 0x3f3f3f3f3f3f3f3f;
//}const int maxn = 100000 + 100;
const int mod = 99999997;int A[maxn],B[maxn],C[maxn],p[maxn],q[maxn],f[maxn],n,ans;
inline int lowbit(int x) {
return x&-x;
}
bool cmp_A(int i,int j) {
return A[i]<A[j];
}
bool cmp_B(int i,int j) {
return B[i]<B[j];
}int get_sum(int x) {
int ret=0;
while(0<x) {
ret+=C[x];
x-=lowbit(x);
}
return ret;
}
void change(int x) {
while(x<=n) {
C[x]++;
x+=lowbit(x);
}
}int main() {
/*FILE{*/
#ifndef ONLINE_JUDGE
string FILE_NAME = "match";
freopen((FILE_NAME+".in").c_str(),"r",stdin);
freopen((FILE_NAME+".out").c_str(),"w",stdout);
#endif/*}*/scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&A[i]);
p[i]=i;
}
for(int i=1;i<=n;++i) {
scanf("%d",&B[i]);
q[i]=i;
}
sort(p+1,p+n+1,cmp_A);
sort(q+1,q+n+1,cmp_B);
for(int i=1;i<=n;++i) {
f[q[i]]=p[i];
}
/*
for(int i=1;i<=n;++i) {
printf("%d ",f[i]);
}
puts("");
*/
ans=0;
for(int i=1;i<=n;++i) {
ans=(ans+(i-1-get_sum(f[i]-1)))%mod;
change(f[i]);
}
printf("%d\n",ans);return 0;
} -
@ 2014-06-18 08:10:11
//{HEADS #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <ctime> #include <algorithm> #include <iostream> #include <fstream> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <complex> #include <string> #define REP(i,j) for(int i=1;i<=j;++i) #define REPI(i,j,k) for(int i=j;i<=k;++i) #define REPD(i,j) for(int i=j;0<i;--i) #define STLR(i,con) for(int i=0,sz=con.size();i<sz;++i) #define STLRD(i,con) for(int i=con.size()-1;0<=i;--i) #define CLR(s) memset(s,0,sizeof s) #define SET(s,v) memset(s,v,sizeof s) #define mp make_pair #define pb push_back #define x first #define y second using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> i_pair; const int INF = 0x3f3f3f3f; const long long INFL = 0x3f3f3f3f3f3f3f3f; //} const int maxn = 100000 + 100; const int mod = 99999997; int A[maxn],B[maxn],C[maxn],p[maxn],q[maxn],f[maxn],n,ans; inline int lowbit(int x) { return x&-x; } bool cmp_A(int i,int j) { return A[i]<A[j]; } bool cmp_B(int i,int j) { return B[i]<B[j]; } int get_sum(int x) { int ret=0; while(0<x) { ret+=C[x]; x-=lowbit(x); } return ret; } void change(int x) { while(x<=n) { C[x]++; x+=lowbit(x); } } int main() { /*FILE{*/ #ifndef ONLINE_JUDGE string FILE_NAME = "match"; freopen((FILE_NAME+".in").c_str(),"r",stdin); freopen((FILE_NAME+".out").c_str(),"w",stdout); #endif/*}*/ scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&A[i]); p[i]=i; } for(int i=1;i<=n;++i) { scanf("%d",&B[i]); q[i]=i; } sort(p+1,p+n+1,cmp_A); sort(q+1,q+n+1,cmp_B); for(int i=1;i<=n;++i) { f[q[i]]=p[i]; } /* for(int i=1;i<=n;++i) { printf("%d ",f[i]); } puts(""); */ ans=0; for(int i=1;i<=n;++i) { ans=(ans+(i-1-get_sum(f[i]-1)))%mod; change(f[i]); } printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 1842
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5085
- 已通过
- 1102
- 通过率
- 22%
- 被复制
- 10
- 上传者
-
Towerlight
