2020-03-27发表2020-05-25更新32 分钟读完 (大约4806个字)

刷题记录

问就是鸽了

2020.3.25

CF EDU 84 (7/7)

A 简单数学

B 暴力

C 构造

全移动到一个点后走遍整个棋盘即可，总步数 $n-1+m-1+n*m$

D 暴力数学

每一个环分别处理，记它的长度为 $len$ 暴力可知，只有 $p^k$ 的 $k$ 是 $len$ 因子时才会分裂

枚举因子暴力 check 即可复杂度 $O(n*sqrt(n))$

E 数学

枚举 Block 的长度算一算

F DP

感谢彭爹教我dp

位与位之间独立，总方案数就是每一位的答案乘起来

考虑第 $i$ 个限制，若 $x_{i}$ 这一位是 $1$，那么 $[l_{i},r_{i}]$ 只能放 $1$

是 $0$ 那么说明 $[l_{i},r_{i}]$ 上至少有一个 $0$，暂时叫他 $0$ 限制

记 $f[i][0/1]$ 表示所有 $r_{i}<=i$ 的限制都已经满足且第 $i$ 位是 $0/1$ 的方案数

若第 $i$ 位有强制是 $1$ 的限制：

$f[i][0]=0$

否则第 $i$ 是 $0$ 总是合法的：

$f[i][0]=f[i-1][0]+f[i-1][1]$

若第 $i$ 位放 $1$，那么必定有一个 $j(j<=i)$ 是 $0$ 来满足那些 $r_{i}$ 在 $[j,i]$ 范围内的 $0$ 限制

考虑枚举所有符合条件的 $j$ 进行转移，即第 $j$ 位是 $0$，$[j+1,i]$ 位都是 $1$

但后缀 $1$ 也不能无限制的放，因为可能会将 $0$ 限制的区间占满

记 $s0_{i}$ 为所有 $r_{i}<=i$ 的0限制的 $l_{i}$ 的最大值，可以发现后缀 $1$ 最左可以放到 $s0_{i}$ 因此:

$f[i][1]=\sum_{j=s0_{i}}^{i-1} f[j][0]$

用前缀和可以优化到线性 O(n)

G AC自动机状压 DP优化

首先考虑暴力dp，$f[i][j][s]$ 表示构造了长度为 $i$ 的字符串，匹配到了 AC自动机上的 $j$ 节点，$s$ 是二进制串，表示问号用过了那些字符

第一维可以滚掉，但复杂度不降

注意到问号最多 $14$ 个，即大多数转移都是固定的，贡献也是固定的，可以提前算出非问号段的转移方向和贡献，从而加速dp

所以总复杂度是 $O(1410002^{14}+1000*4e5)$

2020.3.26

CF Global Round 4 (8/9)

A 暴力

B 前缀(后缀)和 dp

C 数学

答案是 $2^{n+m}$，快速幂

D 构造

给定点数 $n$，构造一个总边数是质数，且每个点的度数都是质数的图

我的做法是连成一个环，找一些度数为 2 的连互连凑到最近的质数

E 暴力性质

给一个长度为 $n$ 只包含 abc 三种字符的字符串，且保证相邻字符不相同，请你找一个长度至少为 $\lfloor \frac{n}{2} \rfloor$ 的回文子序列

考虑字符串的头两个字符和后两个字符，一定存在两个字符相等，把这对找出来加到回文子序列里

即每 $4$ 的长度至少贡献 $2$ 长度的回文，所以答案永远存在

F1 区间 dp

F2 区间 dp plus

G 凸壳 dfs序分块

抄了题解维护 $ans=(A_{i}+x)*B_{i}$ 的区间最大值，支持 $x$ 的区间加操作

分块，维护块上加法标记块内维护凸壳

CF1326F1 Wise Men (Easy Version)

meet in mid

状压 dp 冲不过。。抄了题解

2020.3.27

CF 629 Div.3

E 树lca

首先拿儿子一定没有拿父亲更优，因此标记所有询问节点的父亲，在判断一下是否在一条链上

我判链的方法是所有节点按深度排序，判相邻两节点的lca是否在他们俩之间

F 暴力前缀和

最后相等的 $k$ 个数一定是某个 $a_{i}$ 枚举算一算

