退役前的做题记录2.0

这里主要记录一些做过的但没必要单独发一篇博客的题。。

---

[LOJ3083][GXOI/GZOI2019]与或和：单调栈

本质就是一个条形图矩形计数，每一行用单调栈跑一下就好了。

核心代码：

int solve(int *ht){
	int ret=0;top=0;
	rin(i,1,n+1){
		while(top&&ht[sta[top]]>ht[i]){
			int l=sta[top-1]+1,r=i-1,wd=r-l+1;
	    	ret=(ret+1ll*(wd+1)*wd/2*(ht[sta[top]]-std::max(ht[i],ht[sta[top-1]])))%MOD;
			--top;
		}
		sta[++top]=i;
	}
	return ret;
}

---

[LOJ2537][PKUWC2018]Minimax：期望DP+线段树合并

离散化后权值为下标，线段树合并的时候顺便记一个概率的前缀和就好了。

---

[LOJ6432][PKUSC2018]真实排名：双指针法+组合数学

对每个数讨论是否( imes 2)，唯一需要注意是特判(A_i=0)的情况。

---

[LOJ3058][HNOI2019]白兔之舞：单位根反演+矩阵快速幂+任意模数NTT

单位根反演的过程比较显然。唯一的难点就是（或者说是一个Trick），我们要想办法把(jt)去掉，可以这样：

之后跑个(MTT)就好了。