题意有毒,是把一个数插入到第x个数后面(不会有数被覆盖)

BIT的一个log做法是假的,BIT+二分好像是对的

hack数据

3
2 2 2

答案应该是1 2 3 假做法还原的序列是0 0 1 错到不知哪里去了

我写完假做法以后才知道是错的

不想写平衡树。。。发现可以用rope,那就来一发

int n, Max, ans[MAXN];
__gnu_cxx::rope<int>a;
struct BIT {
  int t[MAXN];
  inline void add(int k, int x) {
    while (k <= n) chmax(t[k], x), k += k & (-k);
  }
  inline int query(int k) {
    int ret = 0;
    while (k) chmax(ret, t[k]), k -= k & (-k);
    return ret;
  }
  inline int kth(int k) {//查询第k小
    int cnt = 0, ret = 0;
    for (int i = log2(n); ~i; --i) {
      ret += 1 << i;
      if (ret >= n || cnt + t[ret] >= k) ret -= 1 << i;
      else cnt += t[ret];
    }
    return ret + 1;
  }
} bit;

int main() {
#ifdef LOCAL_DEBUG
  Debug = 1; double tim1 = clock();
  // freopen("data.in", "r", stdin) && freopen("data.out", "w", stdout);
#endif
  in, n;
  lop(i, 1, n) {
    int x;
    in, x;
    a.insert(x, i);
  }
  lop(i, 0, n-1) { //求LIS
    int x = bit.query(a[i]) + 1;
    ans[a[i]] = x;
    bit.add(a[i] + 1, x);
  }
  lop(i, 1, n) {
    chmax(Max, ans[i]);
    out, Max, '\n';
  }
#ifdef LOCAL_DEBUG
  fprintf(stderr, "\ntime:%.5lfms\n", (clock() - tim1) / CLOCKS_PER_SEC * 1000);
#endif
  return 0;
}
分类: 平衡树

发表评论

电子邮件地址不会被公开。 必填项已用*标注