BZOJ 1260 [CQOI2007]涂色paint 区间dp

HDU 2476 区间dp

上面那题加强版

CF 522 Div.2 (5/7)

A 读题暴力

B 暴力

C DP 记录方案

D 几何

A B 两点可唯一确定一个矩形，求出矩形与直线的交点后暴力算一算，答案取 min

E DP 数学

只有两种数的情况特判掉

否则答案选的一定是一些重量相等的数

$dp[i][j]$ 选 $i$ 个数和为 $j$ 的方案数，dp搞一搞

考虑各种情况下能唯一确定，记 $cnt[i]$ 为重量 $i$ 出现的次数

当 (j % i == 0) && dp[i][j] == C(cnt[j/i],i) 的时候可以唯一确定

符合条件的取个 max 即是答案

2020.3.28

牛客 NC204019 序列自动机

CF1183H 序列自动机

牛客 NC204272 dsu on tree

Luogu P2742 几何凸包

这题数据好弱。。。我用正方形卡了自己的AC代码

zoj 3537 几何区间dp

最优三角剖分

将凸多边形顺时针编号，$f[l][r]$ 代表将 $l…r$ 组成的多边形全割成三角形的最小代价

在最优割法中，边 $l-r$ 一定属于某个三角形之中，枚举三角形的第三个顶点 $k (l+1<=k<=r+1)$，转移方程为

$f[l][r] = min\{f[l][k]+f[k][r]+w(l,k)+w(k,r)\}$

LightOJ 1422 区间 dp

有点像刷字符串那个题，乍一看和区间 dp 没啥关系

$f[l][r]$ 表示以 $l…r$ 顺序排列时的答案

考虑第 $r$ 件是否可以和某一个共享:

$f[l][r] = min\{f[l][i]+f[i+1][r-1]+(a[i]!=a[k])\}$

CF 149D 区间dp

恶心

$f[l][r][cl(0…2)][cr(0…2)]$ 表示为区间 $l…r$ 染色，括号 $l$ 的颜色为 $c1$，括号 $r$ 的颜色为 $c2$ 的方案数

若 $l$ 与 $r$ 匹配，则要先判断颜色是否合法，再枚举与他相邻的括号的颜色进行转移

$f[l][r][cl][cr] = \sum_{}f[l+1][r-1][cl'][cr']$

否则，分别枚举与他们匹配的括号的颜色，这样 $l…r$ 就被分成了三段，分别 dp 计数乘在一起就行

2020.3.29

牛客 NC13221 数位dp 数论分块

~~为什么我会写数论的题~~

HDU 4283 区间dp

难，抄了题解，枚举 $f[l][r]$ 枚举 $l$ 是第 $k$ 个进入房间然后转移：

$f[l][r] = min\{f[l+1][l+k-1]+f[l+k][r]+(k-1)*a[i]+sum(l+k,r)*k\}$

ZOJ 3469 区间dp

同 Luogu P1220 关路灯

费用计算上的技巧

poj 1651 区间dp

和某场训练赛杀狼那个猎人的题一样。。。

NOIP2000 乘积最大 dp

练练python。。。才不是在水题

BZOJ 1090 区间dp

$f[l][r]$ 表示 $s[l…r]$ 能缩成的最短字符串

拼一拼：

$f[l][r] = min\{f[l][i]+f[i+1][r]\}$

缩一缩：

$f[l][r] = min\{f[l][l+len-1]+cost(l,r,len)\}$

BZOJ 1068 区间dp

注意 M-R 组成的区间不能相交，其他的和上面差不多

BZOJ 1055 区间dp

$f[l][r][k]$ 表示字符串 $s[l…r]$ 是否能合成单个字符 $k$

转移枚举断点即可

$f[l][r][k]|=(f[l][i][c1]\&\&f[i+1][r][c2])$

区间dp先刷到这里。。刷了 hzwer 和 kuangbin 的题单

2020.3.30

BZOJ 1086 王室联邦

一种树分快学习

再补几道，from 【动态规划3】区间与环形动态规划

CF607B 区间dp

luogu P3205 区间dp

luogu P3146 区间dp

spoj COT1 主席树

spoj COT2 树分快可持久化块状数组

2020.3.31

BZOJ 2589

同 spoj COT2，强制在线卡了卡常

