青蛙树

C++(g++ 7.5.0) 解法, 执行用时: 3377ms, 内存消耗: 475088K, 提交时间: 2023-05-06 08:58:19

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
// #define double long double
#define eps (1e-15)
#define lowbit(i) ((i)&(-i))
const int mod=998244353;
const int N=1e6+10;
int fac[N],facinv[N],inv[N],cat[N<<1],catinv[N<<1];
typedef array<int,2> pr;
int fast(int x,int k)
{
	int ret=1;
	while(k)
	{
		if(k&1) ret=ret*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ret;
}
void init(int n=1e6)
{
	fac[0]=facinv[0]=1;
	for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	facinv[n]=fast(fac[n],mod-2);
	for(int i=n-1;i>=1;--i) facinv[i]=facinv[i+1]*(i+1)%mod;
	cat[0]=catinv[0]=inv[1]=1;
	for(int i=2;i<=n+1;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;++i) cat[i]=cat[i-1]*(4*i-2)%mod*inv[i+1]%mod,catinv[i]=fast(cat[i],mod-2);
}
struct dkr
{
	int n,top,rt;
	int a[N],st[N];
	int son[N][2],dep[N],f[N][21],g[N][21];
	int lg[N],rg[N],len[N];
	int ilg[N],irg[N];
	void dfs(int now,int fa)
	{
		if(now==0)
		{
			lg[now]=rg[now]=1;return;
		}
		dep[now]=dep[fa]+1;
		f[now][0]=fa;
		for(int i=1;i<=20;++i) f[now][i]=f[f[now][i-1]][i-1];
		dfs(son[now][0],now);
		dfs(son[now][1],now);
		if(a[son[now][1]]==a[now]) len[now]=len[son[now][1]]+1;
		else len[now]=1;
		lg[now]=lg[son[now][0]]*rg[son[now][0]]%mod;
		rg[now]=lg[son[now][1]]*rg[son[now][1]]%mod*cat[len[now]]%mod*catinv[len[now]-1]%mod;
	}
	void dfs(int now)
	{
		if(now==0) return;
		if(now!=rt)
		{
			lg[now]=lg[now]*lg[f[now][0]]%mod;
		}
		ilg[now]=fast(lg[now],mod-2);
		irg[now]=fast(rg[now],mod-2);
		g[now][0]=rg[now];
		for(int i=1,v=now;i<=20;++i)
		{
			g[now][i]=g[now][i-1]*g[f[now][i-1]][i-1]%mod;
			if(son[f[v][0]][0]!=v) g[now][i]=g[now][i]*irg[f[v][0]]%mod;
			v=f[v][i-1];
		}
		dfs(son[now][0]);dfs(son[now][1]);
	}
	void init()
	{
		top=0;
		for(int i=1;i<=n;++i)
		{
			while(top&&a[st[top]]>a[i])
			{
				if(top>1&&a[st[top-1]]>a[i])
					son[st[top-1]][1]=st[top];
				else son[i][0]=st[top];
				--top;
			}
			st[++top]=i;
		}
		while(top>1) son[st[top-1]][1]=st[top],--top;
		rt=st[top];
		dfs(rt,0);
		dfs(rt);
	}
	int getlca(int x,int y)
	{
		while(dep[x]^dep[y])
		{
			if(dep[x]<dep[y]) swap(x,y);
			x=f[x][__lg(dep[x]-dep[y])];
		}
		if(x==y) return x;
		for(int i=20;~i;--i) if(f[x][i]^f[y][i])
			x=f[x][i],y=f[y][i];
		return f[x][0];
	}
	pr cal(int x,int y)
	{
		int lca=getlca(x,y);
		if(x==lca) return pr{1,x};
		int sum=rg[x];
		int xx=x;
		x=f[x][0];
		for(int i=20;~i;--i) if(dep[f[x][i]]>=dep[lca])
		{
			sum=sum*g[x][i]%mod;
			if(son[x][0]!=xx) sum=sum*irg[x]%mod;
			x=f[x][i];
			xx=f[xx][i];
		}
		return pr{sum,x};
	}
}t1,t2;
void solve()
{
	init();
	int n;cin>>n;
	t1.n=n,t2.n=n;
	for(int i=1;i<=n;++i)
	{
		cin>>t1.a[i];
		t2.a[n-i+1]=t1.a[i];
	}
	t1.init();
	t2.init();
	int m;cin>>m;
	while(m--)
	{
		int l,r;cin>>l>>r;
		pr x=t1.cal(l,r),y=t2.cal(n-r+1,n-l+1);
		int ans=x[0]*y[0]%mod;
		int u=x[1],v=n-y[1]+1;
		ans=ans*t1.lg[v]%mod*t1.ilg[u]%mod*cat[t1.len[u]-t1.len[v]+1]%mod;
		cout<<ans<<'\n';
	}
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
    // cout<<clock()-st<<'\n';
    return 0;
}
/*
3*5 7*4 11*3 15*2 19*1
\sum (st+4i)(t-i)
\sum (st*t-i*st+4*i*t-4*i*i0)

*/

C++14(g++5.4) 解法, 执行用时: 3607ms, 内存消耗: 46264K, 提交时间: 2020-07-11 08:20:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353,block=700;
const int N=1e6+5;
int n,q,a[N],ans[N];
ll res,f[N],invf[N],cat[N],invcat[N];
ll C(ll n,ll m)
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
struct node
{
    int l,r,id;
    bool operator<(const node&o)const
    {
        if(l/block==o.l/block) return r<o.r;
        return l<o.l;
    }
}b[N];
int top,st[N],len[N];
void brute(int s)
{
    top=0;
    int l=b[s].l,r=b[s].r;
    ll res=1;
    for(int i=l;i<=r;i++)
    {
        while(top&&st[top]>a[i]) top--;
        if(!top||a[i]>st[top]) st[++top]=a[i],len[top]=1;
        else
        {
            res=res*invcat[len[top]]%mod;
            len[top]++;
            res=res*cat[len[top]]%mod;
        }
    }
    ans[b[s].id]=res;
}
int le,ri,que[N],sum[N];
int que2[N],sum2[N];
bool vis[N];
void add(int x)
{
    while(ri>=le&&que[ri]>a[x]&&vis[ri]) ri--;
    if(ri<le) que[++ri]=a[x],vis[ri]=false,sum[ri]=1;
    else if(a[x]==que[ri])
    {
        res=res*invcat[sum[ri]]%mod;
        sum[ri]++;
        res=res*cat[sum[ri]]%mod;
    }
    else
    {
        vis[ri+1]=a[x]>que[ri];
        que[++ri]=a[x];
        sum[ri]=1;
    }
}
int solve(int s)
{
    int k,l=b[s].l/block*block+block,r=l-1;
    res=1;le=500001;ri=le-1;
    for(k=s;k<=q&&b[k].l/block==b[s].l/block;k++)
    {
        if(b[k].l/block==b[k].r/block) {brute(k);continue;}
        while(r<b[k].r) add(++r);
        ll rres=res;
        int lle=le,rri=ri,f=le;
        for(int i=l-1;i>=b[k].l;i--)
        {
            while(lle<=rri)
            {
                while(f<=lle) que2[f]=que[f],sum2[f]=sum[f],f++;
                if(que2[lle]>a[i]) lle++;
                else break;
            }
            if(lle>rri||que2[lle]<a[i]) que2[--lle]=a[i],sum2[lle]=1;
            else if(que2[lle]==a[i])
            {
                rres=rres*invcat[sum2[lle]]%mod;
                sum2[lle]++;
                rres=rres*cat[sum2[lle]]%mod;
            }
        }
        ans[b[k].id]=rres;
    }
    return k;
}
int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int main()
{
    srand(time(0));
    cat[0]=f[0]=f[1]=invf[0]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i]*invf[i-1]%mod;
    for(int i=1;i<=500000;i++) cat[i]=(C(2*i,i)-C(2*i,i-1)+mod)%mod,invcat[i]=qpow(cat[i],mod-2);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    q=read();
    for(int i=1;i<=q;i++) b[i].l=read(),b[i].r=read(),b[i].id=i;
    if(rand()&1)
    {
        reverse(a+1,a+1+n);
        for(int i=1;i<=q;i++) b[i].l=n-b[i].l+1,b[i].r=n-b[i].r+1,swap(b[i].l,b[i].r);
    }
    sort(b+1,b+1+q);
    for(int i=1;i<=q;) i=solve(i);
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}

