题解 P7334【[JRKSJ R1] 吊打】
cyffff
·
·
题解
\text{Link}
题意
给出 n,m 表示长为 n 的序列 a，m 次操作，支持两种操作：
1 l r，对所有 i\in[l,r]，将 a_i\gets\left\lfloor\sqrt{a_i}\right\rfloor。2 l r，对所有 i\in[l,r]，将 a_i\gets{a_i}^2。
最后输出 \displaystyle\left(\sum_{i=1}^na_i\right)\bmod 998244353。
时间 1s，n,m\le 2\times10^5。
思路
发现区间开方直接拍一个分块上去，参考 P4145。
这里不好维护原数，考虑维护 $i$ 位置上的数被平方的次数 $s_i$。
操作 $1$ 为区间加。考虑操作 $2$，散块暴力，整块维护 $s_i$ 最小值。若 $\min s_i\ge1$，直接打区间减 $\text{tag}$，否则若 $\max a_i= 1$，跳过，否则暴力开方或将 $s_i$ 减一。
由势能分析，我们知道这部分是 $O(n\sqrt {n\log\log w})$ 的。
求出 $s_i$ 后考虑得出答案，用欧拉定理降幂，预处理一下 $2^{k}\bmod998244352$,即可在 $O(\log p)$ 时间内求出 $a_i^{2^{s_i}}$，总时间复杂度为 $O(n\sqrt{n\log\log w})$，期望得分 $100$ 分。
我没写代码，$\text{dqstz}$ 写了：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mx=2e5+5;
const int mod=998244353;
int a[mx];
int bl[mx],fl[mx],fr[mx];
int s[mx],tag[mx],mn[mx],os[mx];
int pow2[mx];
int n,b,ks;
void init()
{
int i,j,k,mx;
b=sqrt(n);
for(i=1;i-1+b<=n;i+=b)
fl[++ks]=i,fr[ks]=i-1+b;
if(i<=n)
fl[++ks]=i,fr[ks]=n;
for(i=1;i<=ks;i++)
for(j=fl[i];j<=fr[i];j++)
bl[j]=i;
}
int qpow(int a,int p,int mod)
{
if(p==0) return 1;
if(p==1) return a;
long long t=qpow(a,p/2,mod);
return t*t%mod*qpow(a,p%2,mod)%mod;
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
void cg(int x)
{
mn[x]=2e9;
for(int i=fl[x];i<=fr[x];i++)
mn[x]=min(mn[x],s[i]+tag[x]);
}
void zk(int x)
{
for(int i=fl[x];i<=fr[x];i++)
s[i]+=tag[x];
tag[x]=0;
}
void add(int l,int r)
{
if(bl[l]==bl[r])
{
zk(bl[l]);
for(;l<=r;l++)
s[l]++;
cg(bl[l-1]);
return;
}
add(l,fr[bl[l]]),add(fl[bl[r]],r);
int i;
for(i=bl[l]+1;i<bl[r];i++)
tag[i]++,mn[i]++;
}
void sqrt(int l,int r)
{
if(bl[l]==bl[r])
{
zk(bl[l]);
for(;l<=r;l++)
{
if(a[l]==1) continue;
if(s[l]==0)
{
a[l]=sqrt(a[l]);
os[bl[l]]+=a[l]==1;
}
else s[l]--;
}
cg(bl[l-1]);
return;
}
sqrt(l,fr[bl[l]]),sqrt(fl[bl[r]],r);
for(int i=bl[l]+1;i<bl[r];i++)
{
if(os[i]==fr[i]-fl[i]+1) continue;
if(mn[i]==0)
sqrt(fl[i],fr[i]);
else
mn[i]--,tag[i]--;
}
}
int main()
{
int m,i,opt,l,r,sum=0,wz=2e9,qwq;
n=read(),m=read();
init();
pow2[0]=1;
for(i=1;i<=n;i++)
a[i]=read();
for(i=1;i<=m;i++)
{
pow2[i]=pow2[i-1]*2;
if(pow2[i]>=mod-1&&wz==2e9) wz=i;
pow2[i]%=mod-1;
}
while(m--)
{
opt=read(),l=read(),r=read();
if(opt==1) sqrt(l,r);
else add(l,r);
}
for(i=1;i<=ks;i++)
zk(i);
for(i=1;i<=n;i++)
{
if(a[i]==1)
{
sum=(sum+1)%mod;
continue;
}
qwq=pow2[s[i]];
if(s[i]>=wz) qwq+=mod-1;
sum=(sum+qpow(a[i],qwq,mod))%mod;
}
cout<<sum%mod;
}
```
再见 qwq~