。。下午颓废。。

CF 630 div2

$Nanako$ 做 $tester$ 的场，兹磁一下

你妈的还说不是 math round

A 数学

判掉 x1=x=x2 && (a||b) 和 y1=y=y2 && (c||d) 的情况，然后判一下最终位置会不会越界

B 数学

$\sqrt{1000}$ 以内的质数最多 $11$ 个，暴力分一分

C 暴力贪心

$s[1]$ 一定和 $s[k]$ 相同，暴力统计所有循环该位置上的字母个数，保留出现位置最多的字母。

D 构造

设 $k$ 的最高位 $1$ 在第 $mx$ 位(从 $0$ 开始编号)，构造答案矩阵 $2*3$：

令 $t=1<<(mx+1)$

$t+k,k,0$

$t,t+k,k$

E 数学矩阵ksm

设奇数为 $1$，偶数为 $0$，推一推可以发现合法的方案一定满足 (有偶数个0 || 有偶数个1)，因为如果有偶数个 0/1 一定可以通过不断改变位置最后碰到一起消掉

设 $f[i][0/1][0/1]$ 表示 $i$ 个格子，$0$ 有奇数/偶数个，$1$ 有奇数/偶数个，枚举最后一个格子放 $0/1$ 转移

显然是个线性递推式，矩阵ksm搞一搞，AC没烦恼

F 树上dp

先转化一下题意，如果把不选也看成染一种颜色($0$)的话，这题等价于求：

给每个点染色 $(0/1/2)$-(在独立集中/不在独立集中/没选) 后选一些边，需满足不存在孤立的 $1/2$ 颜色的点，$1$ 颜色之间的点不能连边，求方案数。

定义状态：

$f[u][0]$ u 点为颜色 $1$ 且不存在孤立点的方案数

$f[u][1]$ u 点为颜色 $2$ 且不存在孤立点的方案数

$f[u][2]$ u 点为颜色 $1$ 且 $u$ 是孤立点的方案数

$f[u][3]$ u 点为颜色 $2$ 且 $u$ 是孤立点的方案书数

$f[u][4]$ u 点为颜色 $0$ 的方案数

两棵树通过 $(u,v)$ 边来进行合并答案：

$dp[0] = f[u][0]*(f[v][0]+f[v][1]*2+f[v][3]+f[v][4]) + f[u][2]*(f[v][1]+f[v][3])$

$dp[1]=f[u][1](f[v][0]2+f[v][1]2+f[v][2]+f[v][3]+f[v][4])+f[u][3](f[v][0]+f[v][1]+f[v][2]+f[v][3])$

$dp[2]=f[u][2]*(f[v][0]+f[v][1]+f[v][4])$ $dp[3]=f[u][3]*(f[v][0]+f[v][1]+f[v][4])$ $dp[4]=f[u][4]*(f[v][0]+f[v][1]+f[v][4])$

2020.4.1

上午。。操作系统还是听听好

SPOJ COT2 树上莫队

学了下树上莫队的做法，会专门开一篇写

WC2013 糖果公园带修树上莫队

CF 愚人节round

~~不务正业草~~

A No

B 分解质因数

C 二进制换位

D 判奇偶

E 画图染色图像处理黑白

F 判字符串能否被化学元素组成 dp

2020.4.2

luogu P4198 楼房重建分块

bzoj 3295 动态逆序对分块/cdq

之前用树状数组套动态开点A过了，补下其他几种做法

分块：每个块维护个vector，删除某个点时同一块内逆序对的暴力统计，其他块二分

cdq:坑着

bzoj 3744 区间逆序对强制在线分块

类似蒲公英，块与块之间的答案 $ans[L][R]$ 先预处理出来，询问时在考虑不完整块的贡献

bzoj 4028 [HEOI2015]公约数数列分块暴力

很妙。。。抄了题解

首先前缀 $gcd$ 这个东西有个很好的性质，即它最多有 $\log_{2}{x}$ 种不同的取值(CF某树上 $gcd$ 也用了这个性质)

考虑分块，当某个块内的前缀 $gcd$ 相等的时候，我们只需要查块内是否存在前缀 $xor$ 和等于 $x/g$ 的位置 $i$

