自己码代码能力太差了

二分

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n, m;cin >> n >> m;
    for (int i=0;i<n;i++) cin >> a[i];
    while (m --) {
        int q; cin >> q;
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= q) r = mid;
            else l = mid + 1;
        }
        if (a[l] != q) puts("-1 -1");
        else {
            printf("%d ", l);
            l = 0, r = n-1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (a[mid] <= q) l = mid;
                else r = mid - 1;
            }
            printf("%d ", l);
            puts("");
        }
    }
    return 0;
}

实域二分

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

int main()
{
    double n;
    cin >> n;
    double l = -10000, r=10000;
    for (int i=0;i<100;i++) {
        double mid = (l + r)/2;
        if (mid * mid * mid > n) r = mid;
        else l = mid;
    }
    printf("%.6lf", l);
}

前缀

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],s[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i ++) cin >> a[i];
    for (int i = 1;i <= n;i ++) s[i] = s[i-1] + a[i];

    while (m --) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

二维

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N][N];
int main()
{
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) 
            cin >> s[i][j];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
        }

    while (k -- ) {
        int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]<<endl;
    }    
}

差分

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N], s[N];
int main()
{
    int n , m; cin  >> n >> m;

    for (int i = 1;i <= n; i ++ ) cin >> a[i];
    for (int i = 1;i <= n; i ++ ) b[i] = a[i] - a[i - 1];

    while (m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c, b[r+1]-=c;
    }
    for (int i = 1;i <= n;i ++ ) b[i]+=b[i-1];
    for (int i = 1; i <=n ;i ++ ) cout << b[i] << " ";
}

双指针

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], st[N];
int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n;i ++ ) cin >> a[i];
    int res = 0;
    for (int i = 1, j = 1; i <= n; i ++ ) {
// 做标记 记录出现次数
        st[a[i]] ++ ;
// 如果重复 则更新序列起始位置
        while (j <= i && st[a[i]] > 1) st[a[j]] --, j ++ ;
        res = max(res, i-j+1);
    }
    cout << res << endl;
    return 0;
}

双指针

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m,k;
int a[N], b[N];
int main()
{
    cin >> n >> m >> k;
    for (int i=0;i<n;i++) cin>>a[i];
    for (int i=0;i<m;i++) cin>>b[i];

    for (int i=0,j=m-1;i<n;i++) {
        while (~j && b[j]+a[i]>k) j --;
        if (a[i]+b[j]==k&&~j) printf("%d %d",i,j);
    }
    return 0;
}

双指针

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n, m;
int main()
{
    cin >> n >> m;
    for (int i=0;i<n;i++) cin >> a[i];
    for (int i=0;i<m;i++) cin >> b[i];

    int i=0, j=0;
    while (j < m && i < n) 
    {
        if (a[i]==b[j]) j ++ , i++;
        else j ++ ;
    }
    if (i==n) puts("Yes");
    else puts("No");
    return 0;
}

位运算

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T; cin >> T;
    while (T--) {
        int a; cin >> a;
        int res=0;
        while (a) {
            int m = a % 2;
            a/=2;
            if (m) res++;
        }
        cout << res << " ";
    }
    return 0;
}

离散化

#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, m;
typedef long long LL;
typedef pair<int, int> PII;

