题解 Omeed

· · 个人记录

T3 Omeed

解题思路

大概有两种打法吧。。

对于基础分数的贡献十分简单在此不做过多的赘述。

对于连击分数的每个位置 i 对于下一位的贡献设为 f_i，就有了下面的柿子：

f_i=p_i\times (f_{i-1}+1)+(1-p_i)\times f_{i-1}\times t

经过层层化简就可以得到类似于 f_{i}=k\times f_{L-1}+b 的柿子，然后发现 k\times f_{L-1} 啥用没有，于是可以直接维护 b 的加和。

上面的是一种做法，但是实现起来比较麻烦，我直接。。。

下面讲一下另一种做法。。。

还是化简柿子，可以得到 \displaystyle f_k=\sum_{i=L}^{k}p_i\prod_{j=i+1}^{k}(t+p_i-p_i\times t)

然后对于每一个区间也是维护 k,b ，与上面做法不同的是这里的取值与左端点 f_L 的取值有关系，因此需要对于每个区间的右端点进行维护，用于合并信息。

有亿点卡常。

code

#include<bits/stdc++.h>
#define ull unsigned long long
#define f() cout<<"Pass"<<endl
#define ls x<<1
#define rs x<<1|1
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=5e5+10,mod=998244353;
int task,ta,tb,n,q,t,a,b,p[N],f[N];
int power(int x,int y)
{
    int temp=1;
    while(y)
    {
        if(y&1) temp=1ll*temp*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return temp;
}
int inv(int x){return power(x,mod-2)%mod;}
struct Segment_Tree
{
    int dat,k,b,datk,datb;
}tre[N<<1];
void update(int x,int num)
{
    tre[x].dat=tre[x].b=tre[x].datk=tre[x].datb=num;
    tre[x].k=(t+num-1ll*num*t%mod+mod)%mod;
}
void push_up(int x)
{
    tre[x].dat=(tre[ls].dat+tre[rs].dat)%mod;
    tre[x].k=1ll*tre[ls].k*tre[rs].k%mod;
    tre[x].b=(1ll*tre[rs].k*tre[ls].b+tre[rs].b)%mod;
    tre[x].datk=(tre[ls].datk+1ll*tre[rs].datk*tre[ls].k)%mod;
    tre[x].datb=(tre[ls].datb+1ll*tre[rs].datk*tre[ls].b+tre[rs].datb)%mod;
}
void insert(int x,int l,int r,int pos,int num)
{
    if(l==r)    return update(x,num),void();
    int mid=(l+r)>>1;
    if(pos<=mid)    insert(ls,l,mid,pos,num);
    else    insert(rs,mid+1,r,pos,num);
    push_up(x);
}
Segment_Tree query_seg(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)  return tre[x];
    int mid=(l+r)>>1;
    Segment_Tree ans1=(Segment_Tree){-1,0,0,0,0};
    Segment_Tree ans2=(Segment_Tree){-1,0,0,0,0};
    if(L<=mid)  ans1=query_seg(ls,l,mid,L,R);
    if(R>mid)   ans2=query_seg(rs,mid+1,r,L,R);
    if(~ans1.dat&&~ans2.dat)
        return (Segment_Tree){(ans1.dat+ans2.dat)%mod,1ll*ans1.k*ans2.k%mod,(1ll*ans2.k*ans1.b+ans2.b)%mod,(ans1.datk+1ll*ans2.datk*ans1.k)%mod,(ans1.datb+1ll*ans2.datk*ans1.b+ans2.datb)%mod};
    if(~ans1.dat)   return ans1;
    return ans2;
}
signed main()
{
    task=read();
    n=read();   q=read();
    ta=read();  tb=read();
    t=1ll*ta*inv(tb)%mod;
    a=read();   b=read();
    for(int i=1,pa,pb;i<=n;i++)
    {
        pa=read();  pb=read();
        p[i]=1ll*pa*inv(pb)%mod;
        insert(1,1,n,i,p[i]);
    }
    while(q--)
    {
        int opt,pos,pa,pb,l,r;
        opt=read();
        if(!opt)
        {
            pos=read(); pa=read();  pb=read();
            p[pos]=1ll*pa*inv(pb)%mod;
            insert(1,1,n,pos,p[pos]);
            continue;
        }
        l=read();   r=read();
        if(l==r){printf("%lld\n",1ll*(a+b)*p[l]%mod);continue;}
        Segment_Tree temp=query_seg(1,1,n,l+1,r);
        printf("%lld\n",(1ll*a*(1ll*temp.dat+p[l])%mod+1ll*(1ll*p[l]*temp.datk%mod+1ll*temp.datb+p[l])*b%mod)%mod);
    }
    return 0;
}