本文将详细讲解以下内容:
直接看这道题目把:
详情看。
由于我们发现原数的范围过大(
≤
1
0
9
\leq 10^9
≤109),而我们求逆序对只需要知道每两个元素的相对大小关系,我们可以使用离散化的思想。
我们先讲离散化
离散化就是这种操作:保留一组长度为
n
n
n数据的大小关系,而使这组数据的值域缩小至
n
n
n以内。这样可以很方便的以数组下标进行操作。
比如(a[0]不存):
a[7]={0, 3, 34, 8, 34, 7, 10}
离散化后这六个元素会变为
b[7]={0, 1, 5, 3, 5, 2, 4}
我们就这样完成了离散化的操作!
下面介绍离散化的两种方法(我个人喜欢第2种)
我们假设要将 n n n个数 a [ 1.. n ] a[1..n] a[1..n]( a [ i ] ≤ 1 0 9 a[i]\leq 10^9 a[i]≤109)离散化
#include<algorithm>
int n;
int a[MAXN];
int b[MAXN];
int id[MAXN];
int cntv;
bool cmp(int x, int y) {
return a[x] < a[y];
}
int main() {
//RS();
n = read();
for(rg int i = 1; i <= n; i++) a[i] = read(), id[i] = i;
std::sort(id + 1, id + 1 + n, cmp);
b[id[1]] = ++cntv;
for(rg int i = 2; i <= n; i++)
b[id[i]] = (a[id[i]] != a[id[i - 1]]) ? ++cntv : cntv;
//To do sth
return 0;
}
这样弄完后, b [ i ] b[i] b[i]就是离散化后的 a [ i ] a[i] a[i],且b的值域是 [ 1 , c n t v ] ∩ Z [1, cntv]\cap Z [1,cntv]∩Z
我们可以使用STL~
#include<algorithm>
int szb, n;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int main() {
szb = n = read();
Rep(i, 1, n) a[i] = b[i] = read();
std::sort(b + 1, b + n + 1);
szb = std::unique(b + 1, b + n + 1) - b - 1;
Rep(i, 1, n) c[i] = std::lower_bound(b + 1, b + 1 + szb, a[i]) - b;
//To do sth
return 0;
}
这样弄完后, c [ i ] c[i] c[i]就是离散化后的 a [ i ] a[i] a[i],且c的值域是 [ 1 , s z b ] ∩ Z [1, szb]\cap Z [1,szb]∩Z
我们考虑如何查找逆序对。
对于原序列(假设为
a
[
.
.
.
]
a[...]
a[...])中的每个数,它造成的逆序对贡献就是所有在它位置之前的、比它大的数的个数。
不难想到我们从前往后将原序列中的每个数插入一个数据结构,并统计此时比这个数大的数的个数。
我们需要每次询问
O
(
l
o
g
n
)
O(logn)
O(logn)完成的数据结构
我们要完成区间查询,单点修改。
我们可以使用权值线段树,或权值树状数组
其实就是把权值作为下标,进行插入。一般需要离散化,不然会MLE
详情看代码:
#define USEFASTERREAD 1
#define rg register
#define inl inline
#define DEBUG printf("qwq\n")
#define DEBUGd(x) printf("var %s is %lld", #x, ll(x))
#define DEBUGf(x) printf("var %s is %llf", #x, double(x))
#define putln putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
typedef unsigned long long ull;
#include<cstdio>
#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
namespace IO {
inl void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);}
inl ll read() {
ll x = 0, f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
return x * f;
}
inl void write(ll x) {
if(x < 0) {putchar('-'); x = -x;}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inl void writeln(ll x) {write(x), putln;}
inl void writesp(ll x) {write(x), putsp;}
}
using namespace IO;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x < 0 ? -x : x;}
#include<algorithm>
const int MAXN = 5e5 + 5;
int szb, n;
int a[MAXN];
int b[MAXN];
struct Segment_tree { //权值线段树
#define ls o << 1
#define rs o << 1 | 1
int l[MAXN << 2];
int r[MAXN << 2];
ll v[MAXN << 2];
//单点修改不用lazy_tag
void pushup(int o) {
v[o] = v[ls] + v[rs];
}
int len(int o) {return r[o] - l[o] + 1;}
void build(int o, int L, int R) {
l[o] = L, r[o] = R;
if(L == R) return;
int m = (L + R) >> 1;
build(ls, L, m);
build(rs, m + 1, R);
//建空树不用pushup
}
void add(int o, int x, ll k) {
if(l[o] == r[o]) {
v[o] += k;
return;
}
int m = (l[o] + r[o]) >> 1;
if(x <= m) add(ls, x, k);
else add(rs, x, k);
pushup(o);
}
ll sum(int o, int x, int y) {
if(x <= l[o] && r[o] <= y) return v[o];
int m = (l[o] + r[o]) >> 1;
ll ans = 0;
if(x <= m) ans += sum(ls, x, y);
if(y > m) ans += sum(rs, x, y);
return ans;
}
#undef ls
#undef rs
}tr;
ll ans;
int main() {
//RS();
szb = n = read();
Rep(i, 1, n) a[i] = b[i] = read();
std::sort(b + 1, b + n + 1);
szb = std::unique(b + 1, b + n + 1) - b - 1;
Rep(i, 1, n) a[i] = std::lower_bound(b + 1, b + 1 + szb, a[i]) - b;
tr.build(1, 1, n);
Rep(i, 1, n) {
tr.add(1, a[i], 1);
ans += tr.sum(1, a[i] + 1, szb);
}
writeln(ans);
return 0;
}
同理。
#define USEFASTERREAD 1
#define rg register
#define inl inline
#define DEBUG printf("qwq\n")
#define DEBUGd(x) printf("var %s is %lld", #x, ll(x))
#define DEBUGf(x) printf("var %s is %llf", #x, double(x))
#define putln putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
typedef unsigned long long ull;
#include<cstdio>
#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
namespace IO {
inl void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);}
inl ll read() {
ll x = 0, f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
return x * f;
}
inl void write(ll x) {
if(x < 0) {putchar('-'); x = -x;}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inl void writeln(ll x) {write(x), putln;}
inl void writesp(ll x) {write(x), putsp;}
}
using namespace IO;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x < 0 ? -x : x;}
#include<algorithm>
const int MAXN = 5e5 + 5;
int szb, n;
int a[MAXN];
int b[MAXN];
struct trarray {
ll t[MAXN];
static int lowbit(int x) {
return x & (-x);
}
void add(int x, ll k) {
for(rg int i = x; i <= szb; i += lowbit(i)) t[i] += k;
}
ll ask(int x) {
ll ans = 0;
for(rg int i = x; i; i -= lowbit(i)) ans += t[i];
return ans;
}
}tr;
ll ans;
int main() {
//RS();
szb = n = read();
Rep(i, 1, n) a[i] = b[i] = read();
std::sort(b + 1, b + n + 1);
szb = std::unique(b + 1, b + n + 1) - b - 1;
Rep(i, 1, n) a[i] = std::lower_bound(b + 1, b + 1 + szb, a[i]) - b;
Rep(i, 1, n) {
tr.add(a[i], 1);
ans += tr.ask(szb) - tr.ask(a[i]);
}
writeln(ans);
return 0;
}
为了防止权值线段树的权值值域过大且难以缩小(如题目强制在线而无法离散化),我们可以使用动态开点线段树。
什么叫动态开点?就是不会用到的点我不开,要用到的点就要用的时候临时开。
实现的时候,一般使用指针动态建树。但是为了减小常数、防止内存泄漏等诸多问题,我们一般会采用建立内存池、数组下标模拟指针的方法。(这种方法相当重要,以后学习平衡树等数据结构也常常用到)
其实实现不难,但是常数有点大(搞得我TLE了几个点)
#define USEFASTERREAD 1
#define rg register
#define inl inline
#define DEBUG printf("qwq\n")
#define DEBUGd(x) printf("var %s is %lld", #x, ll(x))
#define DEBUGf(x) printf("var %s is %llf", #x, double(x))
#define putln putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
typedef unsigned long long ull;
#include<cstdio>
#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
namespace IO {
inl void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);}
inl ll read() {
ll x = 0, f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
return x * f;
}
inl void write(ll x) {
if(x < 0) {putchar('-'); x = -x;}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inl void writeln(ll x) {write(x), putln;}
inl void writesp(ll x) {write(x), putsp;}
}
using namespace IO;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x < 0 ? -x : x;}
#include<algorithm>
#include<cstring>
#define Clear(arr) memset(arr, 0x00, sizeof arr)
const int MAXN = 5e5 + 5;
const int MAXV = 1e9 + 7;
int n;
ll a[MAXN];
struct Segment_tree {
int ls[7000005];
int rs[7000005];
ll v[7000005];
int cnt;
//动态开点.(上面的可以理解成内存池)
Segment_tree() {
Clear(ls), Clear(rs), Clear(v);
cnt = 1;//先把第一个点建好
}
int crenode() {
++cnt;
v[cnt] = ls[cnt] = rs[cnt] = 0;
return cnt;
}
void pushup(int o) {
v[o] = v[ls[o]] + v[rs[o]];
}
void modify(int o, ll l, ll r, ll x) {
if(l == r) {
v[o]++;
return;
}
ll m = (l + r) >> 1;
if(x <= m) {
if(!ls[o]) ls[o] = crenode();
modify(ls[o], l, m, x);
} else {
if(!rs[o]) rs[o] = crenode();
modify(rs[o], m + 1, r, x);
}
pushup(o);
}
ll ask(int o, ll l, ll r, ll x, ll y) {
if(!o) return 0;
if(x <= l && r <= y) return v[o];
ll m = (l + r) >> 1;
ll ans = 0;
if(x <= m) ans += ask(ls[o], l, m, x, y);
if(y > m) ans += ask(rs[o], m + 1, r, x, y);
return ans;
}
}tr;
ll ans;
int main() {
//RS();
n = read();
Rep(i, 1, n) a[i] = read();
for(rg int i = 1; i <= n; i++) {
tr.modify(1, 1, MAXV, a[i]);
ans += tr.ask(1, 1, MAXV, a[i] + 1, MAXV);
}
writeln(ans);
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