CF1621G Weighted Increasing Subsequences 题解

题目链接

点击打开链接

题目解法

这种题就感觉每一步都不难想，但串在一起就不会

显然考虑位置 \(x\) 作为 \(lis\) 的一部分，合法的 \(lis\) 的个数
合法的约束是：令 \(lis\) 的最后一个位置为 \(last\)，满足 \(\max\{a_{last+1},...,a_n\}>a_x\)
不难发现，合法的 \(last\) 是一段区间 \([x,r_x]\)，且 \(r_x\) 不难求出
容斥一下，相当于 经过点 \(x\) 的 \(lis\) 个数 \(-\) 经过点 \(x\) 且 \(last\) 在 \((r_x,n]\) 的 \(lis\) 个数
前一部分是好求的
后一部分我们考虑 \(r_i\) 实际上是最后一个满足 \(a_{r_x+1}>a_x\) 的位置，所以 \((r_x+1,n]\) 的位置一定不能作为 \(last\)，这等价于我们需要求 经过 \(x\)，且在 \(r_x+1\) 结束的 \(lis\) 个数
我们考虑 \(r_x\) 一定是最远能结束的 \(lis\) 的位置，所以在树状数组中多记一维就好了

时间复杂度 \(O(\sum n\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010,P=1e9+7;
int n,cnt,a[N],disc[N],mx[N],nxt[N];
int pre[N],suf[N],f[N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline void dec(int &x,int y){ x-=y;if(x<0) x+=P;}
#define lowbit(x) x&-x
struct fenwick{
    int tr[N];
    void add(int x,int v){ for(;x<=cnt;x+=lowbit(x)) inc(tr[x],v);}
    int ask(int x){ int res=0;for(;x;x-=lowbit(x)) inc(res,tr[x]);return res;}
    void clr(){ F(i,1,n) tr[i]=0;}
}fwk;
struct fenwick2{
    int tr[N],mx[N];
    void add(int x,int to,int v){
        for(;x<=cnt;x+=lowbit(x)){
            if(to>mx[x]) mx[x]=to,tr[x]=0;
            if(to==mx[x]) inc(tr[x],v);
        }
    }
    pii ask(int x){
        int to=0,res=0;
        for(;x;x-=lowbit(x)){
            if(mx[x]>to) to=mx[x],res=0;
            if(mx[x]==to) inc(res,tr[x]);
        }
        return {to,res};
    }
    void clr(){ F(i,1,n) tr[i]=mx[i]=0;}
}fwk2;
void work(){
    read(n);
    F(i,1,n) read(a[i]),disc[i]=a[i];
    sort(disc+1,disc+n+1);
    cnt=unique(disc+1,disc+n+1)-disc-1;
    F(i,1,n) a[i]=lower_bound(disc+1,disc+cnt+1,a[i])-disc;
    mx[n+1]=0;
    DF(i,n,1) mx[i]=max(mx[i+1],a[i]);
    F(i,1,n){
        int lo=i,hi=n+1;
        while(lo<hi-1){
            int mid=(lo+hi)>>1;
            if(mx[mid]>a[i]) lo=mid;
            else hi=mid;
        }
        nxt[i]=lo;
    }
    fwk.clr();
    F(i,1,n) pre[i]=(fwk.ask(a[i]-1)+1)%P,fwk.add(a[i],pre[i]);
    fwk.clr();
    DF(i,n,1) suf[i]=(fwk.ask(cnt-a[i])+1)%P,fwk.add(cnt-a[i]+1,suf[i]);
    int ans=0;
    F(i,1,n) inc(ans,1ll*pre[i]*suf[i]%P);
    fwk2.clr();
    DF(i,n,1){
        auto [to,v]=fwk2.ask(cnt-a[i]);
        if(a[i]==mx[i]) to=i,v=1;
        fwk2.add(cnt-a[i]+1,to,v);
        dec(ans,1ll*pre[i]*v%P);
    }
    printf("%d\n",ans);
}
int main(){
    int T;read(T);
    while(T--) work();    
    return 0;
}