C++(g++ 7.5.0) 解法, 执行用时: 250ms, 内存消耗: 11944K, 提交时间: 2023-01-18 20:17:38
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)
using namespace std;
const int N=2e5+5,mod=1e9+7;
char s[N];
int n,m,inv,a[N],b[N],s1[N],s2[N],s3[N],s4[N];
inline int lowbit(int x) {return x&-x;}
inline int read()
{
int x=0,f=1;
char c=getchar();
while(!isdigit(c))
{
f=c^'-'?1:-1;
c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
inline int power(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
inline void update(int* tr,int x,int val)
{
while(x<=n)
{
tr[x]=(tr[x]+val)%mod;
x+=lowbit(x);
}
}
inline int query(int* tr,int x)
{
int ans=0;
while(x)
{
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
signed main()
{
scanf("%lld%lld%lld%s",&n,&m,b+1,s+1);
b[0]=1;
for(int i=1;i<=n;++i)
{
a[i]=s[i]-'a'+1;
b[i+1]=b[i]*b[1]%mod;
inv=power(b[i],mod-2);
update(s1,i,a[i]*i%mod*inv%mod);
update(s2,i,a[i]*inv%mod);
update(s3,i,a[i]*i%mod);
update(s4,i,a[i]);
}
while(m--)
{
int opt=read();
if(opt)
{
char ch[2];
int i;
scanf("%lld%s",&i,ch);
inv=power(b[i],mod-2);
update(s1,i,-a[i]*i%mod*inv%mod);
update(s2,i,-a[i]*inv%mod);
update(s3,i,-a[i]*i%mod);
update(s4,i,-a[i]);
a[i]=ch[0]-'a'+1;
update(s1,i,a[i]*i%mod*inv%mod);
update(s2,i,a[i]*inv%mod);
update(s3,i,a[i]*i%mod);
update(s4,i,a[i]);
}
else
{
int l,r;
scanf("%lld%lld",&l,&r);
int ans=power(b[1]-1,mod-2);
ans=(ans<<1)%mod*power((r-l+1)*(r-l+2)%mod,mod-2)%mod;
int t1=query(s1,r)-query(s1,l-1),t2=query(s2,r)-query(s2,l-1),t3=query(s3,r)-query(s3,l-1),t4=query(s4,r)-query(s4,l-1);
ans=ans*(b[r+1]*(t1+(1-l)*t2%mod)%mod-(t3+(1-l)*t4)%mod)%mod;
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
}
}
C++14(g++5.4) 解法, 执行用时: 838ms, 内存消耗: 11896K, 提交时间: 2019-04-26 23:40:16
#include<bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
inline bool rd(int &X)
{
X=0;int w=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
X=w?-X:X; return 1;
}
char a[N],c;
int n,m,b,inv,p=1e9+7,now;
int invB[N],B[N],s[N],s1[N],s2[N],s3[N];
int POW(int a,int b=p-2,int ans=1){
for(;b;b>>=1,a=a*a%p)
if(b&1) ans=ans*a%p;
return ans;
}
void add(int *f,int x,int d){
for(;x<=n;x+=x&-x) f[x]=(f[x]+d)%p;
}
int ask(int *f,int x,int ans=0){
for(;x;x-=x&-x) ans=(ans+f[x])%p; return ans;
}
void change(int i,int d){
add(s,i,-a[i]),add(s1,i,-i*a[i]);
now=a[i]*invB[i]%p,add(s2,i,-now),add(s3,i,-i*now);
a[i]=d; add(s,i,a[i]),add(s1,i,i*a[i]);
now=a[i]*invB[i]%p,add(s2,i,now),add(s3,i,i*now);
}
void init()
{
inv=POW(b-1);
for(int i=B[0]=1;i<=n+1;i++)
a[i]-='a'-1,B[i]=B[i-1]*b%p,invB[i]=POW(B[i]);
for(int i=1;i<=n;i++)
add(s,i,a[i]),add(s1,i,i*a[i]);
for(int i=1;i<=n;i++)
now=a[i]*invB[i]%p,add(s2,i,now),add(s3,i,i*now);
}
int Ask(int l,int r){
int sum=ask(s,r)-ask(s,l-1),sum1=ask(s1,r)-ask(s1,l-1);
int sum2=ask(s2,r)-ask(s2,l-1),sum3=ask(s3,r)-ask(s3,l-1);
int v=((l-1)*sum-sum1+(sum3-(l-1)*sum2)%p*B[r+1])%p;
return (POW((r-l+1)*(r-l+2)/2%p)*v%p*inv%p+p)%p;
}
signed main()
{
rd(n);rd(m);rd(b);
scanf("%s",a+1); init();
while(m--){
int pd,l,r,x;rd(pd);
if(pd==0) rd(l),rd(r),printf("%lld\n",Ask(l,r));
if(pd==1) rd(x),scanf("%c",&c),change(x,c-'a'+1);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 434ms, 内存消耗: 11896K, 提交时间: 2020-03-24 20:35:00
#include<iostream>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const ll mod=1000000007;
const int maxn=2e5+50;
char s[maxn];
ll a[maxn];
int n,m;
ll qm(ll a,ll b)
{
ll r=1;
while(b)
{
if(b&1) r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
ll s1[maxn],s2[maxn],s3[maxn],s4[maxn];
void up(int i,ll x,ll t[])
{
while(i<=n)
{
t[i]=(t[i]+x)%mod;
i+=lowbit(i);
}
}
ll sum(int i,ll t[])
{
ll ans=0;
while(i)
{
ans+=t[i];
i-=lowbit(i);
}
return ans;
}
ll b[maxn];
int main()
{
scanf("%d%d%lld",&n,&m,&b[1]);
b[0]=1;
scanf("%s",s+1);
for(ll i=1;i<=n;++i)
{
a[i]=s[i]-'a'+1;
b[i+1]=b[i]*b[1]%mod;
ll inv=qm(b[i],mod-2);
up(i,a[i]*i%mod*inv%mod,s1);
up(i,a[i]*inv%mod,s2);
up(i,a[i]*i%mod,s3);
up(i,a[i],s4);
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==0)
{
ll l,r;
scanf("%lld%lld",&l,&r);
ll ans=qm(b[1]-1,mod-2);
ans=ans*2%mod*qm((r-l+1)*(r-l+2)%mod,mod-2)%mod;
ll t1=sum(r,s1)-sum(l-1,s1);
ll t2=sum(r,s2)-sum(l-1,s2);
ll t3=sum(r,s3)-sum(l-1,s3);
ll t4=sum(r,s4)-sum(l-1,s4);
ans=ans*(b[r+1]*(t1+(1-l)*t2%mod)%mod-(t3+(1-l)*t4)%mod)%mod;
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
else if(op==1)
{
char cc[2];
int i;
scanf("%d%s",&i,cc);
ll inv=qm(b[i],mod-2);
up(i,-a[i]*i%mod*inv%mod,s1);
up(i,-a[i]*inv%mod,s2);
up(i,-a[i]*i%mod,s3);
up(i,-a[i],s4);
a[i]=cc[0]-'a'+1;
up(i,a[i]*i%mod*inv%mod,s1);
up(i,a[i]*inv%mod,s2);
up(i,a[i]*i%mod,s3);
up(i,a[i],s4);
}
}
}