权值线段树

· · 题解

Update on 2023.10.23 修改了配图的样例解释中的错误。

前言

这个题真的卡了我好久，最开始写的正解因为一些莫名其妙的原因 RE 了。。

Solution

发现值域 [1,n] 始终是固定的，看到题解里全是平衡树维护，果断掏出看家本领权值线段树。

前置知识：线段树 - OI Wiki，O(n \log n) 最长上升子序列做法。后者不熟悉的同学可以去看看P1020 [NOIP1999 普及组] 导弹拦截后 100 分的加强数据。

什么是权值线段树？

以权值为维护信息的线段树，本质仍是线段树。

不同于普通线段树所维护的区间信息，权值线段树维护的是值域固定，并统计 一列数字中数的个数。

我们可以联想到桶排序中桶的概念，权值线段树的一个节点维护就是一个桶，在一个节点所表示的区间 [l,r] 中，该节点本身的值即表示这个区间内数的个数。

举个栗子：有这样一个数列，

1\space1\space1\space2\space3\space3\space4\space5\space......

权值线段树上表示区间 [1,1] 的节点值为 3 表示有 3 个 1 ，表示区间 [2,2] 的节点值为 1 ，而他们的父节点表示 [1,2] ，值为 4 ，表示有 4 个 1 和 2 ，以此类推。

建树

void build(int p = 1,int l = 1,int r = n){
    if(l == r) return t[p] = a[l],void();//a[l]表示l的个数
    register int mid(l+r>>1);
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p] = t[p<<1]+t[p<<1|1];//建议写个push_up因为修改的时候也有相同操作，如果维护的信息更复杂会方便一些
}
int main(){
    build();//直接建
}

修改

void modify(int val,int k,int p = 1,int l = 1,int r = n){//将权值val增加k个
    if(l == r) return t[p]+=k,void();//如果到了叶子，直接加
    register int mid(l+r>>1);
    if(k <= mid) modify(val,k,p<<1,l,mid);//如果k在该节点左子树所表示的区间内
    else modify(val,k,p<<1|1,mid+1,r);//如果在右子树中
    push_up(p);//t[p] = t[p<<1]+t[p<<1|1]; 这里一定要记得
}

用排名查询数值

int query(int k,int p = 1,int l = 1,int r = n){//查询第k小的数是多少
    if(l == r)return l;//递归到了叶子节点
    register int mid(l+r>>1);
    if(k <= t[p<<1]) return query(k,p<<1,l,mid);//如果左子树的大小大于等于k，说明排名k一定在左，否则在右
    else return query(k-t[p<<1],p<<1|1,mid+1,r);//把左边的数量减掉，相当于在右边找第k-t[p<<1]的数
}

实际上权值线段树还可以用值查排名，同样也可以求前驱后继，没错，它就是平衡树的平替版，而且编码难度低，实际上统计区间数字个数很像平衡树统计子树大小来求排名、前驱、后继等操作，只是有一个问题，权值线段树需要提前知晓所有数值的范围，所以很适合用来处理 n 个数分别为 1 到 n 的问题，而且如果数据分散的话空间浪费很大，一般搭配动态开点食用，具体操作上面丢的线段树网址里面有。

甩一道练习题：P3224 [HNOI2012] 永无乡

回到本题

考虑维护插入后的序列，因为后插入的会影响先差入的点，就考虑逆序处理，先插入的直接挤到后面即可。再就是逆序处理很容易发现一个性质，就是插入位置的编号即使当前空位的编号，这样子空说可能不好理解，我们来看一个样例：

5
0 0 1 2 2

初始状态全是空位

倒序处理时，先将 5 插入第二个空位。

再将 4 插入第二个空位。

把 3 插入第一个。

接着插入 2 。

最后再插入 1 （就不放图了大家都会）。

那么我们就需要快速求出排名 k 的空位，联系前文，用权值线段树维护，初始整个区间赋值为 1 ，每次查询排名第 k ，查询结束后把其修改为 0 即可。

求最长上升子序列

这一部分很简单，建议自己想。

考虑动态规划，f[i] 表示长度为 i 的最小的最后一位数，易证明 f 数组具有单调性，每次再里面二分查找。

以 mx_i 表示以 i 结尾的最大上升子序列长度，记得开个 ans 记录全局最大，因为最长上升子序列可能不以这个点结尾。

code

/*
by tanhaotian
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)//想学习题解的同学请把这几行删掉
#include <bits/stdc++.h>
#define f_inline inline __attribute__((always_inline))
#define ll long long
using namespace std;
const int maxn = 1e5+5;
namespace quick{
    inline int read(){
        int x;
        char c=getchar();x=0;int f=0;
        for(;!isdigit(c);c=getchar()) f|=(c=='-');
        for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
        return x=f?-x:x;
    }
    inline ll _read(){
        ll x;
        char c=getchar();x=0;int f=0;
        for(;!isdigit(c);c=getchar()) f|=(c=='-');
        for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
        return x=f?-x:x;
    }
    template< typename T >inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10^48);
    }
    template< typename T >inline void print(T x){
        write(x);putchar('\n');
    }
    template< typename T >inline void _print(T x){
        write(x);putchar(' ');
    }
    inline void swap(int &a,int &b){a^=b,b^=a,a^=b;}
    inline int max(const int &a,const int &b){return a>b?a:b;}
    inline int min(const int &a,const int &b){return a<b?a:b;}
    inline int abs(int x){return x>0?x:-x;}
    inline ll labs(ll x){return x>0?x:-x;}
}
using namespace quick;
int t[maxn<<2],n;
f_inline void upd(int p){t[p] = t[p<<1]+t[p<<1|1];}
void build(int p = 1,int l = 1,int r = n){
    if(l == r) return t[p] = 1,void();
    int mid((l+r)>>1);
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    upd(p);
}
void modify(int k,int p = 1,int l = 1,int r = n){
    if(l == r) return t[p] = 0,void();
    int mid((l+r)>>1);
    if(k <= mid) modify(k,p<<1,l,mid);
    else modify(k,p<<1|1,mid+1,r);
    upd(p);
}
int query(int k,int p = 1,int l = 1,int r = n){
    if(l == r) return l;
    int mid((l+r)>>1);
    if(k <= t[p<<1]) return query(k,p<<1,l,mid);
    else return query(k-t[p<<1],p<<1|1,mid+1,r);
}
int ans;
int stpos[maxn];
int pos[maxn];
int f[maxn];
int mx[maxn];
f_inline int binary(int x){
    int l = 1,r = n;
    while(l < r){
        register int mid((l+r)>>1);
        f[mid] < x? l = mid+1 : r = mid;
    }
    return l;
}
int main(){
   freopen("lis.in","r",stdin);
   freopen("lis.out","w",stdout);
    n = read();
    build(); 
    for(register int i(1);i <= n;++i){
        stpos[i] = read(); ++stpos[i]; f[i] = 0x3f3f3f3f;
    }
    for(register int i(n);i;--i){
        register int t = query(stpos[i]);
        pos[t] = i;
        modify(t);
    }
//  for(register int i(1);i <= n;++i)
//      print(pos[i]);
    for(register int i(1);i <= n;++i){
        register int t = binary(pos[i]);
        f[t] = pos[i];
        mx[pos[i]] = t;
    }
//  for(register int i(1);i <= n;++i)
//      print(mx[i]);
    for(register int i(1);i <= n;++i){
        if(mx[i] > ans) ans = mx[i];
        print(ans);
    }
    return 0;
}