T1 三元上升子序列
题目要求$i< j< k$的$a_i< a_j< a_k$三元组数量,经典的套路是枚举中间数$j$。
枚举了$j$之后的事情就比较简单，直接用树状数组正向遍历维护$i< j$的$a_i< a_j$二元组数量，反向遍历$j< k$的$a_j< a_k$二元组数量，根据乘法原理再相乘即可。
$\scriptsize{理论情况下，三元组个数会达到N^3个，需要开\text{long long}}$
fw.clear(N - 1);
for (int i = 1; i <= n; ++i)
{
lw[i] = fw.qry(a[i] - 1);
fw.add(a[i], 1);
}
fw.clear(N - 1);
for (int i = n; i; --i)
{
rw[i] = n - i - fw.qry(a[i]);
fw.add(a[i], 1);
}
for (int i = 1; i <= n; ++i)
res += lw[i] * rw[i];T2(T1法二) Subsequence
长度为二的上升序列个数是易求的，那么如果要将长度扩展到3，容易想到可以 DP。
设$dp_{i,j}$表示以$a_i$结尾，长度为$j$的上升子序列个数，那么我们可以得到状态转移方程：
$$
dp_{i,j}\leftarrow \sum_{p\in \mathbb{N}^{\tiny{+}} \wedge p< i \wedge a_p<a_i}dp_{p,j-1}
$$
观察到式中的求和是前缀和，每次求值只涉及单点修改，考虑使用树状数组维护，即维护$k$个树状数组，第$j$个树状数组的第$i$个前缀和表示到$a_i$为止（并非以$a_i$结尾）的长度为$j$的上升子序列个数即可。
$\scriptsize{题面保证了答案不大于8\times10^{18}，运算过程中需要开\text{unsigned long long}}$
for (int i = 1; i <= n; ++i)
g[i][0] = 1;
for (int j = 1; j <= k; ++j)
{
fw[j].clear(n);
for (int i = 1; i <= n; ++i)
{
fw[j].add(a[i], g[i][j - 1]);
g[i][j] = fw[j].qry(a[i] - 1);
}
}
for (int i = 1; i <= n; ++i)
res += g[i][k];T3 Distinct Values Queries
题目问一个区间内不同元素的个数，我们可以考虑求出每一个区间内的数在该区间中最后一次出现的位置。
如果题目中的$b$不变，我们可以直接从b向左扫，记录一个数组$lst_x$表示$x$第一次出现的位置，$f_i$表示$[i=lst_{a_i}]$，如果$a_i$在此之前没有出现过（即$lst_{a_i} = 0$），那么$lst_{a_i}\leftarrow i,f_i\leftarrow \text{true}$。容易得知，答案为：$\sum^{b}_{i=a}f_i$
问题就会转化为：维护一个数组$f_i$，支持单点修改，区间求和。
直接用树状数组维护即可。
但是现在的$b$并不是一成不变的，显然最容易维护的情况是$b$逐次递增，这个时候只有$lst_{i\in (b_{i-1},b_{i}]}$是会改变的，那么我们只需要将询问离线下来，按$b$排序，每次询问把$(b_{i-1},b_{i}]$遍历一遍即可。
sort(qr + 1, qr + q + 1, [](const Q &x, const Q &y) { return x.b < y.b; } );
fw.clear(n)
for (int i = 1; i <= q; ++i)
{
if (qr[i].b > qr[i - 1].b)
{
for (int j = qr[i - 1].b + 1; j <= qr[i].b; ++j)
{
if (lst[a[j]])
fw.add(lst[a[j]], -1);
lst[a[j]] = j;
fw.add(j, 1);
}
}
res[qr[i].id] = fw.qry(qr[i].b) - fw.qry(qr[i].a - 1);
}T4 Petya and Array
记$a$的前缀和为$s$，那么题目要求的其实就是满足$s_r-s_{l-1}< t$的$\left( l,r \right)$个数。
移项，可以得到$s_{l-1}> s_r-t$，那我们要求的就是：
对于每一个$r$，比$s_r-t$更大的$s_{l-1}$的个数之和。
离散化后用树状数组维护即可。
fw.clear(cnt);
fw.add(lsh[0], 1);
for (int r = 1; r <= n; ++r)
{
res += r - fw.qry(lsh[s[r] - t]);
fw.add(lsh[s[r]], 1);
}T5 Substring of Sorted String
我们可以把询问的要求拆成两部分：
- $s[l,r]$递增
- $s[l,r]$中每个字符的出现次数等于$T$中那个字符的出现次数
第二个要求是非常好维护的，主要考虑第一个要求
对于第一个要求有一个 trick, 记$f_i\leftarrow [s_l\ge s_{l+1}]$，那么这个要求就可以转化为$\sum^{r-1}_{l}f_i=0$
每次做操作一时，只需要判断新的$c$和邻项的大小关系并更新$f_i$和出现次数即可。
那么问题就转化为了单点修改，区间查询，使用树状数组即可。
fenwick<N, ll> fw[27]; // fw[26]就是上文的f
void init()
{
for (int i = 0; i <= 26; ++i)
fw[i].clear(n);
for (int i = 1; i <= n; ++i)
fw[s[i] - 'a'].add(i,1);
for (int i = 1; i < n; ++i)
if (s[i] > s[i + 1])
fw[26].add(i,1);
}
void add(int x, int c)
{
s[x] = c;
fw[c - 'a'].add(x, 1);
if (x > 1 && s[x - 1] > s[x])
fw[26].add(x - 1, 1);
if (x < n && s[x] > s[x + 1])
fw[26].add(x, 1);
}
void del(int x)
{
fw[s[x] - 'a'].add(x, -1);
if (x > 1 && s[x - 1] > s[x])
fw[26].add(x - 1, -1);
if (x < n && s[x] > s[x + 1])
fw[26].add(x, -1);
}
if (op & 1)
{
del(x);
add(x, c)
}
else
{
bool f = 0;
for (int i = s[x] - 'a' + 1; i < s[y] - 'a'; ++i)
if(fw[i].qry(y) - fw[i].qry(x - 1) != fw[i].qry(n))
{
f = 1;
break;
}
cout << (f || fw[26].qry(x - 1) != fw[26].qry(y - 1) ? "No\n" : "Yes\n");
}T6 Box in Box
箱子可以旋转，考虑像田忌赛马一样将一个箱子的$h,w,d$排序再比较。
内部排序之后问题就转化为了一个“三维偏序”，按照常规套路是排序降一维, CDQ 降一维，数据结构降一维，但是这道题比较特殊，只判断是否存在而不需要计数，所以我们可以利用这一特殊性质用树状数组维护。
首先随便按一维排序（比如$h$），然后再将$w$离散化，这样既不影响对$w$比较，而且还可以直接将新的$w_i$作为$d$的下标。那么我们对于每一个枚举到的点$i$，只需要看$\min_{j\in[1,w_i)}d_j$是否小于$d_i$即可，这是一个前缀最小值，可以用树状数组维护。
for (int i = 1; i <= n; ++i)
{
if (b[i].h > b[i].w)
swap(b[i].h, b[i].w);
if (b[i].h > b[i].d)
swap(b[i].h, b[i].d);
if (b[i].w > b[i].d)
swap(b[i].w, b[i].d);
w[i] = b[i].w;
}
sort(b + 1, b + n + 1, [](const Q &x, const Q &y) { return x.h < y.h; } );
sort(w + 1, w + n + 1);
int wn = std::unique(w + 1, w + n + 1) - w - 1;
fw.clear(n);
for (int i = 1, j = 1; i <= n; i++)
{
for (; j <= n && b[j].h < b[i].h; ++j)
fw.add(std::lower_bound(w + 1, w + wn + 1, b[j].w) - w, b[j].d);
if (fw.qry(std::lower_bound(w + 1, w + wn + 1, b[i].w) - w - 1) < b[i].d)
{
cout << "Yes";
return 0;
}
}
cout << "No";