思路：1.可以使用懒标记线段树进行区间修改和查询，但是这样写不够萌新。
           2. 使用二分 + 前缀和的思想解决。二分体现在二分答案，即去寻找最小的订单个数使教室无法安排。具体的，在每次check时，使用一个数组b来维护，对于区间[s,t]，令b[s] += d表示从s天开始每天多用d 个，b[t+1] -= d表示第t+1条把这d个释放掉。然后利用前缀和便可以得知每天需要的教室数目，与a对比即可。时间复杂度O(nlogm),代码如下：
#include <bits/stdc++.h>

typedef long long ll;

const int N = 1e6+10;

ll a[N], b[N];
std::array<int,3> all[N];
int n, m;

void solve()
{
    std::cin >> n >> m;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=m;i++) {
        int d, t, s; std::cin >> d >> s >> t;
        all[i] = {d,s,t};
    }
    
    int l = 1, r = m+1;
    while(l<r) {
        int mid = (l+r)>>1;
        auto check = [&](int x) {
            memset(b,0,sizeof b);
            for(int i=1;i<=std::min(x,m);i++) {
                auto [d,s,t] = all[i];
                b[s] += d, b[t+1] -= d;
            }
            for(int i=1;i<=n;i++) b[i] += b[i-1];
            for(int i=1;i<=n;i++) if(b[i]>a[i]) return true;
            return false;
        };
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    if(r==m+1) std::cout << 0 << "\n";
    else std::cout << -1 << "\n" << l << "\n";
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int t = 1;
    while(t --)
        solve();
    return 0;
}
E 带路

思路：题目数据范围有误，M,N 实际上是小于等于50的，所以我们直接进行暴力dfs求解。下面贴上了代码，数组mp是用于存储图形，vis则是记忆化数组，用于标记这个点是否到过，dir数组则是每个位置可能移动的四个方向：上下左右。在dfs过程中，我们需要注意判别边界和这个点是否已经到过。需要注意每次遇到.需要把记忆化数组重新初始化。 

#include<bits/stdc++.h>
using namespace std;
char mp[55][55];
int vis[55][55];
vector<int> ans;
int m,n;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};

void dfs(int x,int y,int deep){
    int cnt = 0;
    for(int i = 0;i < 4;i ++){
        int dx = x + dir[i][0],dy = y + dir[i][1];
        if(dx >= 0 && dx <= m && dy >=0 && dy <=n && vis[dx][dy] == 0 && mp[dx][dy] == '.'){
            vis[dx][dy] = 1;
            dfs(dx,dy,deep + 1);
            vis[dx][dy] = 0;
            cnt ++;
        }else{
            ans.push_back(deep);
        }
    }
    if(cnt == 0) return;
}

void solve()
{
    cin >> m >> n;
    for(int i = 0;i < m;i ++)
        for(int j = 0;j < n;j ++) cin >> mp[i][j];
    for(int i = 0;i < m;i ++){
        for(int j = 0;j < n;j ++){
            if(mp[i][j] == '.'){
                memset(vis,0,sizeof(vis));
                vis[i][j] = 1;
                dfs(i,j,1);
            }   
        }
    }
    sort(ans.begin(),ans.end());
    cout << ans.back() << endl;
}


signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    //cin >> t;
    while(t --)
        solve();
    return 0;
}
K 质量检测

思路：滑动窗口模板题，思想类似于双指针，滑动窗口详解 - 知乎 (zhihu.com)。时间复杂度O(n)。也可以使用ST表等方法。 

#include<bits/stdc++.h>
using namespace std;
deque<int> q;
void solve()
{
    int n,m;scanf("%d %d",&n,&m);
    vector<int> a(n+1);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++){
        while(!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if(i >= m){
            while(!q.empty() && q.front() <= i - m) q.pop_front();
            printf("%d\n",a[q.front()]);
        }
    }
    return ;
}


signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    //cin >> t;
    while(t --)
        solve();
    return 0;
}