2019计蒜之道复赛 A 线段树求最长升子序列方案数
题意:给定长度为 n 的数列 a,显然这个数列有很多最长上升子序列,我们等概率地取出一个最长上升子序列,求每个数被选中的概率,对 998244353 取模。
链接:https://nanti.jisuanke.com/t/39611
题外话:勉强混了个前400拿T恤,中间麻将题不知道为什么常数奇大无比调了好久,导致比赛时候这个题没做出来。看了题解发现是个sb题简单题。我真的是弱啊。
思路:会用线段树求最长上升子序列就会这个了,思路是从左到右扫一遍,线段树维护以a[i]
结尾的最长上升子序列的方案数,显然一颗线段树或者bit都可以,单点修改前缀查询。同样的方法右边再来一次。最后直接就可以得出答案了---一个点在多少个最长上升子序列里/总上升子序列。
代码:
#include <bits/stdc++.h>
#define LL long long
#define inf 1000000007
#define pii pair<int,int>
#define mod 998244353
#define PB insert
#define X first
#define Y second
using namespace std;
const int maxn=1e7+7;
namespace seg_tree{
int len[maxn],lson[maxn],rson[maxn];
long long sum[maxn];
int N=0;
const int root=0;
void init(){
memset(len,0,sizeof(len));
memset(sum,0,sizeof(sum));
memset(lson,-1,sizeof(lson));
memset(rson,-1,sizeof(rson));
N=1;
}
void push_up(int rt){
int l=lson[rt],r=rson[rt];
if(len[l]==len[r]){
len[rt]=len[l],sum[rt]=(sum[l]+sum[r])%mod;
}
else{
if(len[l]<len[r])swap(l,r);
len[rt]=len[l],sum[rt]=sum[l];
}
}
void make_rt(int &x){
x=N++;
len[x]=sum[x]=0;
}
void add(int rt,int l,int r,int x,int le,long long su){
if(l==r){
if(len[rt]==le){
sum[rt]=(sum[rt]+su)%mod;
}
else if(len[rt]<le){
len[rt]=le;
sum[rt]=su;
}
return;
}
if(lson[rt]==-1)make_rt(lson[rt]);
if(rson[rt]==-1)make_rt(rson[rt]);
int mid = (l + r) / 2;
if(x<=mid) add(lson[rt],l,mid,x,le,su);
else add(rson[rt],mid+1,r,x,le,su);
push_up(rt);
}
pii query(int rt,int l,int r,int x){
if(r<=x){
return {len[rt],sum[rt]};
}
if(lson[rt]==-1)make_rt(lson[rt]);
if(rson[rt]==-1)make_rt(rson[rt]);
int mid = (l + r) / 2;
if(x<=mid){
return query(lson[rt],l,mid,x);
}
else{
pii a=query(lson[rt],l,mid,x);
pii b=query(rson[rt],mid+1,r,x);
if(a.X==b.X){
return {a.X,(a.Y+b.Y)%mod};
}
else{
if(a.X<b.X) swap(a,b);
return a;
}
}
}
}
LL q_pow(LL a,int n,int p){
LL r=1;
while(n){
if(n&1) r=(r*a)%p;
a=(a*a)%p;
n>>=1;
}
return r;
}
int a[maxn];
pii l[maxn],r[maxn];
int main(){
int n,L=0,R=1e9+7;
pii mx;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
seg_tree::init();
seg_tree::add(seg_tree::root,L,R,a[0],1,1);
l[0]={1,1};
for(int i=1;i<n;i++){
pii p=seg_tree::query(seg_tree::root,L,R,a[i]-1);
if(p.X==0) p={0,1};
seg_tree::add(seg_tree::root,L,R,a[i],p.X+1,p.Y);
l[i]={p.X+1,p.Y};
}
mx=seg_tree::query(seg_tree::root,L,R,R);
seg_tree::init();
seg_tree::add(seg_tree::root,L,R,R-a[n-1],1,1);
r[n-1]={1,1};
for(int i=n-2;i>=0;i--){
pii p=seg_tree::query(seg_tree::root,L,R,R-a[i]-1);
if(p.X==0) p={0,1};
seg_tree::add(seg_tree::root,L,R,R-a[i],p.X+1,p.Y);
r[i]={p.X+1,p.Y};
}
for(int i=0;i<n;i++){
if(r[i].X+l[i].X-1==mx.X){
cout<<((long long)r[i].Y*l[i].Y%mod)*q_pow(mx.Y,mod-2,mod)%mod<<" \n"[i==n-1];
}
else{
cout<<0<<" \n"[i==n-1];
}
}
return 0;
}