对J组知识点进行复习并将板子放入到本文中，每复习一个知识点，将会写一篇专栏。

\text{S Goal:}\ 200 \to 100

\text{NOIP Goal: }\ 140

注意事项与调试工作

暴力

对我来说，在NOIP的任何一道题都先打暴力，暴力就是用低级的数据结构来完成部分的题目要求。然后可以尝试打正解或极大分数，正确性可以使用对拍进行验证。

对拍

下面是文件名称所代表的意义：

文件名	意义
gen.cpp	生成随机样例
code.cpp	解答题目正解或部分分的代码
bl.cpp	暴力（一定要正确）
diff.cpp	比较函数

我们以 a+b problem 作为例子举例，环境为 Noi Ubuntu：

gen.cpp（生成随机值）

CPP

#include <bits/stdc++.h>
using namespace std;

int main()
{
    mt19937 rnd(time(0)); // 随机种子

    cout << rnd() % 100000+1 << ' ' << rnd() % 100000+1 << endl;
    return 0;
}

code.cpp（有

\frac{1}{20}

的概率出错）

CPP

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if((a + b) % 20 == 0) cout << a + b + 1 << endl;
    else cout << a + b << endl;
    return 0;
}

bl.cpp（暴力）

CPP

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

diff.cpp

未带后缀名的如 gen、code、bl 为编译后的文件。

CPP

#include <bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=1; ; i++)
    {
        cout << "No. " << i << endl;
        // 把数据生成器生成的数据写入 qwq.in(输入数据)
        system("./gen > qwq.in");
        // 把 qwq.in 的内容交给 code(正解) 运行，输出到 code.out
        system("./code < qwq.in > code.out");
        // 把 qwq.in 的内容交给 bl(暴力) 运行，输出到 code.ans
        system("./bl < qwq.in > code.ans");
        // 比较 code.out 与 code.ans，若不同则获得了一组错误样例
        if(system("diff code.out code.ans") != 0)
            {cout << "GG" << endl; break;}
    }
}

调试与检查

求代码中两地的时间差

CPP

auto t1 = clock();
int a = 0; for(int i=0; i<1e5; i++) rand();
auto t2 = clock();
cerr << t2-t1 << " ms" << endl;

防止 TLE

CPP

void dfs()
{
    if(sum > ans) return;
    if(clock() - t1 > 950) {cout << ans; exit(0);}
}

CPP

cout << "Running at Line" << __LINE__ << "\n";

检查 RE

ASAN & UBSAN （仅在Linux）

TERMINAL

-fsanitize=address -fsanitize=undefined

TERMINAL

g++ a.cpp -o a -std=c++14 -g
gdb a
// Used "r"; Quit "q".

STL 调试模式

TERMINAL

-D_GLIBCXX_DEBUG

防止数值溢出

TERMINAL

-ftrapv

注意事项

今年报名情况分析——机位上升、小学生不让考，对应获奖不会变难。
考试前的准备
- 注意休息，特别是前一晚。
- 赛前饮食要注意，别太撑。
- 比赛需要的物资准备好。
考试的一些经验：

审题：
- 如果不会被干扰：建议先把题目都看一遍，否则可以多看一题。
- 一定要看清楚题面，看看是否有偷藏信息。
- 样例一定要走一遍、样例解释一定要看懂。（防止读错题）
- 数据范围要看清。
解题：
- 题目再翻译很重要（自然描述——>数学描述）。
- 标注重要信息，防止忘记。
- 梳理思维链路，列出关键问题，不要想一出是一出。
- 先有解法后有代码，不要混在一起。
- 从简单开始（弱数据范围、弱约束条件）。
- 可以根据数据范围来排除一些问题。
编码：
- 想好总框架，想好实现，再写代码。
- 做好无经验实现的准备。
- 从大往小写。
调试：
- 造样例 + 中间过程输出。
- 二分法快速定位错误目标。
- 输出哪些信息很重要。
- 如果会对拍，那么会更好。
检查：
- 检查语法版本问题。
- 检查初始化和数组规模问题。
- 检查文件夹建立问题。
- 检查大样例正确性。
- 检查调试代码是否关闭。
比赛策略/心态建设：
- 部分分很重要。
- 策略根据情况（完成情况、剩余时间、题目的）
- 分数并不代表排名，不要被过度影响。
- 一定要留时间，不要一味追分。

