专栏文章

P12523 [Aboi Round 1] Nomad 做题记录

ggcx12012
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip7j86x
此快照首次捕获于
2025/12/03 07:26
3 个月前
此快照最后确认于
2025/12/03 07:26
3 个月前
查看原文

前言

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

Solution

首先直接维护是非常困难的，考虑寻找 f(x)f(x) 的特殊性质。
发现 f(x)=x(x+2)=(x+1)2−1f(x)=x(x+2)=(x+1)^2-1。
然后题目要求非空子序列积和，把未在子序列内的点值设为 11，那么我们要求的就是：
∏i=lr(1+ai)−1\prod_{i=l}^r (1+a_i)-1
其中 −1-1 是减掉空子序列对答案的贡献。
然后你发现常系数被抵消掉了，于是先把全部 ai+1a_i+1 后就变成区间 ai2k→aia_i^{2^k}\to a_i 以及区间积。
直接线段树做的话是 O(qlog⁡2n)O(q\log^2 n) 的，显然无法通过最后一个 sub，于是我们把 aia_i 转化为它的离散对数，因为 log⁡ab=log⁡a+log⁡b,log⁡ab=blog⁡a\log ab=\log a+\log b,\log a^b=b \log a，于是我们可以把幂操作转为乘操作，求积转化为求和，这里我们利用  mod \bmod 的一个原根 g=5g=5 来解决。
求一个数的离散对数可以用 BSGS 解决，当然也可以用某个基于值域的科技，但是没有必要。
这里转化离散对数的复杂度是 O( mod B+nB)O(\frac{\bmod}{B}+nB) 的，取 B=30B=30 时较优。
然后线段树部分就可以做到 O(qlog⁡n)O(q \log n) 的复杂度了，常数比较大，可能需要稍微卡一下常。
CPP
#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;
}
/*

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...