假设当前是第 $k$ 块，那么块内某个位置 $i$ 的前缀 $xor$ 和又可以分为 (前 $k-1$ 块的 $xor$ 和)^(第 $k$ 块首部到 $i$ 的 $xor$ 和) 两部分，而当 $k$ 确定时前者是个定值，因此只需维护每个位置的块内前缀 $xor$ 和即可

因此对于每个块，我们维护以下几个值：

$lgcd$：块左端点的前缀 $gcd$ 值

$rgcd$：块右端点的前缀 $gcd$ 值

$sgcd$：块内所有数的 $gcd$

$sxor$：块内所有数的 $xor$ 和

$set(S)$：块内所有位置的前缀 $xor$ 和组成的 $set$

对于查询操作，我们从头枚举每个块，当块的 $lgcd$ == $rgcd$ 时，我们只需在 $set$ 里 $find$ 一下是否存在符合条件的位置 $i$；当块的 $lgcd$ != $rgcd$ 时我们大力枚举块内的每一个位置来查找答案。

由于前缀 $gcd$ 最多有 $\log_{2}{x}$ 种取值，所以 $lgcd$ != $rgcd$ 的块最多有 $\log_{2}{x} + 1$ 个，复杂度有保证

对于单点修改操作，我们只需暴力重建 $x$ 所在的块，并更新后面所有块的 $lgcd$ 与 $rgcd$ 即可

const int SZ = 500;
int n,m;
int id[MAXN];
LL  a[MAXN];
struct block
{
    int l,r;
    LL lgcd,rgcd,sgcd,sxor;
    vector<LL> v;
    inline bool find(LL x)
    {
        vector<LL>::iterator it = lb(all(v),x);
        return it!=v.end()&&*it==x;
    }
}b[MAXN/SZ+5];
void build(int k)
{
    b[k].v.clear();
    LL pre=0,g=a[b[k].l];
    fp(i,b[k].l,b[k].r)pre^=a[i],b[k].v.pb(pre),g=__gcd(g,a[i]);
    sort(all(b[k].v));
    b[k].sxor=pre;
    b[k].lgcd=k?__gcd(b[k-1].rgcd,a[b[k].l]):a[b[k].l];
    b[k].sgcd=g;
    b[k].rgcd=__gcd(b[k].lgcd,b[k].sgcd);
}
int work()
{
    scanf("%d",&n);
    fp(i,1,n)scanf("%lld",&a[i]);
    fp(i,1,n)id[i]=(i-1)/SZ+1;
    fp(i,1,n)if(!b[id[i]].l)b[id[i]].l=i;
    fd(i,n,1)if(!b[id[i]].r)b[id[i]].r=i;
    fp(k,1,id[n])build(k);
    scanf("%d",&m);
    while(m--)
    {
        char s[10]; scanf("%s",s+1); LL x,y;
        if(s[1]=='M')
        {
            scanf("%lld%lld",&x,&y),x++,a[x]=y,build(id[x]);
            LL g=b[id[x]].rgcd;
            fp(k,id[x]+1,id[n])
            {
                b[k].lgcd=__gcd(g,a[b[k].l]);
                b[k].rgcd=__gcd(g,b[k].sgcd);
                g=__gcd(g,b[k].sgcd);
            }
        }
        else
        {
            scanf("%lld",&x); LL sxor=0,sgcd=a[1];bool flag=0;
            fp(k,1,id[n])
            {
                if(b[k].lgcd!=b[k].rgcd||(x%b[k].lgcd==0&&b[k].find((x/b[k].lgcd)^sxor)))
                {
                    LL s=0,g=a[b[k].l];
                    fp(i,b[k].l,b[k].r)
                    {
                        s^=a[i],g=__gcd(g,a[i]);
                        if((s^sxor)*__gcd(g,sgcd)==x)
                            {printf("%d\n",i-1);flag=1;break;}
                    }
                }
                sxor^=b[k].sxor,sgcd=__gcd(sgcd,b[k].sgcd); if(flag)break;
            }
            if(!flag)puts("no");
        }
    }
    return 0;
}

2020.4.3

bzoj 1926 二分莫队

CF 631 div.2

I_LOVE_DREAMOON

A

B

C 贪心

D 数学 dp

2020.4.4

GCJ 资格赛

A 模拟

B 每次选一段区间减去最小值

