单调栈

直观用途：o(n)找出数组中每个数右边第一个比它大的元素

题目：给定一个整型数组，数组元素随机无序的，要求打印出所有元素右边第一个大于该元素的值。
如数组A=[1,5,3,6,4,8,9,10] 输出[5, 6, 6, 8, 8, 9, 10, -1]
如数组A=[8, 2, 5, 4, 3, 9, 7, 2, 5] 输出[9, 5, 9, 9, 9, -1, -1, 5, -1]

对于类似的这种问题,即可用单调栈来优化.
其实只用到了栈结构，即先进后出。
遍历原数组，当遍历过i后将i加入栈。若i+1的值大于栈顶呢么一直出栈即可，直到遇到栈顶大于i+1的值，此时栈顶就是该点一侧的第一个大于该元素的值。
每个元素都会进栈一次最多出栈一次，故复杂度为O(2n)即O(n)算法。
证明显然，出栈的元素比小于当前点，呢么对之后点就无法起到贡献(因为当前点比出栈的元素大且靠近之后的点)，因此出栈点对后续操作没有影响

void Work()
{
    int Stack[Maxn]={},now=0;//数组实现栈，now是栈顶，入栈前自增，出栈--。
    for(int i=1;i<=n;i++)
    {
        while(Stack[now]<a[i])now--;
        ans[i]=Stack[now];
        Stack[++now]=a[i];
    }
}

单调队列

单调队列主要用于解决在长度为n的序列中，求每个长度为m的区间的区间最值。

基本思想是，维护一个所有元素都在目前区间的单调递减双向队列，遍历序列时仅当一个元素可能成为某个区间最值时才保留它，队列里面储存的数是原数组的下标
以求区间最大为例
当遍历到第n个数时，将其与队首元素比较大小，若大于队首元素，则将队首元素出队，直到小于队首元素，然后进队，之后队尾元素在m区间以外的元素出队，此时区间最大为目前的队尾。
每个元素都最多进一次队出一次队，故复杂度为O(n);
代码大概是这样

int n,a[50],ans[maxn];
int work()
{
    int Queue[maxn],ll=0,rr=1;
    Queue[++ll]=1;
    for(int i=2;i<=n;i++)
    {
        while(a[Queue[rr]]<a[i])rr--;
        Queue[++rr]=i;
        while(Queue[ll]+m<i)ll++;
        ans[i]=Queue[ll];
    }
}

约瑟夫环

有n个人围成一个圈，每 q个人踢掉一个人，问最后留下来的人是几号？

模拟的复杂度肯定是不合要求的，在此不做多说。
以下是 logn复杂度求法

#include <bits/stdc++.h>
using namespace std;
long long Ceil(long long x, long long y) {return x / y + (x % y != 0);}
long long J(long long n, long long q) 
{
    long long D=1,end=(q-1)*n;
    while(D<=end)
        D=Ceil(q*D,q-1);
    return q*n+1-D;
}
int main()
{
    long long n,q;
    while(~scanf("%lld%lld",&n,&q))printf("%lld\n", J(n,q));
    return 0;
}

具体证明见godweiyang的回答

序列自动机

求s1是否是s2的子串，复杂度是 siz(s2)26+siz(s1);空间只需要siz(s2)26即可

当时在太原五中看到的，整理旧blog时顺带补上
原理就是预处理出s2的每位后最靠前的26个字母，存起来之后把s1放到上面扫就行。

string s1,s2;
int a[27][100010];
void init()
{
    memset(a,-1,sizeof(a));
	for(int i=s1.size()-1;i>=0;i--)
	{
		for(int j=1;j<=26;j++)
			a[j][i]=a[j][i+1];
		a[s1[i]-'a'+1][i]=i;
	}
}
void work()
{
	while(cin>>s2)
	{
		int kl=0;
		for(int i=0,j=0;i<s2.size();i++)
		{
			//cout<<i<<' '<<a[s2[i]-'a'+1][j]<<endl;
			if(a[s2[i]-'a'+1][j]!=a[0][0])
				j=a[s2[i]-'a'+1][j];
			else
			{kl=1;break;}
		}
		if(kl==1)
			cout<<"NO"<<endl;
		else
			cout<<"YES"<<endl;
	}
}

伪三分

求二次函数极值

正常的二分只能在单调函数上寻找值，呢么假如我们要寻找二次函数的极值这种问题，肯定是无法直接使用二分来进行。
呢么我们可以用三分来解决这个问题，当然这个小专题名字叫做伪三分，呢就肯定不是正常的三分算法。准确的说我们使用的还是二分算法，只不过相当于是在原函数的“导数”上二分。
每一次取mid时，通过判断mid左右极小值的函数值大小来判断此点的斜率，假如f[mid+eps]>f[mid-eps]，呢么函数在mid这一点的极小邻域内必定是上升。反之，则是下降。根据函数特性来用mid替换左边界或右边界。
题目和代码

#include<bits/stdc++.h>
using namespace std;
double eps=0.00001;
long long n;
double ll,rr,Fans,a[30];
inline double F(double x)
{
    double ans=a[n+1],xx=x;
    for(int i=n;i>=1;i--)
    {
        ans+=a[i]*xx;
        xx*=x;
    }
    return ans;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    cin>>n>>ll>>rr;
    for(int i=1;i<=n+1;i++)cin>>a[i];
    while((rr-ll)>eps)
    {
        double mid=(ll+rr)/2;
        if(F(mid+eps)-F(mid-eps)<0)rr=mid;
        else ll=mid;
        //cout<<ll<<' '<<rr<<' '<<mid<<' '<<F(mid)<<endl;
    }
    cout<<rr<<endl;
    return 0;
}

二叉树的三种遍历方式

首先我们需要知道这三种方式都是如何遍历的
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
我们知道中序遍历以及另一种遍历结果，是可以求出来剩下的一种遍历结果的，而已知前序遍历、后序遍历无法求出中序遍历（因为由前序后序重构出来的二叉树不止一种）

分段打表

2022的天梯赛选拔，寄。
主要原因卡了两道题，一题是自己的思路绕弯了，把自己卡了很久。另一道就是这个需要分段打表的题。
考场上确实是推出来是逆元的性质，但是不会做快速求1e9的阶乘。
分段打表是可以将打表的递推数据不全部打出，假入全部输出线性递推的所有数据（比如这道题用的阶乘），输出所耗时间很多并且文件也很难存下。
于是可以将区间平均的分为100段，只存这100段的头的数据，具体需要求哪个数的时候从距离他最近的打表数据开始递推，复杂度就降到了n/100（可以打更多的段，复杂度就更低）。
大概是这样，希望下次不寄。