1.一部分需要求类似于(sum ans(x)^k)，k不大，(ans(x))贡献每次多(1)。
解：这种题感觉突然很常见还比较套路，在联赛出现也不是不可能/kk
直接二项式定理可以做到(O(k^2))更新贡献，但是并不优秀。
考虑斯特林数展开，(x^k=sum_{i=0}^kegin{Bmatrix}k\iend{Bmatrix}i!egin{pmatrix}x\iend{pmatrix})。
如何理解？考虑组合意义，(x^k)为(x)个集合放(k)个数的方案数（集合可以为空），那么可以枚举非空集，(egin{Bmatrix}k\iend{Bmatrix})是(i)个集合放(k)个数（集合不可以为空），盒子不一样所以乘(i!)，(egin{pmatrix}x\iend{pmatrix})是从(x)个集合选(i)个非空集。
于是这个式子变为(sum_{i=0}^kegin{Bmatrix}k\iend{Bmatrix}i!sumegin{pmatrix}ans(x)\iend{pmatrix})。
发现每次贡献更新只会跟(egin{pmatrix}ans(x)\iend{pmatrix})有关，而贡献多(1)后，(egin{pmatrix}ans(x)+1\iend{pmatrix}=egin{pmatrix}ans(x)\iend{pmatrix} + egin{pmatrix}ans(x)\i-1end{pmatrix})，于是我们维护(egin{pmatrix}ans(x)\iend{pmatrix},0le ile k)，每次更新贡献可以(O(k))完成。
2.拉格朗日恒等式。
感觉用的不多？写下吧
证明：
证毕。
然后这个可以用来证明柯西不等式，其实上面也已经证完了。
注意到
那么有
证毕。
貌似还有个更一般的式子？（后面的字母都是向量）
证明：
向量的混合积：([a,b,c]=(a imes b)cdot c)
([a,b,c])的集合意义就是以(a,b,c)为邻边的平行六面体体积
混合积性质：([a,b,c]=[b,c,a]=[c,a,b])
双重外积公式：((a imes b) imes c=b(a imes c)-a(b imes c))
然后对式子往后化简：
3.(nBSGS)
(n)次询问(g^xequiv y_i(mod p))。
如果每次都做一遍(BSGS)是(nsqrt{p})的，这也太慢了吧kk，怎么办呢。
注意我们(BSGS)的过程，设(y_i=aK-b)，原式化为((g^K)^aequiv y_i imes g^b(mod p))
注意到左边的不会改变，所以我们设(K=sqrt{frac{p}{n}})，于是(a)有(frac{p}{K}=sqrt{np})个，开始预处理出来，而(b)只有(K=sqrt{frac{p}{n}})个，一共做(n)次，复杂度就变成了(sqrt{np})
4.(O(n)-O(1)rmq)
复杂度优秀写起来也简单QAQ
这里拿区间最大值来说。
考虑对序列分块，块大小为(O(logn))，所以一共有(O(frac{n}{logn}))个块。
首先考虑(l,r)不在同一个块，显然可以对整块用st表查询最大值，零散块分别是一个前缀和后缀最大值，可以(O(n))预处理出来。
然后(l,r)在同一个块内的情况，考虑在每个块维护一个递减的单调栈，那么([l,r])之间的最大值就是在加入(r)之后从底部到顶部第一个下标大于等于(l)的元素。
那么考虑压位，每个点记录下来加入这个点的元素后当前块的单调栈形态，第(i)位二进制数表示当前块的左端点(+i)这个元素存不存在，然后每次查询相当于查询(r)位置存的二进制数后缀(0)的个数，(underline{~~~~}builtinunderline{~~}ctz(x))可以返回(x)的二进制中后缀(0)的个数，于是答案下标就是(l+underline{~~~~}builtinunderline{~~}ctz(x>>l-1))，左移是因为有了(l)个元素。
一般实现块大小采用(32)，压到(unsigned)里。
这是由乃救爷爷的代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define reg register
const int N = 2e7;
const int M = 7e5;
using namespace std;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
int n,m,s,a[N + 5],L,R,bln,pre[N + 5],suf[N + 5],mx[M + 5],stk[50],top,lg[M + 5],st[M + 5][21],idc;
unsigned bo[N + 5];
unsigned long long ans;
inline void prework()
{
bln = ((n - 1) >> 5) + 1;
for (reg int x = 1;x <= bln;x++)
{
L = ((x - 1) << 5) | 1,R = min(n,(x << 5));
for (reg int i = L;i <= R;i++)
{
mx[x] = max(mx[x],a[i]);
pre[i] = mx[x];
}
suf[R] = a[R];
st[x][0] = mx[x];
for (reg int i = R - 1;i >= L;i--)
suf[i] = max(suf[i + 1],a[i]);
top = 0;
unsigned t = 0;
for (reg int i = L;i <= R;i++)
{
while (top && a[stk[top]] < a[i])
{
t ^= 1 << stk[top] - L;
top--;
}
t |= 1 << i - L;
stk[++top] = i;
bo[i] = t;
}
}
lg[1] = 0;
for (reg int i = 2;i <= M;i++)
lg[i] = lg[i / 2] + 1;
for (reg int i = 1;(1 << i) <= bln;i++)
for (reg int j = 1;j + (1 << i - 1) - 1 <= bln;j++)
{
int l = st[j][i - 1],r = st[j + (1 << i - 1)][i - 1];
st[j][i] = max(l,r);
}
}
inline int qST(reg int l,reg int r)
{
if (l > r)
return 0;
int len = lg[r - l + 1];
return max(st[l][len],st[r - (1 << len) + 1][len]);
}
inline int query(reg int l,reg int r)
{
int bll = ((l - 1) >> 5) + 1,blr = ((r - 1) >> 5) + 1;
if (bll != blr)
{
int L = ((bll - 1) << 5) + 1;
int ans = qST(bll + 1,blr - 1);
ans = max(ans,suf[l]);
ans = max(ans,pre[r]);
return ans;
}
else
{
int pos = l + __builtin_ctz(bo[r] >> l - L);
return a[pos];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
srand(s);
for (reg int i = 1;i <= n;i++)
a[i] = read();
prework();
int l,r;
while (m--)
{
l = read() % n + 1;r = read() % n + 1;
if (l > r)
swap(l,r);
ans += query(l,r);
}
printf("%llu
",ans);
return 0;
}
5.(O(nlogn))三维偏序？嗯
(a_i<a_j,b_i<b_j,c_i<c_j)的个数。
特殊要求：同一维元素互不相同，（有相同的好像也能做？/kk）
我们观察一对((i,j))，他们存在的偏序关系要么是存在二维偏序要么是三维偏序。
于是我们把任意两维偏序都拿出来做二维偏序，也就是对((a,b),(a,c),(b,c))分别做二维偏序记录和(sm)，会发现一对((i,j))如果是二维偏序那么会被统计一次，如果是三维偏序那么会被统计三次，每一对((i,j))都作为二维偏序统计了一次的个数是(n(n-1)/2)，然后只剩下两倍的三维偏序数，于是我们可以得到三维偏序的数量(=frac{1}{2}(sm-n(n-1)/2))。
6.三元环计数。
复杂度是(msqrt{m})，但是这个可以(bitset)优化啊啊啊，某次考试的时候竟然没想到。
打上标记之后直接按位与一下就可以了，复杂度是(O(frac{n^3}{w}))。