vector排序
vector<int >an;
sort(an.begin(),an.end());//从小到大排列;更相减损术
适用于求：gcd_sub(pow(a,b),pow(a,c))=pow(a,gcd(b,c))
ll gcd_sub(ll a, ll b) {
if (a < b)
swap(a, b);
if (b == 1)
return a;
return gcd_sub(b, a / b);
}三分法
对于求一个只包含一个波峰或者波谷函数的最值，通过求两个三分点进行比较，更接近目标的是好点，否则是坏点，坏点的那一边往里缩，因为目标和好点一定在坏点的一侧，坏点的那边就不包含最优解了
double left = 0, right = 1000;
double ans = 0x3f3f3f3f;
while (fabs(right - left) > lp) {
double ll = left + (right - left) / 3;
double rr = right - (right - left) / 3;
double rrans = 0;
double llans = 0;
for (int i = 1; i <= n; i++) {
rrans = max(rrans, a[i] * rr * rr + b[i] * rr + c[i]);//求解函数值
llans = max(llans, a[i] * ll * ll + b[i] * ll + c[i]);//求解函数值
}
ans = min(rrans, llans);
if (rrans < llans)//注意这里的更小值是好点，所以rr是好点，ll那边就要缩
left = ll;
else
right = rr;
}保序离散化
提前将所有要用到的下标存进alls里面（vector），队alls进行排序+去重，对于要用到的下标根据find函数去寻找，注意在返回时+1，相当于将这些下标映射在1~alls.size()。
sort(alls.begin(), alls.end());//排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重，unique函数返回不重复序列的后一个指针。
int find(int a) {
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = r + l >> 1;
if (alls[mid] < a)
l = mid + 1;
else
r = mid;
}
return l + 1;
}非保序离散化
用unordered_map和递增的idx赋予每一个下标一个独特的值，代码量简单，与alls区别是寻找和离散化过程结合在一起。
int idx=0;
unordered_map<int,int> res;
res.clear();
idx=0;
int find(int a) {
if (res.count(a) == 0)
res[a] = ++idx;
return res[a];
}字符串操作:
string str1("hello");
cout << str1 << endl;//hello
string str2("hello",2);//指定字符串的前2个字符
cout << str2 << endl;//he
string str3(str1, 2);//从下标2开始的字符的拷贝
cout << str3 << endl;//llo
string str4(str1, 2,2);//从下标2开始的2个字符的拷贝
cout << str4 << endl;//ll约数个数
给定 n个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7取模
假设k=a1^p1a2^p2a3^p3
那么约数个数为(p1+1)(p2+1)(p3+1)
约数之和
假设k=a1^p1a2^p2a3^p3
约数和为(pow(a1,0)+pow(a1,1)+….pow(a1,p1)(pow(a2,0)+pow(a2,1)+….pow(a2,p2))(pow(a3,0)+pow(a3,1)+….pow(a3,p3))
欧几里得
返回的是a和b的最大公约数
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}拓展欧几里得
适用于ax+by=gcd(a,b) 通解为x0+z*(b/p) y0-z*(a/p) z为任意整数 如果右边不是gcd(a,b) 则必须整除gcd(a,b)才有解，并且x0和y0要相应的改变
int exgcd(int a, int b, int& x, int& y)
{
if (!b)
{
x = 1;
y = 0;
return;
}
exgcd(b, a % b, y, x);
y = y - a / b * x;
}筛质数（n）:
bool st[100001000];
vector<int> res;
void get_prime(int n)
{
for (int a = 2; a <= n; a++)
{
if (!st[a])
{
res.push_back(a);
}
for (int j = 0; res[j]*a <= n; j++)
{
st[a * res[j]] = true;
if (a % res[j] == 0)
break;
}
}
}分解质因数（logn）:
unordered_map<int, int> res;
void help(int a)
{
for (int i = 2; i <= sqrt(a); i++)
{
while (a % i == 0)
{
res[i]++;
a = a / i;
}
}
if (a > 1)
res[a]++;
}秦九韶算法
针对a0pow(p,0)+a1pow(p,1)+a2pow(p,2)+….anpow(p,n);
long long int o=an;
for(int i=n-1;i>=0;i--)
o = (o * p + a[i]) % mod;矩阵快速幂
（要理解本质，ab的矩阵与bc的矩阵相乘结果为a*c的数组，遍历顺序是a到c到b）
void mul(ll an[][6], ll bn[][6],ll cn[][6])
{
ll temp[6][6];
memset(temp, 0, sizeof(temp));
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
for (int z = 0; z < 6; z++)
{
temp[i][j] =(temp[i][j]+ an[i][z] * bn[z][j] % N)%N;
}
}
}
memcpy(cn, temp, sizeof(temp));
}
void quickmi(ll an[6][6], ll p)
{
ll res[6][6];
memset(res, 0, sizeof(res));
for (int i = 0; i < 6; i++)
{
res[i][i] = 1;
}
while (p > 1)
{
if (p & 1)
{
mul(res, an,res);
p--;
}
p = p / 2;
mul(an, an,an);
}
mul(res, an,res);
memcpy(an, res, sizeof(res));
}1到n的所有数的约数(nlogn)
for (int i = 1; i < n; i++)
{
for (int j = i; j < n; j = j + i) {
yueshu[j].push_back(i);
}
}差分
int an[100010];
int bn[100010];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> an[i];
}
bn[1] = an[1];
for (int i = 2; i <= n; i++)//前缀和的逆向使用，an是bn的前缀和，由an得到bn，这样一次性操作an中k个数字同时增加减少，只需要对bn中两个数字进行操作即可
{
bn[i] = an[i] - an[i - 1];
}
while (m--)
{
int l, r, c;
cin >> l >> r >> c;
bn[l] += c;
if (r < n)
bn[r + 1] -= c;
}
an[1] = bn[1];
for (int i = 2; i <= n; i++)
{
an[i] =an[i-1]+bn[i];
}
for (int i = 1; i <= n; i++)
{
cout << an[i] << " ";
}
return 0;
}
