T3MLE了qwq

上午比赛

A

对于3

首先随便配下式子能的到$D_j$不要为$D_i$约数

如果不互为约数就能满足

那么就是对于每个数不能是之前某个数的约数可以最长反链

就是没有一个点能走到前面的点

Dilworth定理可知道最长反链等于最小链覆盖

最小链覆盖是我们考虑和并链,然后用总边数-去

然后建边我们可以考虑用dfs,然后用个bitset处理一下传递闭包

可以考虑猜结论,是高维立方体 ,每个位置上有上界$lim_i$

这个最长反链答案一定是有一个所有指数和都相同的答案,就是有一层的

B

首先树形DP

$f_{i,j}$表示点i为root,最深点距离点i为j的连通块数

$f'[p][max(d1,d2+1)]=\sum_{d_1+d_2+1<=R}f[p][d1]*f[v][d2]$

优化一下,分类讨论max

$f[p][d2+1]+=(\sum_{d_1+d_2+1<=R,d_1<=d_2}f[p][d1])*f[v][d2]$

f'[p][d1]+=\sum_{d_1+d_2+1<=R&&d1<=d2}f[p][d1]*f[p][d2]

前面的式子可以用前缀和优化就是统计第二维的前缀和即可

然后您会发现后面那个好像可以线段树优化,因为一开始其实$f'=f$

那么也就是区间加上自己的一些倍数

然后可以用map维护一个差分,最后用线段树来推平,区间乘,区间+,单点修改,一个log

$O(n^2)?$

我们之前的放缩是深度严格小于两颗子树的点数乘积

放弃这个放缩,利用上子树深度性质

我们会发现d_1,d_2是深度的乘积,然后如果利用长链剖分短链的均摊性可以做到$O(n^2)$

其实就是直接背包

$n<=2e5$长链剖分

先dfs深度最大的儿子

dp过程可以直接线段树

如果我们能直接继承重儿子,那么轻儿子就可以直接做是复杂度合法的

问题是怎么在重链的地方做成线性的,发现只有一个+1

方法一是平移数组下标

方法二而我们可以把第二维记一个k级儿子是谁,然后其实就会

其他的复杂度是短链长度和,可以给长链标号,这样一条长链就是一段连续区间,就能很好了

C

显然可以发现我们能算贡献,然后这个贡献好像之和

会发现我们可以把他转成系数*2^次数的形式

发现如果直接链表记次数会自闭的$n\sqrt n$空间,显然可以垃圾桶

然后其实我们只需要拿个数组记一下就好了...然后询问的时候暴力平移回去

这个复杂度是合法的...

注意光速幂,可以预处理根号次

下午讲课

树状数组

反向查询

总数减前缀或者把修改和查询反着查

会发现我们实际上是变成了区间打标记然后单点查询

树状数组清零....

懒标记就是时间戳,看看是不是一样

二维树状数组

可以直接两个循环

区间加区间查询

实际上是加了一次函数

实际上我们做了两次前缀和

所以一个维护正常的$\sum{b_i}$前缀和一个维护$\sum_{i=1}^r i*b_i$

树状数组二分

直接+-lowbit

树状数组代替简单线段树

可以支持标记永久化可减性的线段树

首先区间加,我们可以在节点上打上加法标记qwq

给一点的父亲路径所有点查一次标记,而给前驱去查询和

要么我们一个区间已经被修改了要么可以通过查父亲的标记来得到修改

CF316E

如果1e9+7,就变成了维护

$\sum{a_i}{\phi^i}$

然后再除掉$\phi^{l}$

考虑维护斐波那契的转移矩阵

发现没有逆元,但好像可以直接维护一个分块矩阵,然后就直接搞就行了

但此时矩阵...有A,会发现A的主对角线是对称的,可以只要一个二元组就能维护

1.平衡树拆点,+平衡树二分

2区间线段树组维护区间加等差数列+树状数组二分

当然线段树也一样

然而我们有更好的做法

发现f_n=f_{n-m-1}f_m+f_{n-m}f_{m+1}

所以我们只需要维护$f_{x}*a_x$和$f_{x+1}*a_x$

51nod1598

对于k=1的情况

绝对值得意义就是到一维数轴上若干的点的距离和

那么现在就相当于查询一个中位数,而且是带权的

而k!=1就可以直接线段树带权中位数

BZOJ4653 NOI2016区间

