[P1402](https://www.luogu.com.cn/problem/P1402) [P2891](https://www.luogu.com.cn/problem/P2891)

## 前言 对于复杂的区间操作，我们自然会想到使用线段树。但是，这也意味着会出现复杂的标记下传与维护，许多初学者也因此开始打退堂鼓。本文将介绍另一种用矩阵乘法来解决复杂标记下传的问题。 前置知识：简单线段树、线性代数基础（矩阵乘法）。 ## 一、多标记下传 ### （一）[P3373 线段树 2](https://ww…

应该没有人和我一样唐吧 ```cpp string merge(string s1,string s2){ string s3="";int i=0; for(;i<s1.size()&&s1[i]==s2[i];i++)s3+=s1[i];s3+='#'; for(;i<s1.size()&&s1[i]!=s2[i]…

~~使用哈希可以水过大部分字符串题~~ ## 思路 假设现有两个字符串 $S1$ 与 $S2$，其中 $S1$ 的长度更短。那么，若这两个字符串要满足要求，则 $S1$ 除第一个字符外的其他字符做组成的串需要是 $S2$ 的后缀，且 $S1$ 的第一个字符要在 $S2$ 除开之前那个后缀的其余部分出现。 换个说法：若…

> 取舍之间，方显智慧。 ——《权书·强弱》 注：本文中所有分析中都以$n$为物品数量,$m$为背包容量,$w_{i}$为物品重量或体积,$v_{i}$为物品价值。 ## 一、0-1背包：[P1048 采药](https://www.luogu.com.cn/problem/P1048) ### 题意 你现在有 $m$…

## 题意 给定一个长度为 n 的序列，其中所有连续且相同的数字为一个“段”，完成以下操作： 1. 1 x y：把序列中所有 x 变为 y。 2. 2：询问整个序列中有多少“段”。 ## 思路 对于这类不可逆的合并操作，容易想到用线段树合并解决。 很明显我们可以对每一种数字开一棵线段树(动态开点)，每一个线段树的节点储…

## 题意 给定一个长度为 n 的序列 a，取 k 个长度在 ql 与 qr 之间的该序列的不同的连续子段，使这 k 个子段中的元素之和最大。 ## 思路 先对原序列计算前缀和，覆盖原数组 a，以便求子段元素和。 求前 k 大的子段元素和可以考虑贪心，即使用堆(priority_queue)，而堆中存储的是一个三元组:…

[题目链接](https://www.luogu.com.cn/problem/P3970) ### 题意 给定一个整数序列，求它的上升子序列个数，且这些上升子序列的长度至少为2。 ### 思路 我们可以先简化一下问题，将只有1个元素的子序列也算入内（后文第一个式子中的+1），最后将它们从答案中减去（后文第二个式子中的…

## 题意 维护一个初始全为1的01序列，完成以下操作： 1. 0 l r：[l,r]变为0 1. 1 l1 r1 l2 r2：将[l1,r1]中的所有1拿来替换[l2,r2]中的0，多余的1则扔掉，不够就尽量往靠左的区间填（这一条可以看题中给的例子来理解） 1. 2 l r：[l,r]中最长的连续0 ## 思路 每一…

## 题意 用线段树维护一个01序列，完成以下操作： 1. 0 l r：[l,r]变为0 1. 1 l r：[l,r]变为1 1. 2 l r：[l,r]翻转 1. 3 l r：[l,r]中1的数量 1. 4 l r：[l,r]中最长的连续1 ## 思路 每一个节点维护8个信息： ```cpp struct tree{…

在讨论《treap悬7关求调》回复：

@[sxq9](luogu://user/658762) OK

在讨论《treap悬7关求调》回复：

@[sxq9](https://www.luogu.com.cn/user/658762) # 原代码错误分析 原代码在实现 Treap 数据结构时存在多个关键错误，导致无法通过洛谷 P3369 的测试。以下是主要错误的分析： ## 1. 旋转操作实现错误 原代码中的旋转操作实现不正确： ```cpp void lro…

在讨论《treap悬7关求调》回复：

@[sxq9](luogu://user/658762)

在讨论《treap悬7关求调》回复：

Deepseek改的： 为了解决代码中的问题，使其能够通过洛谷P3369的测试，我们需要对代码进行一系列修改。主要问题包括旋转操作错误、删除操作不完整、查询第k大函数未考虑重复元素、前驱和后继函数实现不准确等。 ### 修改思路 1. **旋转操作修正**：确保左旋和右旋操作正确调整节点关系并更新子树大小。 2. **…

在讨论《莫队48分求卡常（悬关）》回复：

@[lzx20120124](luogu://user/1592513)thanks(已关)

```cpp bool cmp(question i,question j){ if(pos[i.l]!=pos[j.l])return pos[i.l] j.r); } ``` r端点在同一块内就按time排序，并且要奇偶性优化

```cpp #include using namespace std; #define rint register int const int maxn=1e6+5; inline int read() { int x=0;char ch=getchar();bool sign=false; while(!isdig…

```cpp //Dijkstra代码 #include using namespace std; #define mid ((l+r)/2) #define ll long long int n,k,dis[200005],vis[200005],ans; vector G[200005]; priority_que…

在讨论《2024年10月12日事件回顾（违规紫三）》回复：

火钳刘明

在讨论《点一下我》回复：

宣传不正规团队，JBL

在讨论《你谷蒸蒸日上》回复：

/jk

在讨论《坐标SC，J 91.5 S 56 能过吗》回复：

@[heike305](/user/789739) thank you

求助

在讨论《坠机，求川线》回复：

@[SiriusIV](/user/1147243) 没救了，退役吧

在讨论《谁能想到我旁边的同学是黑题大佬》回复：

@[WangCurry](/user/764518) /jk

在讨论《J组72.5，在全国是什么水平》回复：

@[zhuyilun_SZ](/user/804172) +1

在讨论《J组72.5，在全国是什么水平》回复：

@[Han_Si_Ying](/user/1334245) 今年 NMG J组怕都有80+

在讨论《J组72.5，在全国是什么水平》回复：

@[Han_Si_Ying](/user/1334245) Ta也在说真的

在讨论《我同学ZJ-S 50.5能进吗》回复：

@[Jerry_heng](/user/763878) ZJ-S50.5 ~~稳~~ 废了，如果是其他省份都有机会

在讨论《J组72.5，在全国是什么水平》回复：

@[chenzheng1004](/user/1099993) 没救了，退役吧