考后的调整：
- 估分可以，但是找对人。
- 分数高低无所谓，比例才是最重要的。
- 记得复盘。
最后的几天如何备赛：
- 没刷真题的、看看真题熟悉难度（对应得分点的难度）。
- 根据自身能力，提前给一个大概的比赛策略。
- 一定要搞清楚对应地区的机器环境、防止出现一些奇怪的爆零问题。
- 拒绝高强度复习增加压力，以回顾和低烈度训练为主。
- 做好考前心理建设，考好考不好都要有心理准备。

std二分

std::binary_search：二分查找。

binary_search(v.begin(), v.end(), value)，其中 value 为需要查找的值。
std::lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 $x$ 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。

lower_bound(v.begin(),v.end(),x)
std::upper_bound：在一个有序序列中进行二分查找，返回指向第一个大于 $x$ 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。

upper_bound(v.begin(),v.end(),x)

CPP

int a[20] = {0, 1, 2, 4, 5, 5, 6, 7, 8, 10, 10};
cout << binary_search(a+1, a+10, 5) << endl;
cout << lower_bound(a+1, a+10, 5) - a << endl;
cout << upper_bound(a+1, a+10, 5) - a << endl;

out

OUT

ture 4 6

BFS

伪代码

CPP

bfs(s)
{
    queue<> q;
    q.push(s); vis[s] = true;
    while(!q.empty())
    {
        u = q.front();
        q.pop()
        for(v : e[u])
            if(!vis[v])
                q.push(v),
                vis[v] = true;
    }
}

最短路

oiwiki: https://oiwiki.com/graph/shortest-path/

朴素 Dijkstra

CPP

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int v, w;};
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    for(int i=1; i<=n; i++)
    {
        int u=0, mind=INF;
        for(int j=1; j<=n; j++)
            if(!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for(auto t : e[u])
            dis[t.v] = min(dis[t.v], dis[u] + t.w);
    }
}

signed main()
{
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Dijkstra 优化

CPP

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 2e5+5;
const int INF = (1<<31)-1;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push({s, 0});

    while(!q.empty())
    {
        int u = q.top().v;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        for(auto t : e[u])
            if (dis[t.v] > dis[u] + t.w) 
                dis[t.v] = dis[u] + t.w, 
                q.push({t.v, dis[t.v]});
    }
}

signed main()
{
    cin >> n >> m >> s;

    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Bellman Ford

CPP

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int u, v, w;};
vector<Edge> e;
int n, m, s, dis[MAX];

bool bellman_ford()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;

    bool flag = 0; // 判断一轮循环过程中是否发生松弛操作
    for(int i=1; i<=n; i++)
    {
        flag = false;
        // 对每一条边进行松弛操作
        for(auto t : e)
        {
            // 最短路长度为 INF 的点引出的边不可能发生松弛操作
            if(dis[t.u] == INF) continue;
            if(dis[t.v] > dis[t.u] + t.w)
                dis[t.v] = dis[t.u] + t.w,
                flag = true; 
        }
        // 没有可以松弛的边时就停止算法
        if(flag == false) break;
    }
    // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
    return flag;
}
signed main()
{
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back((Edge){u, v, w});
    }
    bellman_ford();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Floyd

CPP

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, f[105][105];

void floyd()
{
    for(int k=1; k<=n; k++)
        for(int x=1; x<=n; x++)
            for(int y=1; y<=n; y++)
                f[x][y] = min(f[x][y], f[x][k]+f[k][y]);
}

int main()
{
    freopen("f.in", "r", stdin);
    cin >> n >> m;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    
    for (int i = 0; i < m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);
    }
    floyd();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << f[i][j] << " ";
        cout << endl;
    }
    return 0;
}

单调队列与单调栈

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e6+5;
int a[MAX];

signed main()
{
    int n, k; cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    deque<int> dq;
    for(int i=1; i<=n; i++) // 维护单调递减
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 淘汰更老且大的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最小
    }
    cout << endl;
    dq.clear();
    for(int i=1; i<=n; i++) // 维护单调递增
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 淘汰更老且小的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最大
    }

    return 0;
}

