期望题目求助

站外题。题目大意：有一个长度为

n

的小写字母序列，定一个数

B

，区间

L,R

的值可以如下计算：

CPP

x=a[L]-'a'+1;
for(int i=L+1;i<=R;i++)
    x=x* B+(a[i]-'a'+1);

x

即为其结果。

现在给定

m

个操作，操作含义如下：

0 l r 表示求在区间 $[L,R]$ 中，随机取一个非空子区间的期望值。
1 l c 表示把序列的第 $l$ 位改成字母 $c$ 。

n,m\leq2\times10^5,B\leq10^9

，答案对

10^9+7

取模。

输入格式：第一行三个整数

n,m,B

，含义同上；接下来一行有一个

n

个字符的小写字符串，表示序列；接下来

m

行，表示

m

种操作。

样例输入：

CPP

样例输出：

CPP

333333363
666666677

样例解释：

333333363\equiv \frac{164}{6} \pmod {10^9+7},666666677\equiv\frac{17}{3}\pmod{10^9+7}

本人的大体思路是用线段树维护一个区间所有子区间的值得和，以及它所有前缀/后缀子区间所对应的的值的和。由于每个区间被选中的概率相等，因此先把每一个子区间的值的和算出来最后再除以非空子区间数量即可。而在合并两个区间时，形成的区间的贡献就是左边区间的贡献和右边区间的贡献加上两个区间拼在一起产生的新的贡献。

我搞了一份通过题目的代码进行对拍，拍了一个小时没拍出来，但是我的代码提交全 WA，蒟蒻求大佬帮调。

这是本人挂掉的代码：

CPP

#include<bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
#define LL long long
/*
	对于一个长度为 n 的区间 其一共有 n(n+1)/2 个非空子区间
	考虑不断的合并两个区间
	这个区间的总贡献 = 左半边的贡献 + 右半边的贡献 + 拼在一起产生的新贡献 
*/
const LL mod=1e9+7;
const int N=2e5+5;
LL qpow(LL a,LL x)
{
	LL res=1;
	while(x)
	{
		if(x&1)
			res=res*a%mod;
		x>>=1;
		a=a*a%mod;
	}
	return res;
}
LL inv(LL x){return qpow(x,mod-2);}
LL COUNT(LL x){return 1ll*x*(x+1ll)/2ll%mod;}
int read()
{
	char ch=getchar();
	int x=0;
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x;
}

int n,m;
LL B,invB_1;

struct node{
	LL tot,pre,suf,all,len;
	void upd(char x){tot=pre=suf=all=x&31;}
	node operator + (const node &s)const{
		node tmp;
		LL K=qpow(B,s.len),KK=(qpow(B,s.len+1)-B+mod)%mod*invB_1%mod;
		tmp=node{(tot+s.tot)%mod,0,0,0,len+s.len};
		tmp.tot=(len*s.pre%mod+tmp.tot)%mod;
		tmp.tot=(KK*suf%mod+tmp.tot)%mod;
		tmp.all=(K*all%mod+s.all)%mod;
		tmp.pre=((all*KK%mod+s.pre)%mod+pre)%mod;
		tmp.suf=((suf*K%mod+s.all*len%mod)%mod+s.suf)%mod;
		return tmp;
	}
}zero,tree[N<<2];

void update(int rt){tree[rt]=tree[lson]+tree[rson];}
void build(int rt,int l,int r)
{
	if(l==r)
	{
		char c=getchar();
		while(c<'a'&&c>'z')
			c=getchar();
		tree[rt].upd(c);
		tree[rt].len=1;
		return;
	}
	int mid=l+r>>1;
	build(lson,l,mid) ;
	build(rson,mid+1,r);
	update(rt);
}
void modify(int rt,int l,int r,int tar,char x)
{
	if(l>tar||r<tar)
		return;
	if(l==r)
	{
		tree[rt].upd(x&31);
		return;
	}
	int mid=l+r>>1;
	modify(lson,l,mid,tar,x);
	modify(rson,mid+1,r,tar,x);
	update(rt);
}
node query(int rt,int l,int r,int L,int R)
{
	if(l>R||r<L)
		return zero;
	if(L<=l&&r<=R)
		return tree[rt];
	node tmp1,tmp2,res;
	int mid=l+r>>1;
	tmp1=query(lson,l,mid,L,R);
	tmp2=query(rson,mid+1,r,L,R);
	res=tmp1+tmp2;
	return res;
}
int main()
{
	freopen("letter.in","r",stdin);
	freopen("letter.out","w",stdout);
	n=read(),m=read(),B=read();
	invB_1=inv(B-1);
	build(1,1,n);
	for(int i=1,opt;i<=m;++i)
	{
		opt=read();
		if(opt)
		{
			int pos=read();
			char c=getchar();
			while(c<'a'||c>'z')
				c=getchar();
			modify(1,1,n,pos,c);
		}
		else
		{
			int lb,rb,p;
			lb=read(),rb=read();
			p=inv(COUNT(rb-lb+1ll));
			node ans=query(1,1,n,lb,rb);
			printf("%lld\n",ans.tot*p%mod);
		}
	}
}

这是搞到的通过的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
using ll=long long;
int n,b;
int fp(int x,int y){
	int ans=1;
	while(y){
		if(y&1)
			ans=(ll)ans*x%mod;
		if(y>>=1)
			x=(ll)x*x%mod;
	}
	return ans;
}
struct tree_sz{
	int a[200005],tree[200005];
	void change(int x,int y){
		for(int i=x;i<=n;i+=i&-i)(tree[i]+=(y-a[x]+mod)%mod)%=mod;
		a[x]=y;
	}
	int ask(int x){
		int ans=0;
		while(x){
			(ans+=tree[x])%=mod;
			x&=x-1;
		}
		return ans;
	}
}i,j,k,f;
int ask(int l,int r){
	return ((i.ask(r)+mod-i.ask(l-1)+ll(j.ask(l-1)+mod-j.ask(r))*l)%mod*fp(b,r+1)+
	k.ask(l-1)+mod-k.ask(r)+ll(f.ask(r)+mod-f.ask(l-1))*l)%mod;
}
void change(int x,int y){
	i.change(x,y*(x+1ll)%mod*fp(fp(b,x)*(b-1ll)%mod,mod-2)%mod);
	j.change(x,(ll)y*fp(fp(b,x)*(b-1ll)%mod,mod-2)%mod);
	k.change(x,y*(x+1ll)%mod*fp(b-1,mod-2)%mod);
	f.change(x,(ll)y*fp(b-1,mod-2)%mod);
}
int main()
{
	freopen("letter.in","r",stdin);
	freopen("ans.out","w",stdout);
	int m;
	cin>>n>>m>>b;
	string s;
	cin>>s;
	for(int i=0;i<n;++i)change(i+1,s[i]-'a'+1);
	while(m--){
		int op,l,r;
		cin>>op;
		if(op==0){
			cin>>l>>r;
			cout<<2ll*ask(l,r)*fp((r-l+1)*(r-l+2ll)%mod,mod-2)%mod<<'\n';
		}else{
			cin>>l;
			cin.get();
			change(l,cin.get()-'a'+1);
		}
	}
}

讨论操作

回复

相关推荐

期望题目求助