题目链接

BZOJ2957

题目概括

给定数列,单点修改,维护全局不同的前缀最大值个数。

思路要点

节点维护最大值和答案。

考虑递归合并答案,对于 $x$ 查找 $x$ 的右儿子后缀大于左区间的最长长度。

时间复杂度 $O(nlog^2n)$

代码

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

namespace FastIO {
char ibuf[1 << 21], *ip1 = ibuf, *ip2 = ibuf;
char obuf[1 << 21], *op1 = obuf, *op2 = op1 + (1 << 21) - 1;

inline char Getchar() {
  return ip1 == ip2 && (ip2 = (ip1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), ip1 == ip2) ? EOF : *ip1++;
}

inline void flush() {
  fwrite(obuf, 1, op1 - obuf, stdout), op1 = obuf;
}

inline void Putchar(char ch) {
  *op1++ = ch; 
  if (op1 == op2)
    flush();
}

#ifdef ONLINE_JUDGE
  #define getchar Getchar
  #define putchar Putchar
#endif

template <class T> 
void rd(T& x, int f = 1, char ch = 0) {
  for (f = 1, x = 0; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
  x *= f;
}

void read(int& x) { rd(x); }
void read(long long& x) { rd(x); }
void read(unsigned int& x) { rd(x); }
void read(unsigned long long& x) { rd(x); }

char sk[20];
int top;

template <class T> 
void pf(T x) {
  if (!x) 
    putchar('0');
  if (x < 0)
    putchar('-'), x = -x;
  while (x)
    sk[++top] = x % 10 + 48, x /= 10;
  while (top)
    putchar(sk[top--]);
}

void write(int x) { pf(x); }
void write(long long x) { pf(x); }
void write(unsigned int x) { pf(x); }
void write(unsigned long long x) { pf(x); }
void write(char x) { putchar(x); }

template <class T> 
void writeln(T x) {
  write(x);
  putchar('\n');
}

#ifdef ONLINE_JUDGE
struct Flush {
  ~Flush() {
    flush();
  }
} flusher; 
#endif
} 

using FastIO::read;
using FastIO::write;
using FastIO::writeln;

const int N = 1e5 + 5;

struct Frac {
  int x, y;

  Frac() { x = -1; }

  Frac(int a, int b) {
    x = a, y = b; 
  }

  bool operator<(const Frac& rhs) const {
    return (ll)x * rhs.y < (ll)y * rhs.x;
  }

  bool operator>(const Frac& rhs) const {
    return (ll)x * rhs.y > (ll)y * rhs.x;
  }

  bool operator==(const Frac& rhs) const {
    return (ll)x * rhs.y == (ll)y * rhs.x;
  }

  bool operator<=(const Frac& rhs) const {
    return *this < rhs || *this == rhs; 
  }

  bool operator>=(const Frac& rhs) const {
    return *this > rhs || *this == rhs; 
  }
};

struct Node {
  Frac max;
  int ans;
} tr[N << 2];

int find(int x, int l, int r, Frac val) {
  if (l == r) 
    return tr[x].max > val;
  int mid = (l + r) >> 1;
  if (tr[x << 1].max <= val)
    return find(x << 1 | 1, mid + 1, r, val);
  else 
    return tr[x].ans - tr[x << 1].ans + find(x << 1, l, mid, val);
}

void pushup(int x, int l, int r) {
  tr[x].max = max(tr[x << 1].max, tr[x << 1 | 1].max);
  int mid = (l + r) >> 1;
  tr[x].ans = tr[x << 1].ans + find(x << 1 | 1, mid + 1, r, tr[x << 1].max);
}

void modify(int x, int l, int r, int p, Frac val) {
  if (l == r) {
    tr[x].max = val;
    tr[x].ans = 1; 
    return;
  }
  int mid = (l + r) >> 1;
  p <= mid ? modify(x << 1, l, mid, p, val) : modify(x << 1 | 1, mid + 1, r, p, val);
  pushup(x, l, r);
}

int n, m, ans;

int main() {
  read(n), read(m);
  while (m--) {
    int x, y;
    read(x), read(y);
    modify(1, 1, n, x, Frac(y, x));
    writeln(tr[1].ans);
  }
  return 0;
}

后言

  • 千万不要直接想正解,要从直观的算法开始优化。
  • 线段树有很强大的功能,而且本身可以代替二分,不要傻乎乎的在套一个二分上去。
最后修改:2020 年 04 月 08 日 02 : 38 PM
如果觉得我的文章对你有用,请随意赞赏