P1908 逆序对

题意

求逆序对的数量。数组的元素可以非常大。

思路

离散化后使用权值线段树即可。

个人理解,权值线段树本质上是使用线段树维护元素出现数量的数据结构,

和线段树没有本质区别。

加入最大元素时,不要进行区间长度为 0 的查询!会 RE!

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define fori(n) for (ll i = 0; i < n; i++)
#define forj(n) for (ll j = 0; j < n; j++)
#define rofi(n) for (ll i = n - 1; i >= 0; i--)
#define rofj(n) for (ll j = n - 1; j >= 0; j--)
const ll N = 500004;
const ll M = 1000001011;
ll n;

// dis
ll b[N], b0[N];
void dis() {
  std::sort(b0, b0 + n);
  ll n1 = std::unique(b0, b0 + n) - b0;
  fori(n) b[i] = std::lower_bound(b0, b0 + n1, b[i]) - b0;
}

// seg
ll a[N << 2];
ll t[N << 2];
ll mid(ll l, ll r) { return l + (r - l) / 2; }
void pull(ll p) { a[p] = a[p << 1] + a[p << 1 | 1]; }
void push(ll l, ll r, ll p) {
  if (r - l != 1) {
    ll m = mid(l, r);
    a[p << 1] += t[p] * (m - l);
    a[p << 1 | 1] += t[p] * (r - m);
    t[p << 1] += t[p];
    t[p << 1 | 1] += t[p];
  }
  t[p] = 0;
}
void add(ll lq, ll rq, ll b, ll l = 0, ll r = n, ll p = 1) {
  push(l, r, p);
  if (lq <= l && rq >= r) {
    a[p] += (r - l) * b;
    t[p] += b;
  } else {
    ll m = mid(l, r);
    if (lq < m)
      add(lq, rq, b, l, m, p << 1);
    if (rq > m)
      add(lq, rq, b, m, r, p << 1 | 1);
    pull(p);
  }
}
ll query(ll lq, ll rq, ll l = 0, ll r = n, ll p = 1) {
  ll f = 0;
  push(l, r, p);
  if (lq <= l && rq >= r) {
    f = a[p];
  } else {
    ll m = mid(l, r);
    if (lq < m)
      f += query(lq, rq, l, m, p << 1);
    if (rq > m)
      f += query(lq, rq, m, r, p << 1 | 1);
  }
  return f;
}

// main
ll f;
void work(ll i) {
  add(b[i], b[i] + 1, 1);
  ll f0 = b[i] + 1 == n ? 0 : query(b[i] + 1, n);
  f += f0;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n;
  fori(n) std::cin >> b0[i];
  fori(n) b[i] = b0[i];
  dis();
  f = 0;
  fori(n) work(i);
  std::cout << f << '\n';
  return 0;
}

P1637 三元上升子序列

题意

求三元上升子序列的个数。

思路

用一个权值线段树维护每个数字出现的次数,

对于每个二元上升子序列,考虑采用较大的数来代表这个数列,

因此可以使用另一个权值线段树维护每个二元上升子序列出现的次数,

因此可以计算出三元上升子序列的数量。

本题不需要离散化。

线段树的总长 n 需要额外赋值。

感觉这种要求程序员记得对某个全局变量复制的做法并不是很好……

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define fori(n) for (ll i = 0; i < n; i++)
#define forj(n) for (ll j = 0; j < n; j++)
#define rofi(n) for (ll i = n - 1; i >= 0; i--)
#define rofj(n) for (ll j = n - 1; j >= 0; j--)
const ll N = 100004;
const ll M = 1000001011;
ll n;
ll n0, a0[N];

struct seg {
  ll a[N << 2];
  ll t[N << 2];
  inline ll mid(ll l, ll r) { return l + (r - l) / 2; }
  inline void pull(ll p) { a[p] = a[p << 1] + a[p << 1 | 1]; }
  inline void push(ll l, ll r, ll p) {
    if (r - l != 1) {
      ll m = mid(l, r);
      a[p << 1] += t[p] * (m - l);
      a[p << 1 | 1] += t[p] * (r - m);
      t[p << 1] += t[p];
      t[p << 1 | 1] += t[p];
    }
    t[p] = 0;
  }
  inline void add(ll lq, ll rq, ll b, ll l = 0, ll r = n, ll p = 1) {
    push(l, r, p);
    if (lq <= l && rq >= r) {
      a[p] += (r - l) * b;
      t[p] += b;
    } else {
      ll m = mid(l, r);
      if (lq < m)
        add(lq, rq, b, l, m, p << 1);
      if (rq > m)
        add(lq, rq, b, m, r, p << 1 | 1);
      pull(p);
    }
  }
  inline ll query(ll lq, ll rq, ll l = 0, ll r = n, ll p = 1) {
    ll f = 0;
    push(l, r, p);
    if (lq <= l && rq >= r) {
      f = a[p];
    } else {
      ll m = mid(l, r);
      if (lq < m)
        f += query(lq, rq, l, m, p << 1);
      if (rq > m)
        f += query(lq, rq, m, r, p << 1 | 1);
    }
    return f;
  }
} s[2];

ll f;
inline void work(ll i) {
  s[0].add(a0[i], a0[i] + 1, 1);
  ll q = s[0].query(0, a0[i]);
  s[1].add(a0[i], a0[i] + 1, q);
  ll q2 = s[1].query(0, a0[i]);
  f += q2;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n0;
  n = N;
  fori(n0) std::cin >> a0[i];
  fori(n0) work(i);
  std::cout << f << '\n';
  return 0;
}