C 二分图

D 交互

$B = 10$ 有手就行

$B = 20$ 考虑四种操作其实对 $i$ 和 $B-i+1$ 的关系(相等/不相等)没有影响，$20$ 次询问每一对 $(i,B-i+1)$，最后在一组内问出数组的一半，另一半根据相等/不等关系推得

$B = 100$ 先找

E 只会暴力

bzoj 4129 树上待修mex 树上待修莫队分块

打打板子

spoj qtree1 树剖

spoj qtree2 倍增

倍增可以干的事还挺多的。。

spoj qtree3 树剖 set

树剖的原理就是把树剖成若干链，同一链内的节点标号连续

同理 $1$ ~ $u$ 的路径也可以拆成若干重链(不一定完整)，用 $set$ 维护每个链内黑点，按深度排序

跳重链询问的时候注意只有深度 <=d[x] 的点才可以更新答案，不然有可能不在路径上

2020.4.5

颓废++

luogu P4332 LCT

bzoj 2959 LCT 并查集

如果加边保证原图一直是一棵树，那么 $a$ -> $b$ 的路径显然是唯一的

如果加边出现了环，这个环内的所有 $a_{i}$ 我们都可以拿到，并且可在任意一点进入/出去，相当于环缩成了一个点

考虑使用 $lct$ 维护这个过程，把 $a$ -> $b$ 的路径拿出来后暴力把他们的编号映射成一个新的点，连接到路径上的虚边可以不用动，这一步可以用并查集来实现

注意缩点以后每个点真实的 $fa[x]$ 都要在并查集里 $find$ 一下

2020.4.6

颓废++++ 少做水题..

bzoj 4998 LCT 并查集

同 bzoj 2959，并查集维护下siz即可

CF 503 div.2

A

B 模拟

C 暴力贪心

D 交互二分

2020.4.7

luogu P4172 LCT 最小生成树

luogu P4180 LCT 严格次小生成树

luogu P4234 LCT

luogu P2387 LCT

luogu P4219 LCT 维护子树信息

2020.4.8

CF 632 Div.2

A 构造

B

C 乱搞

D

先暴力搞出最快移动方案，拆成大小为 $k$ 就行

F 数论

$x$ 一定是在答案是他最大因子的那一轮加进去，暴力分解

2020.4.9

1900~2300 xjb练 [0]

2h solved 3/5

CF 864E *2000 dp

$d_{i}$ 小的肯定先救，按 $d_{i}$ sort 后按时间轴 dp，$f[i][j]$ 表示考虑前 $i$ 个物品，当前在时间 $j$ 时能救的最大价值，记录方案 dp

CF 853B *1900 乱搞

直接暴力枚举停留的时间点 $[i,i+k-1]$，然后搞个 $multiset$ 维护一下前后每个人来和去最便宜的航班

CF 865B *1900 贪心

假如每个人都吃他最喜欢的那个种类的披萨，设 $A$ 种披萨的需求量为 $Sa$，$B$ 的需求量为 $Sb$，若 $Sa$ % $S + Sb$ % $S$ > $S$，则所有人都可以满足，否则有一些人需要放弃他最喜欢的那种，枚举最后一块披萨是 $A$ 还是 $B$ 的情况，按差值排序选最小的几个即可。

CF 862D *2000 交互二分

观察可以发现通过询问 $111110000$ 可以算出某段区间的 $0$ 和 $1$ 的个数，二分找左区间全是 $0$，有区间全是 $1$ 的位置就行

CF 808D *1900 乱搞

枚举断开的位置，$set$ 查一查差值

QTREE6 lct

lct维护同色联通快

2020.4.10

CF EDU 85

2020.4.11

GCJ 没进R2

颓废 ++++++

2020.4.12

1900-2300 xjb刷 [1]

solved 2/5

CF 1017D *1900 暴力

$ 2^12 $ 种情况的价值开个桶存一下

CF 1015E2 *2000 贪心

枚举中点贪心放星，check 的话搞个差分

CF 992D *2100 暴力

如果没有 $1$, $P$ 往前乘不到 $100$ 次就爆 $2e18$ 了

考虑成段的 $1$ 一起处理，因为乘积不变，符合条件的位置最多一个

1900-2300 xjb刷 [2]

