分治学习笔记

分治及分治优化学习笔记

前言

这里的分治主要将的是普通分治技巧，cdq分治，线段树分治的应用，树上的点分治之类的可能会再开一个专题（主要是现在作者还不会），先把基础打好。
普通分治

分治主要分为两种——最值分治和中点分值，顾名思义，就是一个取一个区间的最大值/最小值，而一个是直接取中间点即可。分治的方法一般放在 \(\displaystyle \sum_{i=1}^n\sum_{j=i}^{n} f(i,j)\) 这样的式子上。可以从 \(O(n^2)\) 的时间复杂度优化到 \(O(n\log n)\) 的时间复杂度。
以一道例题举例：E - Yet Another Sigma Problem (atcoder.jp)
这道题求的就是两个字符串的最长前缀。
而我们发现排序不影响结果，先排个序。
我们发现刚好，排完序之后，因为只有首字母相同的才可以有贡献，我们发现有贡献的都连在了一起，这样是不是就可以直接分治了呢？
直接对于第 k 个相同的区间进行分治每一次往前多推进一个字符。
代码也是非常简单。
[code]#include#define int long longusing namespace std;const int N=3E5+5;int n;string s[N];int solve(int l,int r,int k){        if(l>=r)return 0;        int p=l;        while(p