Algorithm

Task

Given a sequence of length \(n\), support for single point modification and interval \(kth\) queries is required to force online.

Limitation

If the input data is considered to be all of the same order as \(n\), the space-time complexity of the algorithm is required \(O(n \log^2n)\)

Solution

In fact, there is no half-money relationship between this thing and the persistent segment tree, essentially it is the tree array hedge segment tree

Consider that if you don't have repairs, you can solve them directly from the chairman tree.The essence of a presidential tree is to maintain a segment tree of prefix weights from \(1\) to each location.

If the President Tree is violent, the single change is \(O(n \log n)\), resulting in GG.

Consider dividing the weight segment tree of a prefix into multiple segments, and adding these weight segment trees together is the total prefix weight segment tree.If the segment is divided into \(O(T)\, then the modification complexity will be \(O(T\log n)\).Note that each segment divided into multiple segments here is a normal weight segment tree within the interval, not a chair tree.

Consider using a tree array to maintain this prefix, then each prefix interval can be divided into \(O(\log n)\) segments, each of which is the weight segment tree of the corresponding interval, so that the complexity of the single modification is \(O(\log^2n)\).

Consider the query prefix, just find out the \(O(\log n)\) prefixes and divide them together.Time Complexity\(O(\log^2n)\)

Thus, total time complexity\(O(n \log^2n)\) can achieve spatial complexity\(O(n \log^2n)\) using dynamic starting points.

Sample

Description

Given a sequence of length \(n\), there are \(m\) operations, either a single modification or a query interval \(kth\).

Limitation

\(1 \leq n,~m \leq 10^5\)

Series range in \(10^9\)

Solution

What Solution to board title

Code

My code constant is so big...It's twice the @DDOSvoid constant...The perception constant is greater than the STD of \(O(\log n)\) nodes stored in the query: on the vectors, it would be much faster to change to handwriting...

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

const int maxn = 100005;

int n, m, upceil;
int MU[maxn];
std::vector<int>tmp;

struct Tree {
  Tree *ls, *rs;
  int v;

  Tree() : ls(NULL), rs(NULL), v(0) {}
};
Tree *rot[maxn];

struct Ask {
  char ch;
  int a, b, c;
};
Ask ask[maxn];

void init_hash();
void update(int p, const int v);
int Query(int l, int r, int k);
void Update(const int p, const int v);
void query(std::vector<int> &a, int &v);
void update(Tree *const u, const int l, const int r, const int p, const int v);

int main() {
  freopen("1.in", "r", stdin);
  qr(n); qr(m);
  rot[0] = new Tree;
  for (int i = 1; i <= n; ++i) {
    rot[i] = new Tree;
    qr(MU[i]);
  }
  char ch; int a, b, c;
  for (int M = 1; M <= m; ++M) {
    do ch = IPT::GetChar(); while ((ch != 'Q') && (ch != 'C'));
    if (ch == 'Q') {
      a = b = c = 0; qr(a); qr(b); qr(c);
    } else {
      a = b = 0; qr(a); qr(b);
    }
    ask[M] = {ch, a, b, c};
  }
  init_hash();
  for (int i = 1; i <= n; ++i) {
    update(i, 1);
  }
  for (int i = 1; i <= m; ++i) {
    ch = ask[i].ch; a = ask[i].a; b = ask[i].b; c = ask[i].c;
    if (ch == 'Q') {
      qw(Query(a, b, c), '\n', true);
    } else {
      Update(a, b);
    }
  }
  return 0;
}

void init_hash() {
  for (int i = 1; i <= n; ++i) tmp.push_back(MU[i]);
  for (int i = 1; i <= m; ++i) if (ask[i].ch == 'C') {
    tmp.push_back(ask[i].b);
  }
  std::sort(tmp.begin(), tmp.end());
  upceil = std::unique(tmp.begin(), tmp.end()) - tmp.begin();
  auto ed = tmp.begin() + upceil;
  for (int i = 1; i <= n; ++i) {
    MU[i] = std::lower_bound(tmp.begin(), ed, MU[i]) - tmp.begin() + 1;
  }
  for (int i = 1; i <= m; ++i) if (ask[i].ch == 'C') {
    ask[i].b = std::lower_bound(tmp.begin(), ed, ask[i].b) - tmp.begin() + 1;
  }
}

inline int lowbit(const int x) { return x & -x; }

void update(int p, const int v) {
  int pv = MU[p];
  do update(rot[p], 1, upceil, pv, v); while ((p += lowbit(p)) <= n);
}

void update(Tree *const u, const int l, const int r, const int p, const int v) {
  u->v += v;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid) {
    update(u->ls ? u->ls : u->ls = new Tree, l, mid, p, v);
  } else {
    update(u->rs ? u->rs : u->rs = new Tree, mid + 1, r, p, v);
  }
}

void Update(const int p, const int v) {
  update(p, -1);
  MU[p] = v;
  update(p, 1);
}

void query(std::vector<Tree*> &a, int &v) {
  if (!a.size()) return;
  for (auto u : a) if (u->ls) {
    v += u->ls->v;
  }
}

void cls(std::vector<Tree*> &a, std::vector<Tree*> &b) {
  for (auto u : a) if (u->ls) {
    b.push_back(u->ls);
  }
}

void crs(std::vector<Tree*> &a, std::vector<Tree*> &b) {
  for (auto u : a) if (u->rs) {
    b.push_back(u->rs);
  }
}

int Query(int l, int r, int k) {
  int tl = 1, tr = upceil; --l;
  std::vector<Tree*> vl[2], vr[2];
  int key = 0, tk = 1;
  do vr[0].push_back(rot[r]); while (r -= lowbit(r));
  do vl[0].push_back(rot[l]); while (l -= lowbit(l));
  while (tl != tr) {
    int mid = (tl + tr) >> 1;
    int s1 = 0, s2 = 0;
    query(vr[key], s1); query(vl[key], s2);
    int sum = s1 - s2;
    if (sum >= k) {
      cls(vr[key], vr[tk]);
      cls(vl[key], vl[tk]);
      tr = mid;
    } else {
      crs(vr[key], vr[tk]);
      crs(vl[key], vl[tk]);
      tl = mid + 1;
      k -= sum;
    }
    vr[key].clear(); vl[key].clear();
    std::swap(key, tk);
  }
  return tmp[tl - 1];
}