CF 1067A *2000 dp

CF 1067B *2000 bfs

从叶子开始多点bfs，按题意check

CF 1039B *2100 交互二分

二分，<=40 rand一个点

CF 1037E *2100 bfs

倒着考虑，首先把所有点都加进去，删掉那些度数 <k 的点和他们连的边，这个可以用 bfs 来做

删掉一个边就看一下他连的那两个点的度数是否 <k，如果 <k 了就继续 bfs 删到不能删为止

边要用set存

CF 493 div.1

A

设 $0$ 有 $n$ 段，答案就是 $min\{x(n-1)+y,yn\}$

B 打表

C 容斥

CF 635 div.1

A

B

2020.4.13

CF 988E 暴力 *2100

CF 962E 贪心 *2200

难想

第一个 P 之前和最后一个 P 之后的 AB 一定都是相邻的直接连

考虑距离最近的两个 P 之间的 AB 如何连：

P—A—A…A—P 加上 P—B—B..B—P
P—A—A A—A—P 加上 P—B B—B—P 然后两个 P 再相连，解释一下就是断开其中最大的间隙

两种取个 $min$ 就是答案

CF 997E 数据结构 *3000

区间 $good$ 的条件： $max-min==r-l$

离线，对于每个右端点维护左面每个位置的答案，套路类似于 zzq 那题，搞两个单调栈，踢出元素的时候再线段树上更新一下，然后统计下 $(max-min)-(r-l)$ 是 $0$ 的有多少

但这样只能求固定某个右端点的答案，我们要的是右端点在 $[l,r]$ 时左端点 $<=l$ 符合条件的点有多少个，即我们需要每个版本答案之和的线段树 ~~主席树?~~

线段树上在维护一个 $save$ 标记，代表这一段区间需要对答案贡献一次，这个标记与时间无关，注意 $pushdown$ 时只能向最小值所在的儿子区间进行累加

namespace seg
{
    int mn[MAXN*4],num[MAXN*4],add[MAXN*4],save[MAXN*4];//,ans[MAXN*4];
    LL  saveans[MAXN*4];
    inline void dosave(int cnt,int v)
    {
        saveans[cnt]+=1LL*num[cnt]*v,save[cnt]+=v;
    }
    inline void doadd(int cnt,int v){mn[cnt]+=v,add[cnt]+=v;}
    inline void down(int cnt)
    {
        if(add[cnt])doadd(ls,add[cnt]),doadd(rs,add[cnt]),add[cnt]=0;
        if(save[cnt])
        {
            if(mn[ls]==mn[cnt])dosave(ls,save[cnt]);
            if(mn[rs]==mn[cnt])dosave(rs,save[cnt]);
            save[cnt]=0;
        }
    }
    inline void up(int cnt)
    {
        if(mn[ls]==mn[rs]) mn[cnt]=mn[ls],num[cnt]=num[ls]+num[rs];
        else if(mn[ls]<mn[rs]) mn[cnt]=mn[ls],num[cnt]=num[ls];
        else mn[cnt]=mn[rs],num[cnt]=num[rs];
        saveans[cnt]=saveans[ls]+saveans[rs];
    }
    void build(int l,int r,int cnt)
    {
        if(l==r){mn[cnt]=0,num[cnt]=1;return;}
        build(l,mid,ls),build(mid+1,r,rs),up(cnt);
    }
    LL query(int l,int r,int nl,int nr,int cnt)
    {
        if(l==nl&&r==nr)return saveans[cnt]; down(cnt);
        if(nr<=mid)return query(l,mid,nl,nr,ls);
        if(nl> mid)return query(mid+1,r,nl,nr,rs);
        return query(l,mid,nl,mid,ls)+query(mid+1,r,mid+1,nr,rs);
    }
    void rangeadd(int l,int r,int nl,int nr,int v,int cnt)
    {
        if(l==nl&&r==nr){doadd(cnt,v);return;} down(cnt);
        if(nr<=mid)rangeadd(l,mid,nl,nr,v,ls);
        else if(nl>mid)rangeadd(mid+1,r,nl,nr,v,rs);
        else rangeadd(l,mid,nl,mid,v,ls),rangeadd(mid+1,r,mid+1,nr,v,rs);
        up(cnt);
    }
    void rangesave(int l,int r,int nl,int nr,int v,int cnt)
    {
        if(l==nl&&r==nr){if(mn[cnt]==0)dosave(cnt,v);return;} down(cnt);
        if(nr<=mid)rangesave(l,mid,nl,nr,v,ls);
        else if(nl>mid)rangesave(mid+1,r,nl,nr,v,rs);
        else rangesave(l,mid,nl,mid,v,ls),rangesave(mid+1,r,mid+1,nr,v,rs);
        up(cnt);
    }
}
 
