这篇文章将作为 CSP-J/S2020 和 期中考试 的游记。

11/4

考语文和物理。

刚考完语文觉得悬，时间其实也蛮紧张的。出来对答案发现有几个点争论不休，没有定论。不过语文作为主观科目，对答案也对不出什么东西。

结果物理就是当头一棒，尤其是计算题，两道全错，第一题漏解，第二题列式错误，完美避开正确答案。实验题其实也没有把握，不过据理力争地分析了最后一道实验题和作图题。

回家之后码了一道 广搜题目，学了康托展开+树状数组维护。然后刷了几套数学，看了几遍历史书。22：00睡觉了（作业要求21：30）。

11/5

数学和历史。

老师的话不可信。

我一直以为 HY 的老师诚实，结果……数学考试恶心至极，时间还紧，直接放弃了填空最后一题和大题最后一小问，答案对下来已经扣了至少 $10$ 分了。

历史也不怎么来得及，还有一题卡住了。

颓betway必威体育官方。用 unordered_map 水了一道哈希（oiwiki 上的例题），然后随机跳题跳了一道很水的贪心（区间覆盖），切了。最后用线段树 AC 了树状数组，算是复习，然后自学了 RMQ。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=1e5+5,maxl=20;
int a[maxn],n,m;
//<------------head-------------> 
#define re register
#define gg (getchar())
inline int read(){
    register int x=0,f=1;
    re char c=gg;
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=gg;
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=gg;
    }
    return x*f;
}
//<----------FastIO----------->
class ST{
    public:
    inline void init(){
        n=read(),m=read();
        rep(i,1,n) a[i]=read();
        l[0]=-1;
        rep(i,1,n)
        {
            f[i][0]=a[i];
            l[i]=l[i>>1]+1;
        }
        rep(j,1,maxl)
        {
            for(int i=1;i+(1<<j)-1<=n;i++)
                f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//Time: O(NlogN)
        }
    }
    inline int query(int x,int y){
        int k=l[y-x+1];
        return max(f[x][k],f[y-(1<<k)+1][k]);// Time: O(1)
    }
    private:
        int l[maxn],f[maxn][maxl+5];//Memory: O(NlogN)
};
ST s;
//<---------RMQ------------>
int main(){
    s.init();
    while(m--){
        int x=read(),y=read();
        printf("%d\n",s.query(x,y));
    }
    return 0;
}

明天英语和道法，不算强项，仔细点吧，加油 rp++！

考完后准备复习图论和基础算法，再练几道动态规划吧。

11/6

英语自认为还好，道法也还行。英语出来对答案发现基础好像错了挺多，首字母还好。据收卷同学说我道法写得是全组最少的。

本打算复习 OI 的，结果STEM课题小组要去写论文，于是荒废了半天的时光。晚上有课，因此备战的时间只剩下一个小时，顿时慌的一批。

没有再去看新的算法，自己列了一个提纲，过了几眼高精、逆序对、快速幂、Dijkstra、线段树的板子，公交上还复习了一下MST。晚上回来开始研究 dp 背包和 LCS $O(n\log n)$。

11/7

CSP RP++！

一直以为上午提高组，紧张至极。到考场发现上午普及，安全。

准时开考，有点不适应环境，T1 卡了一会儿，觉得比去年麻烦，想到转二进制，还开了个辅助数组做出来的。T2 一开始没想到正解，用 sort and nth_element 暴力都失败了，毕竟复杂度是 $O(n^2\log n)$。考虑二分加插排，瞄到数据 $n$ 的上面一行，限制 $score\le 600$，发现 $O(600n)$ 能过，于是码了一个桶排碰运气。

T3 一开始以为是简单的表达式求值，用栈模拟，结果写着写着发现有些复杂，跳到了 T4。“方格取数”第一眼先暴力 dfs，结果还调了好久，拿了 20 分。再看发现跟betway必威体育官方某一次月赛的“雷雨”有点像，并且 $|w|\le 10^4$，于是找了个办法化掉了负边权用 Dijkstra 做。连边方式想了一会儿，最后再计算取到的数和 这题 有点像。

打完发现大样例过了。再回来测样例一，结果SPFA了，原来没法走环。

没思路，跑回 T3，打了一个暴力保佑。

考试出来才知道：T2 好多人没想到桶排；T4 是动态规划；T3 全输出 0 可以拿很多分……

提高组要抱灵了qaq

就这样担惊害怕的进了考场。密码输了好久不对，拿到 T1 就慌了。听到旁边两位同学都在飞速 typing，于是决定果断放弃，来看T2。发现这题很简单，随便码了一段居然大样例也过了。检查数据范围： $k\le 64$ 用 unsigned long long，又试了几组极限数据，判断了一下边界，觉得切了一题。

T3 T4 明显不会，只能骗分，暴力拿了45回去看T1了。

T1 只好硬着头皮慢慢做，还列了一个提纲式的东西，用九十行的代码过了前两个样例，觉得有 $50\sim 60$ 分，收工了。

11/8

代码公开了，开始自测。

发现结果让我大跌眼镜。普及 100+100+5+35=240，提高 10+60+25+20=115，彻底炸了。很好奇提高 T1T2 到底错哪里了。不管了。

正解：普及

• T1 二进制模拟，特判奇数
• T2 桶排（强制在线很讨厌）
• T3 表达式树
• T4 dp $O(nm)$

提高

• T1 大模拟（我旁边那位码出来了，结果调试行没注释抱灵了）
• T2 跟我的思路差不多，可能有几个细节
• T3 拓扑
• T4 贪心

1= 无望了。

11/9

还能不能见到明天的太阳？

出期中考试成绩，满分460，我语数外集体翻车，还好有物理历史道法救我。

因数学太不符合水准被蔡帝叫去谈话，给我分析卷子：“这题解三角形找特殊角……这题图都对了还错……这几题都是看错……”说着说着我就100了。

一个礼拜总算结束了qaq