T1 养花

$f[i]$表示艳丽值小于等于 i 的最大值是多少，那么我们再令 $g[i]$表示这段区间被 i 膜的最大值，那么我们有 $g[i]=max(f[i\times j-1] \% i)(1 \leq j \&\& i \times j \leq 1e5)$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
int n, m, sq, up, max[330][N + 5], f[N + 5], bl, br, a[N];
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, n)
scanf("%d", &a[i]);
sq = (int) sqrt(n);
up = sq + 3;
fo (i, 1, up)
{
int l = (i - 1) * sq + 1, r = i * sq;
if (l > n) break;
memset(f, 0, sizeof f);
fo (i, l, r)
f[a[i]] = a[i];
fo (i, 1, N)//一定要弄到值域大小吧不然会 gg
f[i] = std::max(f[i], f[i - 1]);
fo (j, 1, N)
{
for (int k = j - 1; k <= N; k += j)//枚举 j 的倍数-1！
max[i][j] = std::max(max[i][j], f[k] - k - 1 + j);//第 i 个块膜 j 的最大值
}
}
fo (i, 1, m)
{
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
bl = (l - 1) / sq + 1;//l 所在块
br = (r - 1) / sq + 1;//r 所在块
int ans = 0;
if (bl == br || bl + 1 == br)
{
fo (i, l, r)
ans = std::max(ans, a[i] % k);
}
else
{
++bl; --br;
fo (i, bl, br)
ans = std::max(max[i][k], ans);
if (ans == k - 1)
{
printf("%d\n", ans);
continue;
}
bl = (bl - 1) * sq;//l 所在块的结尾
br = br * sq + 1;//r 所在块的开头
fo (i, l, bl)
ans = std::max(ans, a[i] % k);
fo (i, br, r)
ans = std::max(ans, a[i] % k);
}
printf("%d\n", ans);
}
return 0;
}


T2: 折射

$$f[i][0] += f[j][1] (y_j \lt y_i)$$
$$f [ j] [ 1 ] += f [ i ] [ 0 ] (y_j \gt y_i)$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 60005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, m, dp[N][2], ans;
struct node{
int x, y;
friend bool operator < (node a, node b)
{
return a.x < b.x;
}
}p[N];
int main ()
{
scanf("%d", &n);
fo (i, 1, n)
scanf("%d %d", &p[i].x, &p[i].y);
std::sort(p + 1, p + n + 1);
fo (i, 1, n)
{
dp[i][0] = dp[i][1] = 1;
fd (j, i - 1, 1)
if (p[i].y > p[j].y)
{
dp[i][0] = (dp[i][0] + dp[j][1]) % mod;
}
else
{
dp[j][1] = (dp[i][0] + dp[j][1]) % mod;
}
}
fo (i, 1, n) ans = (ans + (dp[i][0] + dp[i][1] - 1) % mod) % mod;
printf("%d\n", ans);
return 0;
}