C++(clang++11) 解法, 执行用时: 2889ms, 内存消耗: 232484K, 提交时间: 2020-11-03 18:02:47

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define N 500050
const int mod=998244353;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,Q;
int ifac[N<<1],fac[N<<1],a[N],h[N],cat[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
	}
}
inline int C(int n,int m){
	if(n<m||n<0||m<0)return 0;
	return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
struct Tree{
	int d[N],f[N][21],g[N][21],dep[N],val[N],root,s[N],invs[N];
	struct node{
		int ch[2];
	}t[N];
	#define ls t[u].ch[0]
	#define rs t[u].ch[1]
	void build(){
		static int st[N],top;
		top=0;
		for(int i=1;i<=n;++i){
			while(top&&a[st[top]]>a[i])t[i].ch[0]=st[top--];
			if(top)t[st[top]].ch[1]=i;
			st[++top]=i;
		}
		root=st[1];
	}
	void dfs1(int u,int fa){
		f[u][0]=fa;
		dep[u]=dep[fa]+1;
		if(ls)dfs1(ls,u);
		if(rs)dfs1(rs,u);
		d[u]=1;
		if(rs&&a[rs]==a[u])d[u]+=d[rs];
		val[u]=h[d[u]];
		if(ls)val[u]=1LL*val[u]*val[ls]%mod;
		if(rs)val[u]=1LL*val[u]*val[rs]%mod;
	}
	void dfs2(int u){
		s[u]=1LL*s[f[u][0]]*val[ls]%mod;
		for(int j=1;j<=19;++j){
			f[u][j]=f[f[u][j-1]][j-1];
			g[u][j]=1LL*g[u][j-1]*g[f[u][j-1]][j-1]%mod;
		}
		if(ls)g[ls][0]=1LL*val[rs]*h[d[u]]%mod,dfs2(ls);
		if(rs)g[rs][0]=1,dfs2(rs);
	}
	pair<int,int> Query(int u,int v){
		int ans=1LL*h[d[u]]*val[rs]%mod;
		if(dep[u]<=dep[v]){
			for(int i=19;i>=0;--i){
				if(dep[f[v][i]]>=dep[u])v=f[v][i];
			}
			if(v==u)return make_pair(1,v);
		}
		else{
			for(int i=19;i>=0;--i){
				if(dep[f[u][i]]>dep[v])ans=1LL*ans*g[u][i]%mod,u=f[u][i];
			}
			if(f[u][0]==v)return make_pair(ans,v);
			ans=1LL*ans*g[u][0]%mod,u=f[u][0];
		}
		for(int i=19;i>=0;--i){
			if(f[u][i]^f[v][i]){
				ans=1LL*ans*g[u][i]%mod;
				u=f[u][i],v=f[v][i];
			}
		}
		return make_pair(ans,f[u][0]);
	} 
	void init(){
		build();
		val[0]=1;
		dfs1(root,0);
		g[root][0]=s[0]=1;
		dfs2(root);
		for(int i=1;i<=n;++i){
			invs[i]=qpow(s[i],mod-2);
		}
	}
}T1,T2;
int main(){
	n=read();
	init(n<<1);
	cat[0]=1;
	for(int i=1;i<=n;++i){
		cat[i]=(C(i<<1,i)-C(i<<1,i-1)+mod)%mod;
		h[i]=1LL*cat[i]*qpow(cat[i-1],mod-2)%mod;
	}
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	T1.init();
	reverse(a+1,a+n+1);
	T2.init();
	Q=read();
	while(Q--){
		int l=read(),r=read();
		auto t1=T1.Query(l,r);
		auto t2=T2.Query(n-r+1,n-l+1);
		int ans=1LL*t1.first*t2.first%mod;
		int u=t1.second,v=n-t2.second+1;
		ans=1LL*ans*cat[T1.dep[v]-T1.dep[u]+1]%mod;
		ans=1LL*ans*T1.s[v]%mod*T1.invs[u]%mod;
		printf("%d\n",ans);
	}
	return 0;
}

详情