并查集

高效处理集合的合并与查询。

CPP

#include<iostream>
using namespace std;

int fa[100005];
// 查询x节点的根节点编号
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

// 合并a、b所在集合
void merge(int a, int b) {fa[find(a)] = fa[find(b)];}

// 初始化n个集合
void init(int n) {for(int i=0;i<=n;i++) fa[i] = i;}

最小生成树

Kruskal

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int fa[MAX], n, m, k;
struct Edge{int u, v, w;} g[MAX];

int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int a, int b) {fa[find(a)] = fa[find(b)];}
void init(int n) {for(int i=0; i<=n; i++) fa[i] = i;}
bool cmp(Edge a, Edge b) {return a.w < b.w;}

void kruskal()
{
	int total = 0; // 已选了的边数
	int ans = 0; // 总的代价
	for(int i=1; i<=m; i++)
		if(find(g[i].u) != find(g[i].v))
		{
			merge(g[i].u, g[i].v);
			total ++;
			ans += g[i].w;
			if(total == n - k) {cout << ans; return;}
		}
	cout << "No Answer";
}

int main()
{
	cin >> n >> m >> k;
	if(n == k) {cout << 0; exit(0);}
	init(n);
	for(int i=1; i<=m; i++)
		cin >> g[i].u >> g[i].v >> g[i].w;
	sort(g+1, g+m+1, cmp);
	kruskal();
	return 0;
}

Prim

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, k, vis[MAX], dis[MAX], cnt=0, ans=0;

void prim()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; q.push({1, 0});

    while(!q.empty())
    {
    	if(cnt >= n) break;
        int u = q.top().v, w = q.top().w;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        ++cnt, ans += w;
        for(auto t : e[u])
            if (t.w < dis[t.v]) 
                dis[t.v] = t.w, q.push({t.v, t.w});
    }
}

signed main()
{
    cin >> n;

    for(int i=1; i<=n; i++)
    {
        int u, v;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    prim();
    if(cnt == n) cout << ans;
    else cout << "No MST";

    return 0;
}

拓扑排序

Kahn

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAX = 105;
queue<int> q;
vector<int> g[MAX], ans;
int rd[MAX], n;

void kahn()
{
	for(int i=1; i<=n; i++)
		if(rd[i] == 0) q.push(i);
	while(!q.empty())
	{
		int t = q.front(); q.pop();
		ans.push_back(t);
		for(auto v : g[t])
		{
			rd[v]--;
			if(rd[v] == 0) q.push(v);
		}
	}
	if(ans.size() != n) cout << "有环" << endl;
	else for(auto v : ans) cout << v << ' ';
}

int main()
{
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		int a; cin >> a;
		while(a) {g[i].push_back(a), rd[a]++; cin >> a;}
	}
	kahn();
	return 0;
}

DFS

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
vector<int> e[MAX];
int n, vis[MAX];

stack<int> ans;
void dfs(int u)
{
    for(auto v : e[u]) {if(vis[v]) continue; dfs(v);}
    vis[u] = 1; ans.push(u);
}

signed main()
{
    int n, a; cin >> n;
    for(int i=1; i<=n; i++)
        while(cin >> a && a)
            e[i].push_back(a);
    for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
    while(!ans.empty()) cout << ans.top() << ' ', ans.pop(); 
    return 0;
}

DP（部分完成）

背包DP

CPP