vector<int> alls;
vector<PII> adds, que;
int a[N], s[N];
void discreate() 
{
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
}
int query(int x)
{
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
int main()
{
    cin >> n >> m;
    for (int i=0;i<n;i++) {
        int id, val;
        cin >> id >> val;
        adds.push_back({id, val});
        alls.push_back(id);
    }
    for (int i=0;i<m;i++) {
        int l, r;
        cin >> l >> r;
        que.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    discreate();
    for (auto t : adds) 
    {
        int id=query(t.first);
        a[id] += t.second;
    }
    for (int i=0;i<alls.size();i++) {
        if (i==0) s[i]=a[i];
        else s[i] = s[i-1] + a[i];
    }
    for (auto &[l, r] : que) 
    {
        int nl=query(l), nr=query(r);
        cout<<s[nr]-s[nl-1]<<endl;
    }
    return 0;
}

区间和

//sort(s.begin(),s.end(),[](vector<int> a,vector<int> b){
//    return a[1]<b[1]; 
//    });//按照s[i][1]升序排序
//
// sort(s.begin(),s.end(),[](vector<int> a,vector<int> b){
//       return a[0]>b[0]; 
//     });//按照s[i][0]降序排序

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> a;
int n;
int main()
{
    cin >> n;
    while (n --) {
        int l, r; cin >> l >> r;
        a.push_back({l, r});
    }
    sort(a.begin(),a.end());
    int l=-2e9, r=-2e9;
    int res=0;
    for (int i=0;i<a.size();i++) {
        if (a[i].first > r) {
            res++, l = a[i].first, r = a[i].second; // 开新段
        }
        else r = max(a[i].second, r); // 注意这里的R更新
    }
    cout<<res<<endl;
    return 0;
}

单调栈

先判断 将不符合条件的剔除 然后将元素加入到栈中

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N], tt;

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i ++ ) 
    {
        int a;
        cin >> a;
        while (tt && stk[tt] >= a) tt --; // 把大元素弹出去
        if (tt == 0) printf("%d ", -1);
        else printf("%d ", stk[tt]);
        stk[++ tt] = a;
    }
    return 0;
}

对顶栈

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010, INF=1e9;
int stl[N], ttl, str[N], ttr;
int s[N], f[N]={-INF};
int main()
{
    int n; cin >> n;
    while ( n--) {
        char op[2]; int x;
        cin >> op;
        if (*op == 'I') {
            cin >> x;
            stl[++ttl] = x; 
            s[ttl] = s[ttl-1]+x;
            f[ttl] = max(s[ttl], f[ttl-1]);
        }
        else if (*op == 'D') {
            if (ttl > 0) ttl --;
        }
        else if (*op == 'L') {
            if (ttl > 0) str[++ ttr] = stl[ttl --];
        }
        else if (*op == 'R') {
            if (ttr > 0) {
            stl[++ ttl] = str[ttr --];
            s[ttl] = s[ttl-1] + stl[ttl];
            f[ttl] = max(f[ttl - 1], s[ttl]);
            }
        }
        else {
            cin >> x;
            printf("%d \n", f[x]);
        }
    }
    return 0;
}

栈的搜索

