本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-04 14:30:23
CSP-S 要是打成这个 b 样，不仅没有 7 级，蓝钩都不一定能保住。
T1 不会，T2 写 80 分没调出来直接 0，T3T4 暴力.
不过记得最近一直是从 tg T2 开始出的，不知道现在是不是
Sol
T1
暂不会。
T2
暂不会。
T3
暂不会。
T4
暂不会。
__vector__ 的博客
博客
标签
暂无
2023.10.4 模拟赛
CF1860F 题解
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-04 16:30:21
点积是 $(a_i \cdot x + b_i \cdot y)$，变为 $y(a_i \cdot \frac{x}{y} + b_i$)，设 $K = \frac{x}{y}$然后把 $K$ 去掉进行排序。
然后按照 $K=0$ 排序得到一个初始数组。
然后计算出所有点对 $(c,d)$ 的 $k$ 值（$c$ 小于 $d$），使得当 $K = k$ 时，初始数组第 $c$ 个三元组的值开始超过初始数组第 $d$ 个。
然后枚举每个 $K = k_i$。
题解剩下的部分见这里
代码（我相信没人读懂，其中 unordered_map 使用的 pair<int,int> 哈希使用了知乎上的代码）：
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const double eps=1e-18;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
\/*
此程序 pair hash 模板转载信息：
作者：youngforest
链接：https:\/\/www.zhihu.com\/question\/30921173\/answer\/1248680260
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*\/
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
\/\/ auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
std::size_t seed = 0;
hash_val(seed, args...);
return seed;
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return hash_val(p.first, p.second);
}
};
const int maxn = 3005;
int t, n;
struct Bracket
{
int a, b;
int contri;
} bracket[maxn];
struct SegmentTree
{
int L[maxn << 2], R[maxn << 2];
int val[maxn << 2];
int premin[maxn << 2]; \/\/ 前缀最小值
int len(int pos)
{
return R[pos] - L[pos] + 1;
}
void pushup(int pos)
{
val[pos] = val[pos << 1] + val[pos << 1 | 1];
premin[pos] = min(premin[pos << 1], val[pos << 1] + premin[pos << 1 | 1]);
}
void chg(int pos, int x, int _val)
{
if (L[pos] > x || R[pos] < x)
return;
if (L[pos] == x && x == R[pos])
{
val[pos] += _val;
premin[pos] = val[pos]; \/\/ 注意不能直接加上 _val，因为 premin[pos] 可能此前没有定义（即 premin[pos]=1e9）
return;
}
int mid = L[pos] + R[pos] >> 1;
if (mid >= x)
chg(pos << 1, x, _val);
if (mid < x)
chg(pos << 1 | 1, x, _val);
pushup(pos);
}
void build(int pos, int l, int r)
{
L[pos] = l, R[pos] = r;
val[pos] = 0;
premin[pos] = 1e9;
if (l == r)
return;
int mid = l + r >> 1;
build(pos << 1, l, mid);
build(pos << 1 | 1, mid + 1, r);
}
} SGT;
struct SWAP
{
int l, r;
double k;
} sw[maxn*maxn];
int top;
int rk[maxn]; \/\/ 首次排序中第 i 个点，现在排名
struct UnionSet
{
int fa[maxn];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void un(int a,int b)
{
int r1=find(a),r2=find(b);
if(r1==r2)return;
fa[r1]=r2;
}
void init()
{
for(int i=1;i<=2*n;i++)fa[i]=i;
}
}us;
vector<short> rem[maxn],rem2[maxn];
vector<short> wait,val2,old1,old2;
unordered_map<pair<short,short>,vector<short>,pair_hash > cnt;\/\/ 每种节点的个数（主意不是交换）
bitset<maxn> vis;
vector<short> thrower,able;
queue<pii> q;
int main()
{
scanf("%d", &t);
FOR(_,1,t)
{
scanf("%d", &n);
FOR(i, 1, 2 * n)
{
scanf("%d%d", &bracket[i].a, &bracket[i].b);
char c = getchar();
while (c != '(' && c != ')')
c = getchar();
if (c == '(')
bracket[i].contri = 1;
else
bracket[i].contri = -1;
}
us.init();
\/\/ 现在按照 (a*x + b*y)\/y = a*(x\/y) + b 排序，设 k = x\/y
\/\/ 则按照 a*k + b 排序
sort(bracket + 1, bracket + 2 * n + 1, [&](Bracket &a, Bracket &b)
{
if(a.b!=b.b)return a.b<b.b;
else if(a.a!=b.a)return a.a<b.a;
else return a.contri>b.contri; }); \/\/ 将所有点对按照 k=0 排序，若权值相同，左括号优先。
SGT.build(1, 1, 2 * n);
\/\/ puts("========");
FOR(i, 1, 2 * n)
{
\/\/printf("%d %d %d\n",bracket[i].a,bracket[i].b,bracket[i].contri);
rk[i] = i;
\/\/ printf("ith.brack = %d\n",bracket[i].contri);
SGT.chg(1, i, bracket[i].contri);
FOR(j, i + 1, 2 * n)
{
if(bracket[i].a<=bracket[j].a)continue;
double k = double(bracket[j].b - bracket[i].b) \/ double(bracket[i].a - bracket[j].a);
if (k <= 1e-18)
continue; \/\/ 由于是 ka+b，在 b 落后的情况下想要反超只能靠 ka
sw[++top] = {i, j, k};
\/\/ printf("provide: %d & %d can swap when k = %.5lf\n",i,j,k);
}
}
bool ok=(SGT.premin[1]==0);
assert(SGT.val[1]==0);
\/\/ printf("premin = %d\n",SGT.premin[1]);
sort(sw + 1, sw + top + 1, [&](SWAP &a, SWAP &b){return a.k<b.k;});
\/\/ printf("number of swaps: %d\n",top);
FOR(i, 1, top)
{
\/\/ printf("i = %d k = %.5lf\n",i,sw[i].k);
int j=i;
wait.clear();
val2.clear();
old1.clear();
old2.clear();
cnt.clear();
vis.reset();
wait.emplace_back(sw[j].l);\/\/ wait: 待排序的节点列表
wait.emplace_back(sw[j].r);\/\/ 所有节点原来的 rank 列表
val2.emplace_back(rk[sw[j].l]);
val2.emplace_back(rk[sw[j].r]);
cnt[make_pair(bracket[sw[j].l].a,bracket[sw[j].l].b)].emplace_back(sw[j].l);
vis[sw[j].l]=1;
if(!vis[sw[j].r])cnt[make_pair(bracket[sw[j].r].a,bracket[sw[j].r].b)].emplace_back(sw[j].r);
vis[sw[j].r]=1;
us.un(sw[j].l,sw[j].r);
\/\/ printf("start from %d and k = %.5lf\n",i,sw[j].k);
\/\/ printf("swap = %d %d\n",sw[j].l,sw[j].r);
while(j<top&&abs(sw[j+1].k-sw[j].k)<=eps)
{
j++;
if(!vis[sw[j].l])cnt[make_pair(bracket[sw[j].l].a,bracket[sw[j].l].b)].emplace_back(sw[j].l);
vis[sw[j].l]=1;
if(!vis[sw[j].r])cnt[make_pair(bracket[sw[j].r].a,bracket[sw[j].r].b)].emplace_back(sw[j].r);
vis[sw[j].r]=1;
wait.emplace_back(sw[j].l);
wait.emplace_back(sw[j].r);
val2.emplace_back(rk[sw[j].l]);
val2.emplace_back(rk[sw[j].r]);
\/\/ printf("swap = %d %d\n",sw[j].l,sw[j].r);
us.un(sw[j].l,sw[j].r);
}
old1=wait;
old2=val2;
thrower.clear();
able.clear();
for(int i=0;i<wait.size();i++)
{
rem[us.find(wait[i])].emplace_back(wait[i]);
rem2[us.find(wait[i])].emplace_back(val2[i]);
thrower.emplace_back(wait[i]);
able.emplace_back(us.find(wait[i]));
}
sort(able.begin(),able.end());
int sz=unique(able.begin(),able.end())-able.begin()-1;
while(able.size()>sz+1)able.pop_back();
for(int v:able)
{
\/\/printf("")
sort(rem[v].begin(),rem[v].end());
int siz=unique(rem[v].begin(),rem[v].end())-rem[v].begin()-1;
while(rem[v].size()>siz+1)rem[v].pop_back();
sort(rem[v].begin(),rem[v].end(),[&](int a,int b){
return bracket[a].contri>bracket[b].contri;});
sort(rem2[v].begin(),rem2[v].end());
unique(rem2[v].begin(),rem2[v].end());
while(rem2[v].size()>siz+1)rem2[v].pop_back();
for(int k=0;k<rem[v].size();k++)
{
SGT.chg(1,rk[rem[v][k]],-bracket[rem[v][k]].contri);
rk[rem[v][k]]=rem2[v][k];
\/\/ printf("chg [%d] = %d\n",rem[v][k],rem2[v][k]);
SGT.chg(1,rk[rem[v][k]],bracket[rem[v][k]].contri);
}
}
for(int v:able)rem[v].clear(),rem2[v].clear();
for(int v:thrower)us.fa[v]=v;
\/\/ puts("????????");
\/\/ printf("up to %d\n",j);
\/* printf("fix up when %d to %d th: \n",i,j);
FOR(k,1,n*2)
{
printf("rk[%d] = %d\n",k,rk[k]);
}*\/
if(SGT.premin[1]==0)
{
ok=1;
break;
}
for(int k=0;k<old1.size();k++)
{
SGT.chg(1,rk[old1[k]],-bracket[old1[k]].contri);
rk[old1[k]]=old2[k];
SGT.chg(1,rk[old1[k]],bracket[old1[k]].contri);
}\/\/ clear
\/* printf("preclear: \n");
FOR(k,1,n*2)
{
printf("rk[%d] = %d\n",k,rk[k]);
}*\/
\/\/ printf("fix up: %d\n",SGT.premin[1]);
for(int k=i;k<=j;k++)
{
sort(cnt[make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b)].begin(),cnt[make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b)].end(),[&](int a,int b){
return bracket[a].contri>bracket[b].contri;});
sort(cnt[make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b)].begin(),cnt[make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b)].end(),[&](int a,int b){
return bracket[a].contri>bracket[b].contri;});
}
for(int k=i;k<=j;k++)
{
int l = sw[k].l, r = sw[k].r;
\/\/ printf("nwswp = %d %d\n",l,r);
\/*
if(cnt[make_pair(bracket[l].a,bracket[l].b)].size()>1)
{
l=cnt[make_pair(bracket[l].a,bracket[l].b)].back();
}
if(cnt[make_pair(bracket[r].a,bracket[r].b)].size()>1)
{
r=cnt[make_pair(bracket[r].a,bracket[r].b)].front();
}*\/
if (rk[l] > rk[r])
continue;
\/\/ printf("swap: %d %d\n",l,r);
SGT.chg(1,rk[l],-bracket[l].contri);
SGT.chg(1,rk[r],-bracket[r].contri);
swap(rk[l],rk[r]);
SGT.chg(1,rk[l],bracket[l].contri);
SGT.chg(1,rk[r],bracket[r].contri);
assert(SGT.val[1]==0);
}
vis.reset();
while(!q.empty())q.pop();
for(int k=i;k<=j;k++)
{
if(!vis[sw[k].l])
{
auto temp=make_pair(bracket[sw[k].l].a,bracket[sw[k].l].b);
q.push(temp);
vis[sw[k].l]=1;
}
if(!vis[sw[k].r])
{
auto temp=make_pair(bracket[sw[k].r].a,bracket[sw[k].r].b);
q.push(temp);
vis[sw[k].r]=1;
}
}
while(!q.empty())
{
pii u=q.front();
q.pop();
vector<int> rkrem;
for(int v:cnt[u])
{
rkrem.emplace_back(rk[v]);
}
sort(rkrem.begin(),rkrem.end());
for(int i=0;i<cnt[u].size();i++)
{
int v=cnt[u][i];
SGT.chg(1,rk[v],-bracket[v].contri);
rk[v]=rkrem[i];
SGT.chg(1,rk[v],bracket[v].contri);
}
}
if(SGT.premin[1]==0)
{
ok=1;
break;
}
i=j;
\/* printf("after %d th: \n",i);
FOR(j,1,n*2)
{
printf("rk[%d] = %d\n",j,rk[j]);
}*\/
}
if(ok)puts("YES");
else puts("NO");
top=0;
}
return 0;
}
Codeforces Round 902
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-08 22:28:44
感觉这场比赛和 1900+ performance 的差距主要在罚时上，想完成 flag（上紫），以后的 CF 得减少大意导致的错误。
D2A
所有人得分加起来是 $0$。
D2B/D1A
优先让分享价格低的人分享。
D2C
显然不同数数量不会超过 $3$。
并且由于 $i=1$ 时，$a_i = 0$，所以从后向前最后一定会变成 $0$，然后一直是 $0$。
- 若 $k = 1$，则全填 $0$，答案是 $1$。
- 若 $k = 2$，第一种情况，在第 $n$ 个位置被 mod 成 $0$，然后向前一直是 $0$，由于最后一位要填 $n$ 的倍数，有 $\lfloor \frac{m}{n} \rfloor$ 种可能；第二种情况，从后向前保持一段时间不变，然后被 mod 成 $0$，然后一直是 $0$，由于最后一位要填 $[0,\min(m,n-1)]$，有 $\min(m,n-1)$ 种可能。
答案是 $\lfloor \frac{m}{n} \rfloor + \min(m,n-1)$ 种可能。 - 若 $k = 3$，则答案是总方案数减去 $k=1,2$ 的方案数。
D1B
考虑每一个点作为黑点，算出它及它连带着加进来的数（它的倍数）的 max。
设有 $cnt_i$ 个点使得它及它连带着加进来的数（它的倍数）的 max 是 $i$。
然后枚举全局 max，算出这个全局 max 在多少种情况中出现，这个情况数是：$2^{\sum\limits_{i=0}^{max-1} cnt_i} \cdot (2^{cnt_{max}} - 1 )$
D1C
不会。
D1D
不会。
D1E
不会。
D1F
不会。
D1G
不会。
F
CSP-S2020
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-10 21:54:42
曾经做过 T3，T4，然而做法忘干净了。。。。。
vp 结果
95 + 80 + 55 + 0 = 230。
虽然稳稳 7 级，但有这样几个问题：
- T2 没注意到答案爆 ull，挂 5 分
- T1 赛时秒出了正解，但是由于读错题卡了较长时间，最后差点写完，只有 80 分。
- T3 只会暴力的 55 分。
- T4 没时间写了，如果写了至少 20 分。
综上，主要原因是手速不够快，还得多打 CF/Atc。
这场比赛在自己目前水平内的提升空间还有 5 + 20 + 0 + 20 = 45 分，即总分达到 275。
T2
每一位都有相应要买的饲料。
每一位拆开算贡献。
T1
听（HaoBa)说当年很多大佬挂在这道题。
感觉本题思维很简单，但是在 4 个小时内，保证其他题正常得分的情况下确实不容易写完。
首先计算出 1582.10.4 及以前的日期对应关系，并记录。
再计算出 1582.10.15 到之后第一个闰年的年末的对应关系。（这么做的原因是为了方便计算闰年数量）
以上可以简单的暴力计算。
询问的儒略日如果已经算出来了，直接回答。
否则，依次二分年份，月，再算出日，细节很少，不写了。
T3
过会写。
T4
https://www.luogu.com.cn/blog/liumonong/p7078-csp-s2020-tan-chi-she-ti-xie
Codeforces Round 903 (Div. 3)
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-13 01:15:23
打星参赛。
赛时倒开，过了 BCDEG。
D
找出所有质因数，每种质因数都必须出现 $n$ 的倍数次。
E
$dp_i$ 代表 $i$ 开头的答案。
F
https://codeforces.com/contest/1881/submission/227980730 维护 f 表示子树内答案，g 表示子树外答案，然后第一次 dfs 求出 f，第二次 dfs 求出 g（算 g 需要先算出 f）
G
分块板子题。
当然应该有别的更优秀做法。
CF1881F
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-15 15:22:31
听（我妈）说有人想跟我探讨这题做法，就写这题较为详细题解了。
先钦定 $1$ 是根节点。
可以先将每个点的答案分别计算出来最后取最小值。
为了方便计算，自然能想到分子树内和子树外分别计算，具体地，设 $f_i$ 表示 $i$ 为根的子树内离 $i$ 最远的关键点的距离，设 $g_i$ 表示 $i$ 为根的子树以外离 $i$ 最远的关键点的距离。
$f_i$ 的计算是很简单的树形 dp。
考虑 $g_i$，有两种转移。设 ${fa}_i$ 表示 $i$ 的父节点，${bro}_i$ 表示 $i$ 的兄弟节点。
- 从父节点继承，即 $g_i = g_{fa_i} + 1$。
- 从兄弟节点继承，即 $g_i = g_{bro_i} + 2$。
完结。
https://codeforces.com/contest/1881/submission/227980730
HaoBa noip 模拟赛
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-08 09:58:04
T1 放 USACO Platinum T3 ？？？？？？？？？
T2 记得是 ARC 原题，而且我打过。
T3&T4 不知道原题链接。
Sol
暂时一道不会，先开个坑。
ChatGPT 写代码注释
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-08 20:54:12
题目链接：http://usaco.org/index.php?page=viewproblem2&cpid=1142&lang=zh
我没有给 ChatGPT 任何提示。
可以看到 ChatGPT 基本读懂了正解代码。
输入：
请解释这段代码，并为其添加注释：
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 155;
int n;
char s[maxn][maxn];
ll dp[maxn][2][2][maxn][maxn]; \/\/ 0 代表增长或不变，1 代表减少或不变状态
ll pre[maxn][2][2][maxn][maxn];
ll w(int id, int cla1, int cla2, int dw, int up, int l, int r)
{
return pre[id][cla1][cla2][up][r] - pre[id][cla1][cla2][dw - 1][r] - pre[id][cla1][cla2][up][l - 1] + pre[id][cla1][cla2][dw - 1][l - 1];
}
ll ans;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%s", s[i] + 1);
}
for (int i = 1; i <= n; i++)
{
for (int llim = 1; llim <= n; llim++)
{
if (s[i][llim] == '.')
continue;
int rlim = llim;
while (s[i][rlim + 1] == 'G')
rlim++;
for (int l = llim; l <= rlim; l++)
{
for (int r = l; r <= rlim; r++)
{
\/\/ printf("dp (%d,%d,%d,%d) = %lld\n", 0, 0, l, r, w(i - 1, 0, 0, l, r, l, r) + 1);
dp[i][0][0][l][r] += w(i - 1, 0, 0, l, r, l, r) + 1; \/\/ 加一是因为，可以从 ith line 开始
dp[i][1][0][l][r] += w(i - 1, 0, 0, 1, l - 1, l, r) + w(i - 1, 1, 0, 1, l, l, r);
dp[i][0][1][l][r] += w(i - 1, 0, 0, l, r, r + 1, n) + w(i - 1, 0, 1, l, r, r, n);
dp[i][1][1][l][r] += w(i - 1, 0, 0, 1, l - 1, r + 1, n) + w(i - 1, 1, 0, 1, l, r + 1, n) + w(i - 1, 0, 1, 1, l - 1, r, n) + w(i - 1, 1, 1, 1, l, r, n);
dp[i][0][0][l][r] %= mod;
dp[i][1][0][l][r] %= mod;
dp[i][0][1][l][r] %= mod;
dp[i][1][1][l][r] %= mod;
}
}
llim = rlim;
}
for (int cla = 0; cla <= 1; cla++)
{
for (int cla2 = 0; cla2 <= 1; cla2++)
{
for (int p = 1; p <= n; p++)
{
for (int q = 1; q <= n; q++)
{
ans += dp[i][cla][cla2][p][q];
ans %= mod;
}
}
}
}
for (int cla = 0; cla <= 1; cla++)
{
for (int cla2 = 0; cla2 <= 1; cla2++)
{
for (int p = 1; p <= n; p++)
{
for (int q = 1; q <= n; q++)
{
pre[i][cla][cla2][p][q] += pre[i][cla][cla2][p - 1][q] + pre[i][cla][cla2][p][q - 1] - pre[i][cla][cla2][p - 1][q - 1] + dp[i][cla][cla2][p][q];
pre[i][cla][cla2][p][q] %= mod;
\/\/ printf("(%d %d %d %d) val = %lld\n", cla, cla2, p, q, pre[i][cla][cla2][p][q]);
}
}
}
}
}
printf("%lld", (ans%mod+mod)%mod);
return 0;
}
ChatGPT 回答：
这段代码的功能是计算一个矩阵中满足一定条件的矩形子区间的数量，并对结果取模。
代码中使用的关键数据结构和变量：
s是一个字符数组，表示输入的矩阵。每个字符代表一个矩阵元素，'.' 表示空白，'G' 表示有填充。dp是一个五维数组，表示状态数组，用于存储子问题的解。dp[i][c1][c2][l][r]表示以第i行，左边界为l，右边界为r的子矩阵，其中c1和c2表示左侧和右侧的填充状态。pre是一个五维数组，表示前缀和数组，用于在计算过程中快速求解和。ans是一个整型变量，用于存储最终的结果。
代码的主要逻辑如下：
- 从输入中读取矩阵的大小
n，然后读取整个矩阵的内容到s数组中。 - 使用双重循环遍历矩阵的每一行和每一个连续的填充块（以连续的 'G' 字符为界）。
- 在每个填充块中的循环中，使用双重循环遍历所有可能的左边界
l和右边界r。 - 根据题目给出的状态转移方程，更新
dp数组中的值。 - 对于每一行，计算所有
dp数组中元素的和，并累加到ans变量中。 - 计算当前行的前缀和并存储到
pre数组中，用于快速计算下一行的状态转移。 - 最后，将计算得到的
ans变量的值取模并输出。
注释已添加在代码中，以更清晰地解释每个部分的作用和计算过程。
CF575A 大概思路
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-11 22:56:18
思路好想，被细节创飞了。
按照套路，先构造矩阵，设 $[f_i,f_{i+1}] \cdot delta_i = [f_{i+1},f_{i+2}]$。
则答案就能用 $[0,1]$ 和 delta 的乘积表示出来了。
然后发现这个 delta 有循环节，每个循环节长度为 $n$。
于是划分成 $\lceil{\frac{k}{n}}\rceil$ 段，把不考虑特殊点情况下的循环节的答案算出来。
对于不存在循环节的段，矩阵快速幂维护。
对于存在循环节的段，这样的段可以分别单独维护。
考虑对 s 的修改会对 delta 造成的影响，可以发现只会影响两个 delta。
提前把对所有 delta 的影响算出来，然后依次枚举每个段落进行修改，查询答案。
可以用线段树维护一个段的 delta 乘积，并支持修改。
当结束一个段落时，线段树查询 delta 乘积，再将线段树改回原样准备下一个段落。
细节很多，列举几个：
- 两个相邻的 si 被修改，会导致同一个 delta 被修改，如果不注意，这两个修改操作结果会互相覆盖。
- 最后一段，如果用 $k \mod n$ 计算长度，$k$ 是 $n$ 的倍数就会寄掉。
百度之星
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-13 13:44:28
我知道骂人会掉粉，但还是要骂。
花 80 元买到了初赛参赛资格。
现在看到要求双机位监考（我妈之前也没看到，说是买了之后才能看规则）。
我 tm 在机房，只有一台电脑。
还我 80 元！
共 320 篇博客
鲁ICP备2025150228号