E - Work or Rest
题意
一周有 \(n\) 天，给出一个长度为 \(n\) 的数组 \(A\)。你可以决定一周中的休息日与工作日的分布，请问如何选择能够使总贡献最大。
如何计算贡献：对于休息日，贡献为0；对于工作日，贡献为 \(A_{min(x, y)}\)， \(x\) 是上一个休息日距今天多少天， \(y\) 是下一个休息日距今天多少天（若是在本周的末尾，后面不再有休息日的话，会找到下一周的第一个休息日）。
思路
首先一眼可以知道是DP题，用 \(f[i]\) 表示前 \(i\) 天，且在第 \(i\) 天休息的最大价值。我首先想的是直接做，但是发现当前状态依赖于后面的状态，所以我们应该逆向思考一下。我们考虑通过确定休息日的位置来计算工作日的贡献。那状态状态方程就可以写出来了：
\[dp_i=max^{i}_{j=0} \{dp_j + calc(j, i)\} \] \(clac(l,r)\) 表示 \(l\) 和 \(r\) 两个端点为休息日，中间皆为休息日的情况下的贡献。通过前缀和可以 \(O1\) 计算出来。又考虑到第 \(n\) 天可能会和下一周结合产生贡献，也就是环形问题。我们应该把休假的日子设成第 \(0\) 天，这样任何状态都可以直接从 \(dp[0]\) 转移过来。
代码
int n;
ll f[N]; //当前为i，上一个holiday为j天前
void solve()
{
cin >> n;
vector<ll> a(n + 1, 0), sum(n + 1, 0);
for(int i = 1; i <= n; i ++)
cin >> a[i], a[i] += a[i - 1];
for(int i = 1; i <= n; i ++)
sum[i] = a[i / 2] + a[(i - 1) / 2];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++)
f[i] = max(f[i], f[i - j] + sum[j]);
ll res = 0;
for(int i = 1; i <= n; i ++)
res = max(res, f[i]);
cout << res << '\n';
}
F - Substring of Sorted String
题意
有一个长度为 \(10^5\) 的字符串。现在有 \(10^5\) 次更新和查询，更新：单点修改字符串中的一个字符；查询：截取字符串的区间 \([l, r]\) ，判断截取的串是否是升序排序后的原串的子串。
思路
如何快速判断呢？我们转化一下，就是在询问截取的串是否升序且掐头去尾后字符数量和原串中是相等的。我们需要维护每个字母数量的区间和且维护区间是否升序。还有掐头去尾可以用线段树维护一下区间最大最小值（其实也不用维护，如果升序的话 \(l\) 和 \(r\) 就是最小字母和最大字母，不升序的话也自然不合法），因为截取串中的最大字符和最小字符是可以不用跟原串相等的。
代码
const int N = 100005;
int n, m;
char a[N];
class BIT {
public:
ll c[N] = {0};
void add(int x, int val) {
for (int i = x; i < N; i += i & -i) {
c[i] += val;
}
}
ll ask(int x) {
ll ans = 0;
for (int i = x; i; i -= i & -i) {
ans += c[i];
}
return ans;
}
} T1, cnt[26]; //维护是否递增，维护各个字母的数量区间和
struct Seg_tree {
struct node {
int l, r;
int mx, mn;
} seg[N << 2];
void pushup(int k)
{
seg[k].mx = max(seg[k << 1].mx, seg[k << 1 | 1].mx);
seg[k].mn = min(seg[k << 1].mn, seg[k << 1 | 1].mn);
}
void build(int k, int l, int r)
{
seg[k].l = l, seg[k].r = r;
if(l == r) {
seg[k].mx = seg[k].mn = a[l] - 'a';
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
pushup(k);
}
void modify(int k, int pos, int v)
{
int l = seg[k].l, r = seg[k].r;
if(l == r) {
seg[k].mx = seg[k].mn = v;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
modify(k << 1, pos, v);
else
modify(k << 1 | 1, pos, v);
pushup(k);
}
int query_mx(int k, int ql, int qr)
{
int l = seg[k].l, r = seg[k].r;
if(ql <= l && r <= qr)
return seg[k].mx;
int mid = (l + r) >> 1;
int res = -inf;
if(ql <= mid)
res = max(res, query_mx(k << 1, ql, qr));
if(mid < qr)
res = max(res, query_mx(k << 1 | 1, ql, qr));
return res;
}
int query_mn(int k, int ql, int qr)
{
int l = seg[k].l, r = seg[k].r;
if(ql <= l && r <= qr)
return seg[k].mn;
int mid = (l + r) >> 1;
int res = inf;
if(ql <= mid)
res = min(res, query_mn(k << 1, ql, qr));
if(mid < qr)
res = min(res, query_mn(k << 1 | 1, ql, qr));
return res;
}
} T2; //维护区间最大值最小值
int main()
{
scanf("%d%s", &n, a + 1);
T2.build(1, 1, n);
for(int i = 1; i <= n; i ++)
cnt[a[i] - 'a'].add(i, 1);
for(int i = 1; i < n; i ++)
{
if(a[i] > a[i + 1]) //若非递增
T1.add(i, 1);
}
scanf("%d", &m);
while(m --)
{
int opt;
scanf("%d", &opt);
if(opt == 1)
{
int x;
char ch[5];
scanf("%d%s", &x, ch);
if(x - 1 >= 1 && a[x - 1] > a[x])
T1.add(x - 1, -1);
if(x + 1 <= n && a[x] > a[x + 1])
T1.add(x, -1);
cnt[a[x] - 'a'].add(x, -1);
a[x] = *ch;
T2.modify(1, x, a[x] - 'a');
cnt[a[x] - 'a'].add(x, 1);
if(x - 1 >= 1 && a[x - 1] > a[x])
T1.add(x - 1, 1);
if(x + 1 <= n && a[x] > a[x + 1])
T1.add(x, 1);
}
else
{
int l, r;
scanf("%d%d", &l, &r);
int ok = 1;
if(T1.ask(r - 1) - T1.ask(l - 1) > 0) //[l, r - 1]是否递增
ok = 0;
int mx_ch = T2.query_mx(1, l, r);
int mn_ch = T2.query_mn(1, l, r);
for(int i = mn_ch + 1; i <= mx_ch - 1; i ++)
if(cnt[i].ask(r) - cnt[i].ask(l - 1) != cnt[i].ask(n))
ok = 0;
if(ok)
cout << "Yes\n";
else
cout << "No\n";
}
}
}