int n,m;
int a[MAXN],l[MAXN],r[MAXN]; LL ans[MAXN];
vector<int> pos[MAXN];
struct elem
{
    int l,r,v;
    bool operator <(const elem &t)const{return v<t.v;}
    bool operator >(const elem &t)const{return v>t.v;}
};
stack<elem> mx,mn;
 
int work()
{   
    scanf("%d",&n);
    fp(i,1,n)scanf("%d",&a[i]);
    scanf("%d",&m);
    fp(i,1,m)scanf("%d%d",&l[i],&r[i]),pos[r[i]].pb(i);
    seg::build(1,n,1);
    fp(i,1,n)
    {
        if(i>1)seg::rangeadd(1,n,1,i-1,-1,1);
 
        elem cur = {0,i,a[i]};
        while(!mx.empty()&&cur>mx.top())
        {
            elem t=mx.top(); mx.pop();
            seg::rangeadd(1,n,t.l,t.r,-t.v,1);
        }
        cur.l=mx.empty()?1:(mx.top().r+1); mx.push(cur);
        seg::rangeadd(1,n,cur.l,cur.r,a[i],1);
 
        while(!mn.empty()&&cur<mn.top())
        {
            elem t=mn.top(); mn.pop();
            seg::rangeadd(1,n,t.l,t.r,t.v,1);
        }
        cur.l=mn.empty()?1:(mn.top().r+1); mn.push(cur);
        seg::rangeadd(1,n,cur.l,cur.r,-a[i],1);
 
        seg::rangesave(1,n,1,i,1,1);

        for(auto j:pos[i])
            ans[j]=seg::query(1,n,l[j],r[j],1);
    }
    fp(i,1,m)printf("%lld\n",ans[i]); return 0;
}

2020.4.14

CF 634 Div.3

1335 E2 暴力

答案一定是从尽量靠两边的位置选 $a$，中间的部分选出现次数最多的字母，处理下前缀和枚举两边的字母和长度就行

复杂度是 $O(200*n)$，一开始还以为是 $O(200*200*n)$，其实每个位置只会被枚举到一次，所以是 $n$ 级别的而非 $200*n$

1335 F 倍增

观察可以发现这图其实是个基环树，走足够步数后所有机器人都会在环上转，即树上每个点都与环上点一一对应

那么 $ans1$ 就是所有环的大小之和，$ans2$ 就是有多少黑点能上环

考虑倍增走个 $2e6$ 步，肯定就上环了，剩下就好做了

$O(nlogn)$ 跑的慢点，但码量少呀

1900-2300 xjb刷 [3]

2/5

CF 909E *2100 拓扑

把拓扑排序扩展一下，每轮先拿黑点到拿不动位置，再不断拿白点到拿不动位置

白点拿的轮数就是答案

CF 912D *2100 期望数据结构

首先格子上每个点对答案的贡献是固定的，我们只要选前 $k$ 大加起来就是最优解

打表观察发现贡献矩阵是从中心向四周递减

由于 $k==1e5$，我们用类似 $bfs$ 的做法，每次选队列中权值最大的点，然后向四周扩展

最多扩展 $4*1e5$ 次，复杂度不会炸

1900-2300 xjb刷 [4]

2/5 1012C

CF 1012C *2000 dp

$dp[i][j][0/1]$ 表示前 $i$ 个坑，造 $j$ 个房子，最后一个山有没有被砍过

这么定义是因为如果一个山被砍过，他一定是 $min(a[i],a[i-1]-1)$ 的高度

转移脑补一下，特判 $n=1$ 和 $n=2$

CF 1061D *2000 贪心 sort stl

按 $pair$ 排序，贪心选一个右端点离当前左端点最近的，如果放不下或新开一个更合适就新开一段

