TVP

# 洛谷P1966 火柴排队(逆序对)

attack

4290

### Sol

``````#include<bits/stdc++.h>
#define lb(x) (x & -x)
#define Fin(x) {freopen(#x".in", "r", stdin);}
using namespace std;
const int MAXN = 1e5 + 10, mod = 99999997;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, a[MAXN], b[MAXN], pos[MAXN], rak[MAXN], date[MAXN], T[MAXN];
void Get(int *a) {
memcpy(date, a, sizeof(a) * (N + 1));
sort(date + 1, date + N + 1);
int num = unique(date + 1, date + N + 1) - date - 1;
for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date;
}
void Add(int x, int val) {
while(x <= N) T[x] += val, x += lb(x);
}
int Query(int pos) {
int ans = 0;
while(pos) ans += T[pos], pos -= lb(pos);
return ans;
}
int add(int x, int y) {
if(x + y < 0) return x + y + mod;
else return (x + y >= mod) ? x + y - mod : x + y;
}
signed main() {
for(int i = 1; i <= N; i++) a[i] = read();
for(int i = 1; i <= N; i++) b[i] = read();
Get(a); Get(b);
for(int i = 1; i <= N; i++) pos[a[i]] = i;
for(int i = 1; i <= N; i++) rak[i] = pos[b[i]];
int ans = 0;
for(int i = 1; i <= N; i++)
Add(rak[i], 1), ans = add(ans, i - Query(rak[i]));
printf("%d", ans);
return 0;
}``````

0 条评论

LV.

• 题意
• Sol