题解 P3774 【[CTSC2017]最长上升子序列】

· · 题解

可以看这里哦

一道杨表的神题。 <!--more-->

前置知识：杨表。

杨表（又称为杨氏矩阵、杨图、Young\ Diagram），是一种特殊的图，用于整数划分类问题上。

杨表定义如下：

对于一个n的划分\lambda=(\lambda_1,\lambda_2,...)\mapsto n定义为杨表为一个左对齐的方块组，其中第i行有\lambda_i个方块。

类似于这样

（画的丑）

我们定义钩子长h(u)（Young\ Diagram）为一个方块它下面的块数和它右边的块数之和（包括本身）。

这里每个格子上的数字表示这个格子的钩子长

我们定义标准杨表（SYT）为将{1,2,...,n}填入杨表且满足从上到下，从左到右数字都是满足比较方式<的杨表。

像这样

我们再定义f^{\lambda}为\lambda对应的标准杨表的个数。

于是可以定义钩子公式：对于\lambda\mapsto n，有f^{\lambda}=\frac{n!}{\prod_{u\in \lambda}h(u)}。

证明考虑组合意义即可。

下面再定义近似杨表（NYT）为将n个不同的数填入杨表且满足从上到下，从左到右数字都是满足比较方式<的杨表。

下面讲述如何构造近似杨表，我们考虑增量法。

每次将一个新的元素插入时，先在第一行查找是否有其后继，若有，替换其后继，让其后继在下一行进行新的查找，递归下去。若无，则插入到这一行的末尾。这样每次插入元素的复杂度可以证明为O(rlogc)，r为行数，c为列数。

同时根据RSK算法，我们可以构造一个关于杨表二元组集合与n个元素之间的双射，即S_{(P,Q)}\leftrightarrow S_n，其中P为近似杨表，Q为标准杨表。RSK算法不再过多赘述，感兴趣可以去wiki一下，这道题只利用到这个算法中的一个性质，即对于任意排列\pi\in S_n，其最长上升子序列的长度等于\pi对于的P的第一行长度。

对于杨表，还有一个性质，即若将其的比较方式取反（<变\geq,>变\leq)，所得杨表为原杨表的转置。（这里的转置定义为形状对称，并非元素对称，即元素可以滑动）

接下来回到这道题。

根据Dilworth定理，我们可以知道一个序列的最长上升子序列的长度等于将其分为若干个不上升子序列所需数量的最小值。

因此，题意转换成对于B的每一个前缀，取出不超过k个最长上升子序列，求最多能取走多少元素。

再根据杨表的性质，我们可以知道求的这个东西即为该序列的不上升杨表中前k行元素数量之和。

于是我们将询问离线，等于每次插入一些元素，然后动态地维护前k行的值即可。若暴力做，则是O(nrlogc)的，这样显然过不了。我们考虑总元素个数是O(n)的，于是对于每一个元素而言，它所在的行与列总有一个是\leq \sqrt{n}的。对于行，我们直接维护前\sqrt{n}行即可。对于列，我们将杨表的比较方式取反，维护转置后的前\sqrt{n}行即可。于是复杂度就在O(n\sqrt{n}logn+qlogn)或者O(n\sqrt{n}logn+q\sqrt{n})了。

code:

//2019.9.6 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define lowbit(x) (x&-x)
#define gc getchar
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
    res s=0,ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//inline int read() {
//    res s=0,ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
//inline void write(RG unl x){
//    if(x>10)write(x/10);
//    putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
//    if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int kcz=998244353;
const int N=2e5+10;
const int M=300;
namespace MAIN{
    inline void add(res &x,const res &y){
        x+=y,x>=kcz?x-=kcz:1;
    }
    inline int mul(const res &x,const res &y){
        return int(1LL*x*y%kcz);
    }
    inline int Add(const res &x,const res &y){
        return x+y>=kcz?x+y-kcz:x+y;
    }
    inline int qpow(res x,res y){
        res ret=1;
        while(y){
            if(y&1)ret=mul(ret,x);
            x=mul(x,x),y>>=1;
        }
        return ret;
    }
    int n,q;
    int tr[N];
    inline void modify(const res &x,const res &y){
        for(res i=x;i<=n;i+=lowbit(i))tr[i]+=y;
    }
    inline int query(const res &x){
        res ret=0;
        for(res i=x;i;i-=lowbit(i))ret+=tr[i];
        return ret;
    }
    int a[N];
    struct Que{
        int m,k,id;
        Que() {}
        Que(res m,res k,res id):m(m),k(k),id(id) {}
        inline bool operator < (const RG Que &b) const {
            return m<b.m;
        }
    }Q[N];
    int ans[N],bl;
    vector<int> YT[M],TY[M];
    inline void add(const res &va){
        for(res i=1,x=va;i<bl;i++){
            if(YT[i].empty()||YT[i].back()>=x){YT[i].pb(x),modify(i,1);break;}
            swap(YT[i][upper_bound(YT[i].begin(),YT[i].end(),x,greater<int>())-YT[i].begin()],x);
        }
        for(res i=1,x=va;i<bl;i++){
            if(TY[i].empty()||TY[i].back()<x){
                TY[i].pb(x);
                if(TY[i].size()>=bl)modify(int(TY[i].size()),1);
                break;
            }
            swap(TY[i][lower_bound(TY[i].begin(),TY[i].end(),x)-TY[i].begin()],x);
        }
    }
    inline void MAIN(){
        n=read(),q=read(),bl=int(sqrt(n))+1;
        for(res i=1;i<=n;i++)a[i]=read();
        for(res i=1;i<=q;i++){
            res m=read(),k=read();
            Q[i]=Que(m,k,i);
        }
        sort(Q+1,Q+q+1);
        for(res i=1;i<=q;){
            res j=i;
            for(res k=Q[i-1].m+1;k<=Q[i].m;k++)add(a[k]);
            while(Q[j].m==Q[i].m&&j<=q)j++;
            j--;
            for(res k=i;k<=j;k++)ans[Q[k].id]=query(Q[k].k);
            i=j+1;
        }
        for(res i=1;i<=q;i++)printf("%d\n",ans[i]);
    }
}
int main(){
//    srand(19260817);
//    freopen("signin.in","r",stdin);
//    freopen("signin.out","w",stdout);
    MAIN::MAIN();
    return 0;
}