找 $<l$ 最大的右端点用 $set$ 就行

CF 1030E *2100 暴力

~~zzqnb就完了~~

把每个数换成 $bitcount(x)$，然后转化题意，问有多少区间满足每次选俩数减 $1$，可以把区间内的数全减乘 $0$

区间内的数可以减为 $0$ 的条件:

1.$\sum_{i=l}^{r}a[i]>=2*max\{a[l]…a[r]\}$

2.$\sum_{i=l}^{r}a[i]$ % $2 == 0$

由于 $1<=a[i]<=64$，长度大于 $128$ 的区间一定满足条件 $1$，只要判下条件 $2$ 即可，这个用通过统计前缀和奇偶性可以 $O(1)$ 来算

长度 $<=128$ 的区间暴力判两个条件

复杂度：$O(nlogn)$

CF 1028D *2100 模拟

意义不明

每次 $accept$ 确定一些 $buy$ 和 $sell$，自己不确定 $ans*=2$

最后一段 $add$ 枚举分界点 $ans*=(siz+1)$

刷题记录

http://blog.bakapiano.site/2020/03/27/刷题记录/

作者

Bakapiano

发布于

2020-03-27

更新于

2020-05-25

刷题记录

2020.3.25

CF EDU 84 (7/7)

A 简单数学

B 暴力

C 构造

D 暴力 数学

E 数学

F DP

G AC自动机 状压 DP优化

2020.3.26

CF Global Round 4 (8/9)

A 暴力

B 前缀(后缀)和 dp

C 数学

D 构造

E 暴力 性质

F1 区间 dp

F2 区间 dp plus

G 凸壳 dfs序 分块

CF1326F1 Wise Men (Easy Version)

2020.3.27

CF 629 Div.3

E 树lca

F 暴力 前缀和

BZOJ 1260 [CQOI2007]涂色paint 区间dp

HDU 2476 区间dp

CF 522 Div.2 (5/7)

A 读题 暴力

B 暴力

C DP 记录方案

D 几何

E DP 数学

2020.3.28

牛客 NC204019 序列自动机

CF1183H 序列自动机

牛客 NC204272 dsu on tree

Luogu P2742 几何 凸包

zoj 3537 几何 区间dp

LightOJ 1422 区间 dp

CF 149D 区间dp

2020.3.29

牛客 NC13221 数位dp 数论分块

HDU 4283 区间dp

ZOJ 3469 区间dp

poj 1651 区间dp

NOIP2000 乘积最大 dp

BZOJ 1090 区间dp

BZOJ 1068 区间dp

BZOJ 1055 区间dp

2020.3.30

BZOJ 1086 王室联邦

CF607B 区间dp

luogu P3205 区间dp

luogu P3146 区间dp

luogu P3146 区间dp

spoj COT1 主席树

spoj COT2 树分快 可持久化块状数组

2020.3.31

BZOJ 2589

CF 630 div2

A 数学

B 数学

C 暴力 贪心

D 构造

E 数学 矩阵ksm

F 树上dp

2020.4.1

SPOJ COT2 树上莫队

WC2013 糖果公园 带修树上莫队

CF 愚人节round

A No

B 分解质因数

C 二进制换位

D 判奇偶

E 画图染色 图像处理黑白

F 判字符串能否被化学元素组成 dp

2020.4.2

luogu P4198 楼房重建 分块

bzoj 3295 动态逆序对 分块/cdq

D 暴力数学

G AC自动机状压 DP优化

E 暴力性质

G 凸壳 dfs序分块

F 暴力前缀和

A 读题暴力

Luogu P2742 几何凸包

zoj 3537 几何区间dp

spoj COT2 树分快可持久化块状数组

C 暴力贪心

E 数学矩阵ksm

WC2013 糖果公园带修树上莫队

E 画图染色图像处理黑白

luogu P4198 楼房重建分块

bzoj 3295 动态逆序对分块/cdq

bzoj 3744 区间逆序对强制在线分块

bzoj 4028 [HEOI2015]公约数数列分块暴力

bzoj 1926 二分莫队

bzoj 4129 树上待修mex 树上待修莫队分块

C 暴力贪心

D 交互二分

CF 862D *2000 交互二分

CF 1039B *2100 交互二分