#include <bits/stdc++.h>
using namespace std;
int n,cnt=20;
vector<int> path;
stack<int> stk;
// 搜索
void dfs(int u)
{
    if (!cnt) return ;
    if (path.size()==n) {
        cnt --;
        for (int i=0;i<n;i++) cout<<path[i];
        puts("");
        return;
    }
    if (stk.size()) {
        path.push_back(stk.top());
        stk.pop();
        dfs(u);
        // 回溯
        stk.push(path.back()); // 将弹出去的再加回来
        path.pop_back();// 将路径上加进来的剔除
    }
    if (u <= n) {
        stk.push(u);
        dfs(u + 1);
        stk.pop();
    }
    return ;
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

括号 栈的使用

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
string str;
stack<int> stk;
int main()
{
    cin >> str;
    int len = 0;
    for (int i = 0; i < str.size(); i ++ )
    {
        if (str[i] == ')' && stk.size() && str[stk.top()] == '(') stk.pop();
        else if (str[i] == '}' && stk.size() && str[stk.top()] == '{') stk.pop();
        else if (str[i] == ']' && stk.size() && str[stk.top()] == '[') stk.pop();
        else stk.push(i);

        if (stk.size()) len = max(len, i - stk.top());
        else len = max(len, i + 1);
    }
    cout<<len;
    return 0;
}

并查集

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int n, m;
int find(int x) // 找父节点
{
    if (p[x] == x) return p[x];
    return p[x] = find(p[x]);
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    while (m -- )
    {
        char op[2]; int a, b;
        cin >> op >> a >> b;
        if (*op == 'M') {
            a = find(a), b = find(b);
            p[a] = b;
        }
        else {
            a = find(a), b = find(b);
            if (a == b) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N], c[N];
int find(int x)
{
    if (p[x] != x) return p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i, c[i] = 1;
    while (m --) {
        string op;
        int a, b;
        cin >> op;
        if (op == "C") {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b) p[a] = b, c[b]+=c[a];
        }
        else if (op == "Q1") {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a == b) puts("Yes");
            else puts("No");
        }
        else {
            cin >> a;
            a = find(a);
            printf("%d\n",c[a]);
        }
    }
    return 0;
}

Trie树 记不住啊！

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int son[N][30], idx=1, cnt[N];
char str[N];
void insert(char *str)
{
    int len=strlen(str), p = 1;
    for (int i = 0; i < len; i ++ )
    {
        int ch = str[i] - 'a';
        if (son[p][ch] == 0) son[p][ch] = ++ idx;
        p=son[p][ch];
    }
    cnt[p] ++;
}
int query(char *str)
{
    int len=strlen(str), p = 1;
    for (int i = 0; i < len; i ++)
    {
        int ch = str[i] - 'a';
        if (son[p][ch] == 0) return 0;
        p = son[p][ch];
    }
    return cnt[p];
}
int main()
{
    int n; cin >> n;
    while (n -- )
    {
        char op[2]; cin >> op >> str; 
        if (*op == 'I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[N][30], cnt[N], idx=1;
char str[N];
void insert(char *str)
{
    int len = strlen(str), p = 1;
    for (int i = 0; i < len; i ++ )
    {
        int ch = str[i] - 'a';
        if (!son[p][ch]) son[p][ch] = ++ idx;
        p = son[p][ch];
    }
    cnt[p] ++ ;
}
int query(char *str)
{
    int len = strlen(str), p = 1;
    int res=0;
    for (int i = 0; i < len; i ++) 
    {
        int ch = str[i] - 'a';
        if (!son[p][ch]) break;
        p = son[p][ch];
        res += cnt[p];
    }
    return res;
}
int main()
{
    int n, m; cin >> n >> m;
    while (n -- ) {
        cin >> str;
        insert(str);
    }
    while (m -- ) {
        cin >> str;
        cout << query(str) << endl;
    }
    return 0;
}

有待理解

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 3000010;
int son[M][2], idx, a[N];
void insert(int a) {
    int p = 0;
    for (int i = 30; ~i; i --) {
        int u = a >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}
int query(int a)
{
    int p = 0;
    int res = 0;
    for (int i = 30; ~i;i --) {
        int u = a >> i & 1;
        if (son[p][!u]) { // 存在对立面
            p = son[p][!u];
            res += 1 << i;
        }
        else {
            p = son[p][u];
        }
    }
    return res;
}
int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i], insert(a[i]);

    int res = 0;
    for (int i = 0; i < n; i ++ ) {
        int t = query(a[i]); res = max(res, t);
    }
    cout << res;
    return 0;
}

堆

// 堆 和贪心
// 按时间排序
// 这道题有个有趣的特点就是 天数可以随便 5天到期的东西（如果之前没有比他过期还短的商品）可以先卖出
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
int main()
{
    int n;
    while (cin >> n) 
    {
        vector<PII> v(n);
        for (int i = 0; i < n; i ++ ) cin >> v[i].y >> v[i].x; // 对时间从小到大排序
        sort(v.begin(), v.end());
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 0; i < n; i ++ ) {
            if (v[i].x > heap.size()) heap.push(v[i].y);
            else if (v[i].x == heap.size() && v[i].y > heap.top()) {
                heap.pop();
                heap.push(v[i].y);
            }
        }
        int res = 0;
        while (heap.size()) {
            res += heap.top();
            heap.pop();
        }
        cout<<res<<endl;
    }
    return 0;
}

堆 多路归并

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 20010;
typedef pair<int, int> PII;
int a[N], T, n, m, b[N], c[N];
void merge() 
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (int i = 1; i <= n; i ++) heap.push({a[1] + b[i], 1});// 保持一个指针在动
    int cnt = 1;
    while (cnt <= n)
    {
        int k = heap.top().x;
        int v = heap.top().y;
        heap.pop();
        c[cnt ++] = k;
        heap.push({k - a[v] + a[v+1], v + 1});
    }
    for (int i = 1; i <= n; i ++ ) a[i] = c[i];
}
int main()
{
    cin >> T;
    while (T --) {
        cin >> m >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        sort(a+1, a+n+1);
        m --;
        while (m -- ) { 
            for (int i = 1; i <= n; i ++) cin >> b[i]; 
            merge();
        }
        for (int i = 1; i <= n; i ++ ) cout << a[i] << " ";
        puts("");
    }
    return 0;
}

堆 贪心

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int a[N];
priority_queue<int, vector<int>, greater<int>> heap;
int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        // heap.push(a[i]);
    }
    for (int i = 1; i <= n; i ++) heap.push(a[i]);
    int res = 0;
    while (heap.size()>1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    cout << res;
}

