刷题记录:牛客NC54585小魂和他的数列 [线段树卡常,真恶心]

传送门:牛客

题目描述:

一天，小魂正和一个数列玩得不亦乐乎。
小魂的数列一共有n个元素，第i个数为Ai。
他发现，这个数列的一些子序列中的元素是严格递增的。
他想知道，这个数列一共有多少个长度为K的子序列是严格递增的。
请你帮帮他，答案对998244353取模。
对于100%的数据，1≤ n ≤ 500,000,2≤ K ≤ 10,1≤ Ai ≤ 109。
输入:
5 3
2 3 3 5 1
输出:
2

前置提要:本题卡线段树常数,十分恶心,本人试了几次卡常,只能优化到85分

首先看到题面,我们会发现这是一个比较清明的$dp$题.我们设$dp[i][j]$为以$i$位置结尾长度为$j$的子序列的的个数.那么对于当前的$i,j$来说,我们的需要找到前$i-1$个位置中每一个$dp[k][j-1]k\in [1,i-1]\&\&a[k]<a[i]$然后进行累加,此时如果我们直接使用$for$进行枚举会发现时间复杂度是不对的.此时复杂度达到了$n\ast k\ast logn$所以我们需要进行优化

我们可以用线段树树状数组来维护这个题目.开$k$个线段树树状数组来维护$i-1$之前所有位置子序列长度为$lenlen\in [1,k]$的子序列个数.那么对于我们现在的$dp[i][j]$来说,$dp[i][j]=query(j-1,1,i-1)参数(id,l,r)$.用$ans$累加一下即可

本题需要进行离散化操作

下面是本人优化到平常极限的线段树代码(85分):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 500100
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,sum;
}tree[11][maxn*4];
const int mod=998244353;
inline void update(int id,int pos,int v,int l,int r,int rt) {if(l==pos&&r==pos) {tree[id][rt].sum=(tree[id][rt].sum+v)%mod;return ;}int mid=(l+r)>>1;if(pos<=mid) update(id,pos,v,l,mid,ls);else update(id,pos,v,mid+1,r,rs);tree[id][rt].sum=(tree[id][ls].sum+tree[id][rs].sum)%mod;
}
inline int query(int id,int l,int r,int L,int R,int rt) {if(L==l&&R==r) return tree[id][rt].sum;int mid=(L+R)>>1;if(r<=mid) return query(id,l,r,L,mid,ls);else if(l>mid) return query(id,l,r,mid+1,R,rs);else return (query(id,l,mid,L,mid,ls)+query(id,mid+1,r,mid+1,R,rs))%mod;
}
int n,k;int a[maxn];
int v[maxn];
int main() {n=read();k=read();for(int i=1;i<=n;i++){a[i]=read();v[i-1]=a[i];}sort(v,v+n);int Size=unique(v,v+n)-v;int ans=0;for(int i=1;i<=n;i++) {int x=lower_bound(v,v+Size,a[i])-v+1;update(1,x,1,1,Size,1);if(x-1==0) continue;for(int j=2;j<=k;j++) {if(j-1>i) continue;int sum=query(j-1,1,x-1,1,Size,1);if(j==k) ans=(ans+sum)%mod;update(j,x,sum,1,Size,1);}}cout<<ans<<endl;return 0;
}

---

下面是可以AC本题的树状数组代码(等我去学完立马补上,博主已简单过了一遍):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
const int mod=998244353;
inline int lowbit(int x) {return x&(~x+1);
}
int n,k;int a[maxn];int sum[11][maxn];
vector<int>v;
void add(int id,int pos,int v) {while(pos<=n) {sum[id][pos]=(sum[id][pos]+v)%mod;pos+=lowbit(pos);}
}
int query(int id,int pos) {int ans=0;while(pos) {ans=(ans+sum[id][pos])%mod;pos-=lowbit(pos);}return ans;
}
int main() {n=read();k=read();for(int i=1;i<=n;i++) {a[i]=read();v.push_back(a[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int ans=0;for(int i=1;i<=n;i++) {int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;add(1,x,1);for(int j=2;j<=k;j++) {int sum=query(j-1,x-1);if(j==k) ans=(ans+sum)%mod;add(j,x,sum);}}cout<<ans<<endl;return 0;
}