// 在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。
for(int i=1; i<=n; i++)
    for(int j=W; j>=w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

多重背包二进制分组优化

CPP

int cnt = 0; // 二进制分组后的物品数量
for(int i=1; i<=n; i++)
{
    int v_i, w_i, m_i; 
    cin >> v_i >> w_i >> m_i;
    for(int j=1; j<=m_i; j<<=1) // 二进制分组优化
        v[++cnt] = j * v_i, w[cnt] = j * w_i, m_i -= j;
    if(m_i) v[++cnt] = v_i * m_i, w[cnt] = w_i * m_i; // 剩余部分
}

区间DP（未完成）

DAG上DP（未完成）

https://oiwiki.com/dp/dag/

状压DP

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
const int M = 21;
int n, dp[N], dis[M][N];

int solve()
{
    for(int i=0; i < (1ll << n); i++) // 枚举状态（前驱状态 < 当前状态）
        for(int a=1, wa=1; a<=n; a++, wa<<=1) // 点编号为a，对应二进制位的值为 wa
            for(int b=1, wb=1; b<=n; b++, wb<<=1)
                if(a != b && (wa & i) == 0 && (wb & i) == 0) // b 没出现过
                    dp[i | wa | wb] = max(dp[i | wa | wb], dp[i]+dis[a][b]);
    return *max_element(dp, dp + (1ll << n));
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            cin >> dis[i][j], dis[j][i] = dis[i][j];
    cout << solve() << endl;

    return 0;
}

树形DP（未完成）

强连通分量

Kosraju

CPP

```cpp
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
vector<int> g1[MAX], g2[MAX], kos;
int vis[MAX], scc[MAX], n, m, scc_cnt=0;

void dfs1(int u)
{
    vis[u] = 1;
    for(auto v : g1[u])
        if(!vis[v]) dfs1(v);
    kos.push_back(u);
}

void dfs2(int u)
{
    scc[u] = scc_cnt;
    for(int v : g2[u])
        if(scc[v] == 0) dfs2(v);
}

void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    reverse(kos.begin(), kos.end());

    for(auto x : kos)
        if(scc[x] == 0) ++scc_cnt, dfs2(x);
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a, b; cin >> a >> b;
        g1[a].push_back(b);
        g2[b].push_back(a);
    }

    kosaraju();
    int cnt[MAX]; for(int i=1; i<=n; i++) cnt[scc[i]]++;
    int ans = 0;
    for(int i=1; i<=scc_cnt; i++)
        if(cnt[i] > 1) ans++;
    cout << ans;
    return 0;
}

缩点

CPP

int in[MAX], out[MAX];
set<int> edge[MAX];
void get_graph()
{
    for(int u=1; u<=n; u++)
    {
        int x = scc[u];
        scc_num += 1; // 点信息
        for(auto v : g1[u])
        {
            int y = scc[v];
            if(x != y) edge[x].insert(y), in[y] ++, out[x] ++; // 外部边信息
        }
    }
}

倍增

LCA

CPP

void dfs(int u, int f, int depth)
{
    fa[u][0] = f;
    dep[u] = depth;
    for(int i=1; i<=30; i++) 
        fa[u][i] = fa[fa[u][i-1]][i-1];

    for(auto i : e[u])
        if(i != f) dfs(i, u, depth+1);
}

int up(int x, int h)
{
    int i=0;
    while(h)
    {
        if(h & 1) x = fa[x][i];
        h >>= 1;
        i++;
    }
    return x;
}

int LCA(int a, int b)
{
    if(dep[a] < dep[b]) swap(a, b);
    a = up(a, dep[a]-dep[b]);
    if(a == b) return a; // attention;

    for(int i=30; i>=0; i--)
        if(fa[a][i] != fa[b][i])
            a = fa[a][i],
            b = fa[b][i];

    return fa[a][0];
}

ST表

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e6+5;
const int LOGMAX = 25;
int st[MAX][LOGMAX], logn[MAX];

void preLog()
{
    logn[1] = 0;
    logn[2] = 1;
    for(int i=3; i<MAX; i++) logn[i] = logn[i/2]+1; 
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    // 长度为1的区间最大值就是元素本身
    for(int i=1; i<=n; i++) cin >> st[i][0];
    // preLog();
    // 递推构建ST表: 
    // st[i][j] = max(st[i][j-1], st[i+2^(j-1)][j-1])
    for(int j=1; (1<<j) <= n; j++)
        for(int i=1; i+(1<<j)-1 <= n; i++)
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);

    for(int i=1; i<=m; i++)
    {
        int l, r; cin >> l >> r;
        int s = log2(r - l + 1); // s = logn[r - l + 1];
        cout << max(st[l][s] ,st[r-(1<<s)+1][s]) << endl;
    }
    return 0;
}

快速幂

CPP

long long p;
long long ksm(long long a, long long b)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1) ans *= a, ans %= p;
        a *= a; a %= p;
        b >>= 1;
    }
    return ans;
}

字符串哈希

CPP

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int P = 131;
ULL v[10005];

ULL value(string s)
{
    ULL ans=s[0];
    for(int i=1; i<s.size(); i++) ans = ans*P + s[i];
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        v[i] = value(s);
    }

    sort(v+1, v+n+1);
    int ans = 0;
    for(int i=1; i<=n; i++)
        if(v[i] != v[i+1]) ans ++;
    cout << ans;
    return 0;
}

离散化（未完成）

树上算法（未完成）

树状数组

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 5e5+5;
int a[MAX], t[MAX], n, m;

int lowbit(int x) {return x & -x;}
void add(int u, int v)
{
    while(u <= n)
        t[u] += v,
        u += lowbit(u);
}
int sum(int u)
{
    int ans = 0;
    while(u)
        ans += t[u],
        u -= lowbit(u);
    return ans;
}
int sum(int x, int y) {return sum(y) - sum(x-1);}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) {cin >> a[i]; add(i, a[i]);}
    for(int i=0;i<m;i++)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if(opt == 1) add(x, y);
        else if(opt == 2) cout << sum(x, y) << endl;
    }
    return 0;
}

线段树

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int MAX = 1e5+5;
struct Segment_Tree
{
	int l, r;
	long long tag, val;
}tree[MAX << 2];
int n, m, val[MAX];
inline int ls(int x) {return x << 1;}
inline int rs(int x) {return x << 1 | 1;}
inline bool out(int u, int l, int r) {if(tree[u].l > r || tree[u].r < l) return 1; return 0;}
inline bool in(int u, int l, int r) {if(tree[u].l >= l && tree[u].r <= r) return 1; return 0;}
inline void pushup(int u) {if(tree[u].l != tree[u].r) tree[u].val = tree[ls(u)].val + tree[rs(u)].val;}
inline void pushdown(int u)
{
	if(tree[u].l == tree[u].r) return;
	if(tree[u].tag)
	{
		tree[ls(u)].tag += tree[u].tag;
		tree[ls(u)].val += (tree[ls(u)].r - tree[ls(u)].l + 1) * tree[u].tag;
		tree[rs(u)].tag += tree[u].tag;
		tree[rs(u)].val += (tree[rs(u)].r - tree[rs(u)].l + 1) * tree[u].tag;
		tree[u].tag = 0; // *
	}
}

int query(int u, int l, int r)
{
	if(out(u, l, r)) return 0;
	if(in(u, l, r)) return tree[u].val;
	pushdown(u);
	return query(ls(u), l, r) + query(rs(u), l, r);
}

void modify(int u, int l, int r, int x)
{
	if(out(u, l, r)) return;
	if(in(u, l, r)) tree[u].tag += x, tree[u].val += (tree[u].r - tree[u].l + 1) * x;
	else
	{
		pushdown(u);
		modify(ls(u), l, r, x);
		modify(rs(u), l, r, x);
		pushup(u);
	}
}

void build(int u, int l, int r)
{
	tree[u].l = l;
	tree[u].r = r;
	if(l == r) {tree[u].val = val[l]; return;}

	int mid = (l + r) >> 1;
	build(ls(u), l, mid);
	build(rs(u), mid+1, r);
	pushup(u);
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> val[i];
    build(1, 1, n);

    while(m--)
    {
        int x, y, op, k;
        cin >> op;
        if(op == 1) {cin >> x >> y >> k; modify(1, x, y, k);}
        else {cin >> x >> y; cout << query(1, x, y) << endl;}
    }

    return 0;
}

文章操作

注意事项与调试工作

暴力

对拍

调试与检查

求代码中两地的时间差

防止 TLE

检查 RE

STL 调试模式

防止数值溢出

注意事项

std二分

BFS

朴素 Dijkstra

Dijkstra 优化

Bellman Ford

Floyd

Kruskal

Prim

Kahn

DFS

背包DP

区间DP（未完成）

DAG上DP（未完成）

状压DP

树形DP（未完成）

Kosraju

缩点

ST表

快速幂

字符串哈希

离散化（未完成）

树上算法（未完成）

字符串算法

01 Trie

KMP

序列分块

莫队

相关推荐

评论