DFS

#include <bits/stdc++.h>
using namespace std;
int n;
int path[8];
bool st[8];
void dfs(int u)
{
    if (u == n+1) {
        for (int i = 1; i <= n; i ++ ) cout << path[i] << " ";
        puts("");
        return ;
    }
    for (int i = 1; i <= n; i ++ ) {
        if (!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u+1);
            st[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

DFS

#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int n;
char g[10][10], path[10][10];
bool st1[N], st2[N], st3[N];

void dfs(int u)
{
    if (u == n) {
        for (int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return ;
    }
    for (int i = 0; i < n; i ++ )
    {
        if (!st1[i] && !st2[i + u] && !st3[n - u + i]) {
            g[u][i] = 'Q';
            st1[i] = st2[i + u] = st3[n - u + i] = true;
            dfs(u + 1);
            st1[i] = st2[i + u] = st3[n - u + i] = false;
            g[u][i] = '.';
        }
    }
    return ;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) 
        for (int j = 0; j < n; j ++) 
            g[i][j] = '.';
    dfs(0);
    return 0;
}

Flood Fill

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
char g[N][N];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; // 八方向位移
int n, m, ans = 0;
bool st[N][N];
void FF(int i, int j) {
    queue<PII> que;
    que.push({i,j});
    st[i][j] = true;

    while (que.size()) {
        auto &[nni, nnj] = que.front();
        que.pop();

        for (int a = 0; a < 8; a ++)
        {
            int ni = nni + dx[a], nj = nnj + dy[a];
            if (!st[ni][nj] && ni >= 1 && ni <= n && nj >= 1 && nj <= m && g[ni][nj] == 'W') {
                st[ni][nj] = true;
                que.push({ni, nj});
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++)
            cin >> g[i][j];

    int res = 0;    
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) 
            if (g[i][j] == 'W' && st[i][j] == false) FF(i, j), ans ++;
    }        
    cout << ans;
    return 0;
}

FolldFill

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 55;
int n, m, ans;
int g[N][N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
void bfs(int x, int y)
{
    queue<PII> que;
    que.push({x, y});
    st[x][y] = true;

    while (que.size())
    {
        int k = que.front().first;
        int v = que.front().second;
        que.pop();
        ans ++ ;
        for (int i = 0; i < 4; i ++) {
            int xx = k + dx[i], yy = v + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !st[xx][yy] && !(g[k][v] >> i & 1)) { // 最后一个条件选择错了g的变量 
                que.push({xx, yy});
                st[xx][yy] = true;
            } 
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];

    int res = 0, area = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (!st[i][j]) 
            {
                ans = 0;
                bfs(i, j);
                res ++ ;
                area = max(area, ans);
            }
    cout << res << endl << area << endl;
    return 0;
}

FolldFill

// 条件1 S的格子具有相同的高度 其实简化了本题
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int g[N][N];
int n;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
bool st[N][N];
bool bfs(int x, int y, bool &has_hi, bool &has_lo)
{
    queue<PII> que;
    que.push({x, y});
    st[x][y] = true;

    while (que.size())
    {
        int k = que.front().first;
        int v = que.front().second;
        que.pop();

        for (int i = 0; i < 8; i ++ )
        {
            int xx = k + dx[i], yy = v + dy[i];
            if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
            if (g[xx][yy] != g[k][v]) {
                if (g[xx][yy] > g[k][v]) has_hi = true;
                else has_lo = true;
            }
            else {
                if (st[xx][yy]) continue;
                que.push({xx, yy});
                st[xx][yy] = true;
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    int valley = 0, peak = 0;        
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) 
            if (!st[i][j]) 
            {
                bool has_hi = false, has_lo = false;
                bfs(i, j, has_hi, has_lo);
                if (!has_lo) valley ++ ;
                if (!has_hi) peak ++ ;
            }
    cout << peak << " " << valley << endl;
    return 0;
}

dfs

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int ans = 18;
int a[N], tcap[N];
int cap, n;
bool cmp(int a,int b)
{
    return a > b;
}
void dfs(int u, int cnt)
{
    if (cnt >= ans) return; // 这里需要提前退出 不然会卡在最后一个数据
    if (u == n + 1)  {
        ans = min(ans, cnt);
        return ;
    }

    for (int i = 1; i <= cnt; i ++) {
        if (tcap[i] + a[u] <= cap) {
            tcap[i] += a[u];
            dfs(u + 1, cnt);
            tcap[i] -= a[u];
        }
    }
    tcap[cnt + 1] = a[u];
    dfs(u + 1, cnt + 1);
    tcap[cnt + 1] = 0;
}
int main()
{
    cin >> n >> cap;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    sort(a+1, a+n+1, cmp);
    dfs(1, 1);
    cout << ans;
    return 0;
}

bfs记录最短路径 (值得记忆)

// 记录路径的关键在于 我们无法知道该点是如何向其他点转移的 但我们知道这个点是怎么来的 构成一个拓扑 (所以需要一个pre记录来时的路径)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N], n, cnt;
bool st[N][N];
PII path[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int x, int y)
{
    queue<PII> que;
    que.push({x, y});
    memset(path, -1, sizeof path);
    st[x][y] = true;
    path[x][y] = {0, 0};

    while (que.size())
    {
        auto &[k, v] = que.front();
        que.pop();
        if (k == 0 && v == 0) return ;
        for (int i = 0; i < 4; i ++ )
        {
            int xx = k + dx[i], yy = v + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < n && !st[xx][yy] && g[xx][yy] == 0) {
                path[xx][yy] = {k, v};
                que.push({xx, yy});
                st[xx][yy] = true;
            } 
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0;i < n ; i ++ )
        for (int j = 0; j < n; j ++) 
            cin >> g[i][j];
    // 反向求解 记录是由何转移而来 dp记录路径也是这个思路
    bfs(n - 1, n - 1);
    PII end = {0, 0};
    while (true) {
        printf("%d %d\n", end.first, end.second);
        if (end.first == n - 1 && end.second == n - 1) break;
        end = path[end.first][end.second];
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 155;
char g[N][N];
int dist[N][N];
int n, m;
bool st[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int bfs(int x, int y)
{
    queue<PII> que;
    que.push({x, y});
    st[x][y] = true;
    dist[x][y] = 0;

    while (que.size())
    {
        auto &[k, v] = que.front();
        que.pop();
        if (g[k][v] == 'H') return dist[k][v];
        for (int i = 0; i < 8; i ++ )
        {
            int xx = k + dx[i], yy = v + dy[i];
            // 这里建议写成continue 如果条件太多 不好判断 运行也会超时
            if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if (st[xx][yy]) continue;
            if (g[xx][yy] == '*') continue;

            if (dist[xx][yy] >= dist[k][v] + 1) {
                dist[xx][yy] = dist[k][v] + 1;
                que.push({xx, yy});
                st[xx][yy] = true;
            }
        }
    }
    return 0;
}
int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'K') {
                cout << bfs(i , j);
                break;
            }
    return 0;        
}

线段树

// 没有懒标记的线段树 （本体需要自动维护序列的长度）

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
struct Node{
    int l, r;
    int maxv;
} tr[N * 4]; // 线段树的结构
void pushup(int u)
{
    tr[u].maxv  = max(tr[u*2].maxv, tr[u*2+1].maxv);
}
void build(int u, int l, int r)
{
    if (l == r) {tr[u]={l,l}; return; }
    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
void insert(int u, int x, int c)
{
    if (tr[u].l == tr[u].r) {tr[u].maxv = c; return ;}
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) insert(u*2, x, c); // 在左半边 
    if (x > mid) insert(u*2+1, x, c);// 在右半边
    pushup(u); // 上传结果
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l &&  tr[u].r <= r) return tr[u].maxv;
    int mid = tr[u].l + tr[u].r >> 1;
    int maxv = 0;
    if (l <= mid) maxv = max(maxv, query(u*2,l,r));
    if (r > mid) maxv = max(maxv, query(u*2+1,l,r));
    return maxv;
}
int main()
{
    int len = 0; int last = 0;
    cin >> n >> m;
    build(1, 1, n);
    while (n -- ){
        char op[2]; int a;
        cin >> op >> a;
        if (*op == 'Q') {
            last = query(1, len - a + 1, len);
            cout << last << endl;
        }
        else {
            insert(1, len + 1, ((long long) last + a) % m);
            len ++ ;
        }
    }
    return 0;
}

// 单点修改
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int a[N], n, m;
struct Node {
    int l, r;
    int sum, lmax, rmax, tmax;
} tr[4 * N];
void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum; // 更新u的和
    u.lmax = max(l.lmax, l.sum + r.lmax); // 更新u的左子树最大值
    u.rmax = max(r.rmax, r.sum + l.rmax); // 更新u的右子树最大值
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax); // 更新u的最大值    
}
void pushup(int u)
{
    pushup(tr[u], tr[u*2], tr[u*2+1]);
}
void build(int u, int l, int r)
{
    if (l == r) {
        tr[u] = {l, r, a[l], a[l], a[l], a[l]};
        return ;
    }
    tr[u] = {l , r};
    int mid = l + r >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    pushup(u);
}
void insert(int u, int x, int v)
{
    if (tr[u].l == x &&  tr[u].r == x) {
        tr[u] = {x,x,v,v,v,v};
        return ;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) insert(u*2, x, v);
    else insert(u*2+1, x, v);
    pushup(u);
}
Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
// Node query(int u, int l, int r)
// {
//     if (tr[u].l >= l && tr[u].r <= r) return tr[u];
//     else
//     {
//         int mid = tr[u].l + tr[u].r >> 1;
//         if (r <= mid) return query(u << 1, l, r);
//         else if (l > mid) return query(u << 1 | 1, l, r);
//         else
//         {
//             auto left = query(u << 1, l, r);
//             auto right = query(u << 1 | 1, l, r);
//             Node res;
//             pushup(res, left, right);
//             return res;
//         }
//     }
// }

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1, 1, n);
    while (m -- )
    {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 1) {
            if (x > y) swap(x, y);
            printf("%d\n",query(1, x, y).tmax);
        }
        else {
            insert(1,x,y);
        }
    }
    return 0;
}