P6186 [NOI Online #1 提高组] 冒泡排序

题意

给定一个排列,有两种操作:

  • 交换相邻两数
  • 询问经过 kk 轮冒泡排序后有多少逆序对

数组长度 2×1052 \times 10^5kk 可以很大。

思路

显然不能对 kk 线性模拟,我们需要找到冒泡排序和逆序对数量的关系。

容易证明,冒泡排序中每交换一次就少一个逆序对,所以用线段树维护交换

但交换的结果受交换发生的顺序影响。

因此,不考虑维护交换,而考虑维护逆序对,

用逆序对右端点代表整个逆序对,这样一些逆序对会叠在一起,其数量成为权值,

那么用权值线段树维护逆序对,

但想半天也想不到逆序对在冒泡排序下有什么规律

手工模拟得知,每次交换后全部逆序对会左移一格,并且权值减一,直到为 0 为止。

因此以逆序对位置为横轴,权值为纵轴建立线段树,但我要怎么实现 max(x-k, 0) 呢?

如果将线段树以柱状图形式画出来,我们会得到类似于这样的东西:

^
4         |
3       | |
2     | | |
1     | | |
x 0 1 2 3 4 >

那么我们每次查询时,实质上是在查询一个矩形区间内的和,而没有涉及 max 操作。

例如,查询 x[0,4],k=2x \in [0, 4], k = 2,涉及如下区间:

^
4 - - - - +
3 - - - + +
2     | | |
1     | | |
x 0 1 2 3 4 >

因此反转横轴和纵轴即可,我们会得到这样的结果:

^
4 - -
3 - - -
2 - - - -
1
0
x 1 2 3 4 >

由于我们并不在乎逆序对的位置,可以对纵轴计数:

y 3 3 2 1
x 1 2 3 4

要求 k=2k = 2 的情况,只需求 [3,4][3, 4] 的区间和即可。

事实上,由于逆序对的位置并不重要,最初就不应该用这个属性来建立线段树。

维护数据

  • 数组 p / 排列
  • 数组 b / 位置 -> 位置权值
  • 树状数组 fen::a / 数字 -> 数字权值
  • 线段树 seg::a / 位置权值 -> 权值权值前缀和

  • 要格外注意线段树访问不要越界!
    • 其实应该修一下线段树模板
  • 注意求逆序对的时候加的区间应该是数后面的区间,而不是前面的!

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define fori(n) for (ll i = 0; i < n; i++)
#define forj(n) for (ll j = 0; j < n; j++)
#define rofi(n) for (ll i = n - 1; i >= 0; i--)
#define rofj(n) for (ll j = n - 1; j >= 0; j--)
const ll N = 200004;
const ll M = 1000001011;
ll n, p[N], b[N], m, t, c;

namespace fen {
ll a[N];
void add(ll p, ll b) {
  for (; p <= n; p += p & -p)
    a[p] += b;
}
ll query(ll p) {
  ll f = 0;
  for (; p > 0; p -= p & -p)
    f += a[p];
  return f;
}
} // namespace fen

namespace seg {
ll a[N << 2];
ll t[N << 2];
inline ll mid(ll l, ll r) { return l + (r - l) / 2; }
inline void pull(ll p) { a[p] = a[p << 1] + a[p << 1 | 1]; }
inline void push(ll l, ll r, ll p) {
  if (r - l != 1) {
    ll m = mid(l, r);
    a[p << 1] += t[p] * (m - l);
    a[p << 1 | 1] += t[p] * (r - m);
    t[p << 1] += t[p];
    t[p << 1 | 1] += t[p];
  }
  t[p] = 0;
}
inline void add(ll lq, ll rq, ll b, ll l = 0, ll r = n + 1, ll p = 1) {
  push(l, r, p);
  if (lq <= l && rq >= r) {
    a[p] += (r - l) * b;
    t[p] += b;
  } else {
    ll m = mid(l, r);
    if (lq < m)
      add(lq, rq, b, l, m, p << 1);
    if (rq > m)
      add(lq, rq, b, m, r, p << 1 | 1);
    pull(p);
  }
}
inline ll query(ll lq, ll rq, ll l = 0, ll r = n + 1, ll p = 1) {
  ll f = 0;
  push(l, r, p);
  if (lq <= l && rq >= r) {
    f = a[p];
  } else {
    ll m = mid(l, r);
    if (lq < m)
      f += query(lq, rq, l, m, p << 1);
    if (rq > m)
      f += query(lq, rq, m, r, p << 1 | 1);
  }
  return f;
}
} // namespace seg

void work() {
  std::cin >> t >> c;
  if (t == 1) {
    ll x = p[c - 1];
    ll y = p[c];
    ll z = b[c - 1];
    ll w = b[c];
    p[c - 1] = y;
    p[c] = x;
    if (x > y) {
      b[c - 1] = w - 1;
      b[c] = z;
      seg::add(w, w + 1, -1);
    } else {
      b[c - 1] = w;
      b[c] = z + 1;
      seg::add(z + 1, z + 2, 1);
    }
  } else {
    if (c + 1 >= n + 1) {
      std::cout << 0 << '\n';
    } else {
      std::cout << seg::query(c + 1, n + 1) << '\n';
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n >> m;
  fori(n) {
    std::cin >> p[i];
    fen::add(p[i], 1);
    b[i] = fen::query(n) - fen::query(p[i]);
    if (b[i] >= 1) {
      seg::add(1, b[i] + 1, 1);
    }
  }
  fori(m) { work(); }
  return 0;
}