P12523 [Aboi Round 1] Nomad 做题记录

· · 个人记录

前言

距离正解差一个离散对数转化，wtcl。

Solution

首先直接维护是非常困难的，考虑寻找 f(x) 的特殊性质。

发现 f(x)=x(x+2)=(x+1)^2-1。

然后题目要求非空子序列积和，把未在子序列内的点值设为 1，那么我们要求的就是：

\prod_{i=l}^r (1+a_i)-1

其中 -1 是减掉空子序列对答案的贡献。

然后你发现常系数被抵消掉了，于是先把全部 a_i+1 后就变成区间 a_i^{2^k}\to a_i 以及区间积。

直接线段树做的话是 O(q\log^2 n) 的，显然无法通过最后一个 sub，于是我们把 a_i 转化为它的离散对数，因为 \log ab=\log a+\log b,\log a^b=b \log a，于是我们可以把幂操作转为乘操作，求积转化为求和，这里我们利用 \bmod 的一个原根 g=5 来解决。

求一个数的离散对数可以用 BSGS 解决，当然也可以用某个基于值域的科技，但是没有必要。

这里转化离散对数的复杂度是 O(\frac{\bmod}{B}+nB) 的，取 B=30 时较优。

然后线段树部分就可以做到 O(q \log n) 的复杂度了，常数比较大，可能需要稍微卡一下常。

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 1000010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
const ll mod=1e9+7,B=30;
int a[N];
int n,q,tp;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int M=4e7;
struct hsh{
    int a1[M][2];
    bitset<M>vis;
    void ins(int x,int y){
        int id=x%M;
        while(vis[id]) id=(id+1)%M;
        vis[id]=1,a1[id][0]=x,a1[id][1]=y;
    }
    int qry(int x){
        int id=x%M;
        while(vis[id] && a1[id][0]!=x) id=(id+1)%M;
        return vis[id]?a1[id][1]:-1;
    }
}F;
ll ksm(int x,int y,int mod1){
    int p=1;
    while(y){
        if(y&1) p=1ll*p*x%mod1;
        x=1ll*x*x%mod1;
        y>>=1;
    }
    return p;
}
int sum[N<<2],tag[N<<2];
void build(int x,int l,int r){
    tag[x]=1;
    if(l==r){
        sum[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    sum[x]=(sum[ls]+sum[rs])%(mod-1);
}
void pushdown(int x){
    sum[ls]=1ll*sum[ls]*tag[x]%(mod-1);
    sum[rs]=1ll*sum[rs]*tag[x]%(mod-1);
    tag[ls]=1ll*tag[ls]*tag[x]%(mod-1);
    tag[rs]=1ll*tag[rs]*tag[x]%(mod-1);
    tag[x]=1;
}
void mul(int x,int l,int r,int L,int R,int v){
    if(L<=l && r<=R){
        sum[x]=1ll*sum[x]*v%(mod-1);
        tag[x]=1ll*tag[x]*v%(mod-1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(x);
    if(L<=mid) mul(lson,L,R,v);
    if(R>mid) mul(rson,L,R,v);
    sum[x]=(sum[ls]+sum[rs])%(mod-1);
}
ll qry(int x,int l,int r,int L,int R){
    if(L<=l && r<=R) return sum[x];
    int mid=(l+r)>>1;
    pushdown(x);
    ll p=0;
    if(L<=mid) p=(p+qry(lson,L,R))%(mod-1);
    if(R>mid) p=(p+qry(rson,L,R))%(mod-1);
    return p;
}

int main()
{
    //freopen("traffic.in","r",stdin);
    //freopen("traffic.out","w",stdout);
    n=read(),q=read(),tp=read();
    int wn=ksm(5,B,mod),inv=ksm(5,mod-2,mod);
    for(int i=0,w=1;i*B<mod;i++,w=1ll*w*wn%mod) F.ins(w,i*B);
    For(i,1,n){
        a[i]=read()+1;
        for(int j=0,w=1;j<B;j++,w=1ll*w*inv%mod){
            int now=F.qry(1ll*a[i]*w%mod);
            if(now>=0){
                a[i]=now+j;
                break;
            }
        }
    }
    build(1,1,n);
    ll ans=0;
    while(q--){
        int op=read(),l=read(),r=read(),k;
        if(op==1){
            k=read();
            mul(1,1,n,l,r,ksm(2,k,mod-1));
        }else{
            ll now=ksm(5,qry(1,1,n,l,r),mod);
            now=(now+mod-1)%mod;
            if(tp) ans^=now;
            else printf("%lld\n",now);
        }
    }
    if(tp) cout<<ans;
    return 0;
}
/*

*/