zcmimi's blog

categories/刷题记录/共653篇文章

avatar
zc
2020-03-29 10:46:00
查看原题

点击跳转

avatar
zc
2020-03-28 23:23:00
查看原题

点击跳转

树套树解法

此题对树套树爱好者极不友好!

首先高高兴兴地写了个树状数组套动态开点权值线段树,发现MLE了,多次调整空间后发现要么re要么mle,难道只能用cdq分治或k-dtree了吗?

好不容易写完的代码舍不得随便删掉

既然卡空间,那我离散化坐标,再把树状数组也改成动态开点线段树还不行吗? 还真不行

我感到了这题深深的恶毒

只能动用黑科技了!

"线段树的压缩路径",如果没有询问要访问这个节点,那就不继续向下开点,以节约空间!

内层和外层都开,终于通过了这道恶毒的题

avatar
zc
2020-03-28 15:20:00
查看原题

点击跳转

树链剖分树套树

这里的树套树使用树状数组动态开点权值线段树实现,要先离散化

我的方法算是有点笨但是好写的方法

avatar
zc
2020-03-27 20:17:00
查看原题

点击跳转

此题非常之毒瘤,我写的整个人都二逼了

共有一下几种解法:

  1. 树状数组套线段树
  2. 线段树套平衡树
  3. 权值线段树套平衡树
  4. 分块
  5. 整体二分

树状数组套线段树

离散化+树状数组套动态开点线段树

这应该是一种常数小又好写的方法了,不开o2也轻松过

可以参照LG 2617 Dynamic Rankings的做法

简要说下思路:

树状数组记录位置,权值线段树记录权值

树状数组的每个节点都是一颗权值线段树

  1. 查询区间内一个数的排名:

    在树状数组上找到区间对应的节点,对应的权值线段树线段树树内查询对应数的排名并求和。

  2. 查询区间内排名为k的数是几:

    找出树状数组中所有对应节点,然后权值线段树上二分(与主席树的方法相似)

  3. 单点修改:

    相当于树状数组上的单点修改,在对应节点的权值线段树中删除原数,加入新数

  4. 前驱:

    查询排名,然后找排名-1的数

  5. 后继:

    查询排名,然后找排名+1的数

语文不好,不大会表述,相信数据结构这种东西直接看代码更好理解

具体可以看代码

avatar
zc
2020-03-26 01:21:00
查看原题

点击跳转

整体二分

接近模板题

avatar
zc
2020-03-25 23:54:00
查看原题

点击跳转

树套树

外层权值线段树 内层区间修改线段树

内层线段树需使用标记永久化,否则可能TLE

外层可以使用非递归结构提高速度

可以预先离散化提高速度

avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-03-23 17:38:00
查看原题

点击跳转

二维数点模板

avatar
zc
2020-03-23 16:44:00
查看原题

点击跳转

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,now为位置i的方案数

H_i\ge x,now=pre+\sum_{j=1}^i [S_j=S_i],这些位置是位置i-1不能满足而位置i可以满足的

H_i\le x,now=pre-\sum_{j=1}^i [S_j=S_{i-1}],这些位置是位置i不能满足而位置i-1可以满足的

这样就可以\Theta(n)解决了呢

记得开long long,S_0先赋值为n,防止负数re

avatar
zc
2020-03-23 08:44:00
查看原题

点击跳转

16/66
Search
search