我们发现答案满足单调性,可以将区间直接排序然后左端点递增的时候右端点也递增.....

也就是在值域轴上随便尺取一下qwq

线段树优化一下就O(nlogn)了

CF916D

你需要搞一个数据结构维护四个操作

set:插入权值为$x_i$​字符串$a_i$​,如果之前有则为修改权值为$x_i$​

remove:将$a_i$删除

query:查询所有还在的字符串中权值比$a_i$小的数量 ,没有输出-1

undo: 撤销回之前$d_i$个操作之前的状态(包括查询)

两颗主席树

一颗维护下标,一颗维护权值

CF893f

按照深度和dfs序维护线段树,扫描线

在线主席树

CFFIBTree

树剖主席树区间加等比+LCA

区间加??标记永久化!

带修主席树,实质是树套树

每个树状数组上记一个主席树

首先把所有的主席树提出来,然后查询的时候一起向下或者向右走一层

这个是$O(log^2)$

BZOJ1146

树上主席树,按照树的fa来建树,这样我们就能很快完成查询

然后修改点权相当于区间修改主席树qwq

权值离散化

CF119F....??

飞哥秒掉了

考虑n^3枚举那些点卡在下面那些点卡左边....

首先我们枚举一个下边界,

然后然后会发现左上方点数+1*右上方点数+1就是这个点答案

所以可以扫描线一下qwq

BZOJ

考虑二维数点

l,r的点,查询一个区间的子区间就类似于一个子三角形....

然后单调栈可以求出每个点作为最小值的区间,就类似于一个矩阵加

矩阵加法其实是加一次函数

所以我们离线时可以维护一个一次函数加即可

然后就能边回答询问边回答修改了

如果区间最小值唯一就一定不会交的

对于l>=r的位置暴力清零即可

LOJ6302

全1长方形可以悬线法DP

枚举每个点,向上最长到哪里,然后再从左向右做一个单调栈即可

正方形可以考虑横向距离超过最小值就弹出去

可以发现如果子矩阵可以二分一个最大值

然后限制一下在某个地方查询一下,二维ST表,这样就是3log

每个行建一个线段树,线段树上每个位置标示这个点向上的选线

然后合并的时候每个点维护下区间范围内最大的1矩阵

然后对于所有的列我们建一棵总线段树

现在我们求行很简单,而这个列怎么办

强制和l,r取min

均摊线段树

HackerRankFaftorialarray

40!mod P = 0

暴力前40

UOJ228

如果数都相等了就算了吧

完全平方数和完全平凡数-1都存在开根就会废操作

如果minmax差大于1,暴力开根

否则不是完全平方数就区间赋值了

否则是区间-

BZOJ4869

扩展欧拉定理

把2换成c,足够多次每个位置就都是c^无穷次

一路快速幂下来

足够多次是$*\phi(k)$,就是多少次后变成1

所以说只需要暴力前logP次,而后面的只需要直接做即可nlogPlogn,预处理根号P下的幂

luogu3733

加一条边其实就是多一个简单环

线段树上每个节点建线性基,记录所有简单环构成的线性基

线性基不支持修改删除,所以可以线段树分治

只要异或变大就一定异或即可,这样就能查询了

UOJ198

实际上我们会发现一个二元组会存在若干时间

用线段树可以维护这棵树的dfs序,每棵树就存在于一个区间中

所以我们可以考虑线段树分治避免凸包删除

凸包末尾删除

发现我们凸包正确的复杂度事实均摊的,所以我们可以记住一个栈顶和二分一个删掉的位置,之后我们只修改那个位置,回溯的时候就只需回溯一个位置和栈顶

询问好像也可以看成一个竖线插入然后直接询问即可

LOJ2537 pkuwc Minimax

首先我们可以做出DP

只有一个儿子能取到

相当于线段树合并

然后我们还要记一个前缀后缀的和,这个类似于冰火战士那个题

就可以在函数里多一维即可qwq

UOJ266

SG值是指后继状态的mex

枚举删除的第一个点然后得到一个森林,然后就是当前局面一个后继状态

然后森林中所有的树SG值异或起来插入集合中,最后对于集合中的数取mex即可

$O(n^2)$

然后一个局面的SG值是所有子局面的SG值XOR

考虑一个子树向上合并的过程,发现只需将子树异或上其他子树的 SG 值并加入到集合，并加入删除根节点的 SG 值，

会发现就是某个集合整体异或或者整体并,可以用01trie和dsuontree