吐槽自己
正如标题之中所写的，我只做出来 4 道题（哭），当时还差点卡 D 了，调得挺崩溃的，也不知道是不是路子不够正。至于 EF 题，我倒是也看了，但是都没有一个具体的思路，以后看看 dalao 的题解，再补充一下吧。
这里是题目
A – Traffic Light
输入一个字符$c$，对于$c$分别为字母 B、Y、R 时，分别输出字母 Y、R、B。
思路如题。
B – Standing Outliers
有$N$个人，第$i$号人位于坐标$X_i$处，如果一个人与其他所有人的距离最小值不小于$D$，就称其为“特殊人”。输出“特殊人”的个数以及每个“特殊人”的编号（编号升序输出）。$N\leq 100$。
对于每个人都找一下就好了。时间复杂度$O(N^2)$。
C – Range Search Query
有两个字符串$s,\, t$，进行$Q$次询问，每次询问给出$L,\, R$，判断$s$从第$L$位到第$R$位的子串中是否包含$t$作为子串。$\lvert s\rvert \leq 4\times 10^5,\, \lvert t\rvert \leq 10,\, Q\leq 2\times 10^5$。
显然$O(Q\lvert s\vert \lvert t\rvert)$是不行的，考虑前缀和。设$sum_i$表示$s$从头到第$i$位出现的$t$子串个数，由于$\lvert t\rvert$很小，所以这里一个$O(\lvert s\rvert \lvert t\rvert)$可以接受。
那么对于每次询问，只需要看看$[L,\, R]$内出现的$t$子串个数是否大于 0 即可。现在，就要考虑如何用$sum_i$表示出$[L,\, R]$内出现的$t$子串个数，直接$sum_R-sum_{L-1}$吗？似乎不太对啊。因为这里关于$sum$的含义，更准确地说应该是：$s$中出现的结尾位不大于$i$的$t$子串个数。回想一下刚才的式子，可能有刚好结尾位为$L$的$t$子串也被统计了，但实际上那个$t$子串并不是完全位于$[L,\, R]$内。
这样一来，就要多考虑一个点：$t$子串的开头位必须不小于$L$。对于开头位最靠前（即为$L$）的$t$子串，其结尾位应该为$L+\lvert t\rvert -1$。那么，$[L,\, R]$内出现的$t$子串个数用$sum_i$表示出来就是：$$sum_R-sum_{(L+\lvert t\rvert -1)-1}.$$
时间复杂度$O(\lvert s\rvert \lvert t\rvert +Q)$。
int main(){
cin >> q >> s >> t;
int ls = s.size(), lt = t.size();
for(int i = 0; i < ls; i++){
if(i + 1 < lt) continue; // 长度还不到|t|
bool f = 0;
for(int j = 0; j < lt; j++)
if(t[j] != s[i - lt + 1 + j]){ f = 1; break; }
sum[i] = sum[i - 1] + (!f);
}
while(q--){
int l, r;
cin >> l >> r; l--, r--; // 前面字符串首位从0开始，这里询问默认首位为1，所以进行-1偏移
if(r - l + 1 < lt) cout << "No\n"; // 区间总长还不到|t|
else{
int c = sum[r] - sum[l + lt - 2];
if(c > 0) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}D – Masking Tape
有$N$个格子排成一行，一开始所有格子的颜色都为 a（颜色用小写字母表示），接着进行$Q$次操作，最后输出每个格子的颜色。操作类型有两种：操作 1 输入一个整数$X$，若第$X$号格子上有瓷砖覆盖就拿掉那块瓷砖，否则就在上面覆盖一块瓷砖；操作 2 输入一个字符$C$，将所有没被瓷砖覆盖的格子染成颜色$C$。$N,\, Q\leq 3\times 10^5$。
考虑倒序操作。先顺序跑一遍，跑出最终所有格子的瓷砖覆盖状态，看看最终没被瓷砖覆盖的格子能否被染上色，如果能染就染，再倒着跑就会发现每次操作 1 最多有一个格子的瓷砖覆盖状态发生改变，如果是瓷砖被揭，就更新一下这个格子的颜色（前提是这个格子颜色还是 a），关于更新为何种颜色，向前找操作 2 即可（当然太靠前的操作 2 也不行，有可能那时该格子的瓷砖覆盖状态又改变了一次，相当于又被覆盖了，那就不能染了）。时间复杂度$O(Q\log Q)$，详见代码注释，可能读起来更好懂些。
int main(){
cin >> n >> q;
for(int i = 1; i <= q; i++){
cin >> op[i];
if(op[i] == 1){
cin >> x[i];
t[x[i]].push_back(i); // t[x]里面存放的是格子x的瓷砖覆盖状态发生改变的操作序号
a[x[i]] ^= 1; // a[i]为0表示没被覆盖，为1表示被覆盖；这里就是在进行01状态转换
}
else{
cin >> c[i];
p[++tot] = i; // p中存放了所有操作2的操作序号
}
}
bool f = 0;
for(int i = q; i >= 1; i--){ // 倒着跑
if(op[i] == 2 && !f){ // 最早碰到的操作2，把目前还没被覆盖的格子染一染
f = 1;
for(int j = 1; j <= n; j++)
if(!a[j]) ans[j] = c[i];
continue;
}
if(op[i] == 1){
a[x[i]] ^= 1;
if(ans[x[i]]) continue; // 已经有不为a的颜色就跳过
if(!a[x[i]]){ // 变完后可以染色，就向前找操作2
int ps = upper_bound(p + 1, p + tot + 1, i) - p - 1; // 二分查找i之前最靠后的操作2
if(!c[p[ps]]) continue; // 前面已经没有操作2了；注意ps只能作为p的下标，只有p[ps]才能作为c的下标
int l = 0, r = t[x[i]].size() - 1; // 二分查找该操作序号i在t[x[i]]中的位置
while(l < r){
int mid = (l + r) >> 1;
if(t[x[i]][mid] < i) l = mid + 1;
else r = mid;
}
if(l == 0) ans[x[i]] = c[p[ps]]; // 前面没有关于该格子的操作1了，安心染色即可
else if(p[ps] > t[x[i]][l - 1]) ans[x[i]] = c[p[ps]]; // 操作2不能太靠前了，如果该格子的瓷砖覆盖状态又改变了就不能染了
}
}
}
for(int i = 1; i <= n; i++){
if(ans[i]) cout << ans[i];
else cout << 'a';
}
cout << '\n';
return 0;
}E – Wheel Distance
（补。完全想复杂了。）
给出一个有$N+1$个点的无向图，对于每个$1\leq i\leq N$，点$i$与点$(i\mod N)+1$之间有一条长$A_i$的边，点$i$与点$N+1$之间有一条长$B_i$的边。进行$Q$次询问，每次询问给出两个点$S,\, T$，询问这两点间的最短距离。$N,\, Q\leq 2\times 10^5,\, 1\leq S<T\leq N+1$。
很显然可以将这个图想成是：一个环 + 一个中心点。从$S$到$T$，可以选择只在环上走，也可以选择途中经过中心点走。环上两点间的距离好求，前缀和即可；途经中心点走分为两部分，先从$S$到$N+1$，再从$N+1$到$T$，跑一个以$N+1$为起点的单源最短路即可。时间复杂度$O(N\log N+Q)$。
signed main(){
init();
dijkstra(n + 1); // 跑单源最短路
while(q--){
int s, t; cin >> s >> t;
if(t == n + 1){ // 此时不能只在环上走
cout << dis[s] << '\n';
continue;
}
int d = sum[t - 1] - sum[s - 1]; // 环上走法其一，另一种见下
int ans = min({d, sum[n] - d, dis[s] + dis[t]});
cout << ans << '\n';
}
return 0;
}F – Count Cells in a Window
（补。完全没想到怎么做，但实际上做法非常巧妙且经典。）
有一个$N$行$M$列的网格，第$i$行的第$L_i$列到第$R_i$列为黑色，其余为白色。进行$Q$次询问，每次询问给出$A,\, B,\, C,\, D$，求第$A$行到第$B$行、第$C$列到第$D$列形成的矩形中的黑色格子个数。$N,\, M,\, Q\leq 2\times 10^5$。
容易想到二维前缀和，可是$N,\, M$太大，根本无法开出一个大小为$NM$的数组。不过我们还是可以根据二位前缀和写出来一个式子，设$f(x,\, y)$表示以$(1,\, 1)$为左上角、$(x,\, y)$为右下角的矩形中的黑色格子个数，则有：$$ans=f(B,\, D)-f(A-1,\, D)-f(B,\, C-1)+f(A-1,\, C-1).$$
既然无法保存$f(x,\, y)$，那么就直接考虑怎么把它求出来。求$f(x,\, y)$需要知道第$1$行到第$x$行之间每一行的贡献。对于第$i$行，其贡献情况有三种，简单来说就是完全不贡献、不完全贡献和完全贡献这三种。具体来说是这样的：若$y<L_i$，则贡献$0$；若$L_i\leq y<R_i$，则贡献$y-L_i+1$；若$y\geq R_i$，则贡献$R_i-L_i+1$。
如此一来，则有：$$f(x,\, y)=\sum_{i\leq x,\, L_i\leq y<R_i} (y-L_i+1)+\sum_{i\leq x,\, y\geq R_i} (R_i-L_i+1).$$
进而可以写成：$$f(x,\, y)=(y+1)\cdot \sum_{i\leq x,\, L_i\leq y<R_i} 1-\sum_{i\leq x,\, L_i\leq y<R_i} L_i+\sum_{i\leq x,\, y\geq R_i} (R_i-L_i+1).$$
整个式子明显分成了三部分，考虑用树状数组维护每一项，分别是不完全贡献行数$cnt$、不完全贡献行的$L_i$之和$sum$以及完全贡献行的$R_i-L_i+1$之和$csum$。每个状态按照$y$从小到大进行更新：对于所有满足$L_i=y$的行$i$，$cnt$加上$1$，$sum$加上$L_i$；对于所有满足$R_i=y$的行$i$，$cnt$减去$1$，$sum$减去$L_i$，$csum$加上$R_i-L_i+1$。
最后考虑查询该怎么处理，先将每个查询操作按照上文提到的关于$ans$的式子的右侧拆成四项，分别是$f(B,\, D)$、$-f(A-1,\, D)$、$-f(B,\, C-1)$和$f(A-1,\, C-1)$，然后再按列存下，这样就可以在更新树状数组时顺便求出一个个查询项。
最后发现是经典的「离线 + 树状数组」思想。时间复杂度$O((N+Q)\log N)$。
signed main(){
cin >> n >> m >> q;
for(int i = 1; i <= n; i++){
cin >> l[i] >> r[i];
el[l[i]].push_back(i); // 存l[i]更新项
er[r[i]].push_back(i); // 存r[i]更新项
}
for(int i = 1; i <= q; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
qry[d].push_back({b, 1, i}); // 按列存：行x，符号sign，操作下标h
qry[d].push_back({a - 1, -1, i});
qry[c - 1].push_back({b, -1, i});
qry[c - 1].push_back({a - 1, 1, i});
}
for(int j = 1; j <= m; j++){
for(int i : el[j]){ // 更新l[i]=y的
update(cnt, i, 1);
update(sum, i, l[i]);
}
for(int i : er[j]){ // 更新r[i]=y的
update(cnt, i, -1);
update(sum, i, -l[i]);
update(csum, i, r[i] - l[i] + 1);
}
for(auto i : qry[j]){ // 求出一个个查询项
int qcnt = query(cnt, i.x);
int qsum = query(sum, i.x);
int qcsum = query(csum, i.x);
int f = (j + 1) * qcnt - qsum + qcsum; // 求f(x, y)的式子
ans[i.h] += (f * i.sign); // 别忘乘符号
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << '\n';
}
return 0;
}