奇技淫巧：Lambda表达式
最近学习到的奇技淫巧：Lambda表达式，将函数包括递归函数改为Lambda表达式写法，可节省大量时间，在大量调用下可能节省近一半时间。
说明
该语法过于复杂，见https://en.cppreference.com/w/cpp/language/lambda，本文仅写在算法竞赛下的应用。
该语法在OIWiki中有所提及，但是十分抽象，而这里将给出的简单易懂的用法，可能不太全面，在算法竞赛中已经够用了。
有关该语法是否可用问题：关于NOI系列活动中编程语言使用限制的补充说明，这表明NOI系列比赛中（包括noip，csp）已经开始使用C++14标准，而该表达式在C++11中就已经支持
具体用法：
无自身递归调用
auto 函数名 = [&](参数) -> 函数类型 { 内容 }；
给定 x 、y, 求x + y
一般写法
#include<bits/stdc++.h>
using namespace std;
int sum(int x, int y)
{
return x + y;
}
int main()
{
int x, y;
cin >> x >> y;
cout << sum(x, y);
}
Lambda表达式写法
#include<bits/stdc++.h>
using namespace std;
int main()
{
auto sum = [&](int x, int y) -> int
{
return x + y;
};//注意这里的分号
int x, y;
cin >> x >> y;
cout << sum(x, y);
}
有自身函数调用
注意：如果函数内存在对自生的调用，按上述写法是无法编译的，我们需要这样写：
int main()
{
auto 函数名 = [&](参数, auto&& self) -> 函数类型
{
//内容
//对自身调用时：
self(参数， self);
}；
//主函数内调用：
函数名（参数， 函数名）;//举例 ： int d = gcd(x, y, gcd);
};
gcd函数
Lambda表达式写法
#include<bits/stdc++.h>
using namespace std;
int main()
{
auto gcd = [&](int x, int y, auto&& self) -> int
{
if(y == 0) return x;
else return self(y, x % y, self);
};//注意这里的分号
int x, y;
cin >> x >> y;
cout << gcd(x, y, gcd);
}
线段树
一般代码
// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ll long long
#define MAXn 100010
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
#define add(x) tr[x].add
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sz(x) tr[x].sz
#define mid(x) tr[x].mid
using namespace std;
int n, m;
int a[MAXn];
struct SegmentTree
{
ll ls, rs, l, r, sum, add, sz, mid;
} tr[MAXn << 2];
ll read()
{
ll num = 0, w = 1;
char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') w = -1; ch = getchar(); }
while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
return num * w;
}
void build(int ind, int L, int R)
{
l(ind) = L;
r(ind) = R;
sz(ind) = R - L + 1;
mid(ind) = (L + R) >> 1;
if(L == R)
{
sum(ind) = a[L];
return;
}
ls(ind) = ind << 1;
rs(ind) = ind << 1 | 1;
int mid = (L + R) >> 1;
build(ls(ind), L, mid);
build(rs(ind), mid + 1, R);
sum(ind) = sum(ls(ind)) + sum(rs(ind));
}
void pushdown(int x)
{
if(add(x))
{
sum(ls(x)) += add(x) * sz(ls(x));
sum(rs(x)) += add(x) * sz(rs(x));
add(ls(x)) += add(x);
add(rs(x)) += add(x);
add(x) = 0;
}
}
void update(int x, int L, int R, ll k)
{
if(L <= l(x) && R >= r(x))
{
sum(x) += sz(x) * k;
add(x) += k;
return;
}
pushdown(x);
if(L <= mid(x)) update(ls(x), L, R, k);
if(R >= mid(x) + 1) update(rs(x), L, R, k);
sum(x) = sum(ls(x)) + sum(rs(x));
}
ll ask(int x, int L, int R)
{
if(L <= l(x) && R >= r(x))
{
return sum(x);
}
pushdown(x);
ll res = 0;
if(L <= mid(x)) res += ask(ls(x), L, R);
if(R >= mid(x) + 1) res += ask(rs(x), L, R);
return res;
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
while(m--)
{
ll flag, x, y;
flag = read(), x = read(), y = read();
if(flag == 1)
{
ll k;
k = read();
update(1, x, y, k);
}
else
{
printf("%lld\n", ask(1, x, y));
}
}
return 0;
}
Lambda代码
// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ll long long
#define MAXn 100010
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
#define add(x) tr[x].add
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sz(x) tr[x].sz
#define mid(x) tr[x].mid
using namespace std;
int n, m;
int a[MAXn];
struct SegmentTree
{
ll ls, rs, l, r, sum, add, sz, mid;
} tr[MAXn << 2];
int main()
{
auto read = [&]() -> ll
{
ll num = 0, w = 1;
char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') w = -1; ch = getchar(); }
while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
return num * w;
};
auto build = [&](int ind, int L, int R, auto&& self) -> void
{
l(ind) = L;
r(ind) = R;
sz(ind) = R - L + 1;
mid(ind) = (L + R) >> 1;
if(L == R)
{
sum(ind) = a[L];
return;
}
ls(ind) = ind << 1;
rs(ind) = ind << 1 | 1;
int mid = (L + R) >> 1;
self(ls(ind), L, mid, self);
self(rs(ind), mid + 1, R, self);
sum(ind) = sum(ls(ind)) + sum(rs(ind));
};
auto pushdown = [&](int x) -> void
{
if(add(x))
{
sum(ls(x)) += add(x) * sz(ls(x));
sum(rs(x)) += add(x) * sz(rs(x));
add(ls(x)) += add(x);
add(rs(x)) += add(x);
add(x) = 0;
}
};
auto update = [&](int x, int L, int R, ll k, auto&& self) -> void
{
if(L <= l(x) && R >= r(x))
{
sum(x) += sz(x) * k;
add(x) += k;
return;
}
pushdown(x);
if(L <= mid(x)) self(ls(x), L, R, k, self);
if(R >= mid(x) + 1) self(rs(x), L, R, k, self);
sum(x) = sum(ls(x)) + sum(rs(x));
};
auto ask = [&](int x, int L, int R, auto&& self) -> ll
{
if(L <= l(x) && R >= r(x))
{
return sum(x);
}
pushdown(x);
ll res = 0;
if(L <= mid(x)) res += self(ls(x), L, R, self);
if(R >= mid(x) + 1) res += self(rs(x), L, R, self);
return res;
};
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n, build);
while(m--)
{
ll flag = read(), x = read(), y = read();
if(flag == 1)
{
ll k;
k = read();
update(1, x, y, k, update);
}
else
{
printf("%lld\n", ask(1, x, y, ask));
}
}
return 0;
}
时间比较
- 一般做法
- Lambda表达式