zcmimi's blog

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

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
查看原题

点击跳转

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

点击跳转

先离散化,然后用树状数组统计两边的数目,比较即可

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

点击跳转

首先可以想到按v_i排序

接下来就直接按顺序插入并统计就可以了

关于距离之和的统计:

可以分前半部分和后半部分统计

用树状数组维护即可

感觉很水

具体看代码吧

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

点击跳转

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

x_i+y_i-\max(x_j+y_j)

坐标再旋转并处理三次就可以了

avatar
zc
2020-03-20 21:22:00
查看原题

点击跳转

17/66
Search
search