Pre
神神奇奇美美妙妙。
下面的板块是直接从洛谷上面的我的题解里面抄的。
Solution
先学一下杨氏矩阵再来做这一题会好一些（否则A不了）。
由(Dilworth)定理，好像是这个名字，可以在对询问排序后求解当前状态下的非升子序列的个数，用杨氏矩阵的每一行来维护，这样是查询前(k)行的元素个数和，所以树状数组统计。
但是空间会开不下，注意到求非升子序列的个数与求升子序列的长度相等，求非升子序列的长度和求升子序列的个数相等，就可以有两种目的的矩阵形状相反(可以想成矩阵是行的个数是子序列个数，最下列的长度是异于上一个子序列的要求的最长子序列)。
也就是两个矩阵的形状互为转置（我没学过线性代数，表述若有误还请原谅）。
那么假设(sz=sqrt n)那么对于行数大于(sz)的就可以在转置矩阵当中求，可以证明，在横坐标(xin [1, sz])与纵坐标(yin [1, sz])当中的所有位置不可能既全部有点，又在这个范围外有点，因为假设全部有点(范围内和转置矩阵(xin [sz + 1, n],yin [sz + 1, n])的区域)，数量超过(n)。
那么转置的矩阵在横坐标(xin [sz+1,n])的范围内，一定不存纵坐标(yin [sz+1, n])的点。
所以可以维护两个(sz imes n)的矩阵求解。
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 50000 + 5, M = 233;
inline int lowbit (int u) {return u & (-u);}
int tree[N];
inline void add (int u, int v) {while (u <= N - 5) tree[u] += v, u += lowbit (u);}
inline int query (int u) {int res = 0; while (u) res += tree[u], u -= lowbit (u); return res;}
struct Q {int m, k, id, ans;}qq[N << 2];
int sz, n, b[N], q;
struct Matrix {
int info[M][N], sign;
inline void insert (int u, int v, int p) {
if (u > sz) {return ;}
int l = 1, r = min (v, info[u][0] + 1), mid;
while (l < r) {
mid = (l + r) / 2;
if (sign ^ (info[u][mid] < p)) {r = mid;}
else {l = mid + 1;}
}
swap (info[u][l], p);
info[u][0] = max (info[u][0], l);
if (p) {insert (u + 1, l, p);}
else {
if (sign) {if (l > sz)add (l, 1);}
else {add (u, 1);}
}
}
}m1, m2;
int main () {
m1.sign = 0, m2.sign = 1;
scanf ("%d%d", &n, &q);sz = sqrt (n);
for (int i = 1; i <= n; ++i) {scanf ("%d", &b[i]);}
for (int i = 1; i <= q; ++i) {scanf ("%d%d", &qq[i].m, &qq[i].k);qq[i].id = i;}
sort (qq + 1, qq + q + 1, [](Q a, Q b){return a.m < b.m;});
int pre = 0;
for (int i = 1; i <= q; ++i) {
while (pre < qq[i].m) {
++pre;
m1.insert (1, INT_MAX, b[pre]);
m2.insert (1, INT_MAX, b[pre]);
}
qq[i].ans = query (qq[i].k);
}
sort (qq + 1, qq + q + 1, [](Q a, Q b){return a.id < b.id;});
for (int i = 1; i <= q; ++i) {printf ("%d
", qq[i].ans);}
return 0;
}
Conclusion
杨氏矩阵还是挺有意思的，但是就这道题来说，这个解法也很有意思啊。