题解 P8527【[Ynoi2003] 樋口円香】
cyffff
·
·
题解
\text{Link}
题意
给出长为 n 的序列 a,b，b 序列初始为 0，m 次操作，每次给出 a 中的一个区间 [l,r] 与 L，执行 \forall i\in[l,r],b_{i+L-l}\gets b_{i+L-l}+a_i。
求出所有操作后的 b 序列。
## 思路
~~乐子一血。~~
对序列 $a$ 按照块长为 $B$ 分块，对于一次操作，若 $l,r$ 同块，则直接加，否则先对散块暴力，整块存下来暂不处理。
所有询问的散块处理完之后，处理整块。对于每个块 $[bL,bR]$，我们记录 $c_i$ 表示这个块加到 $b$ 序列中以 $i$ 开始的等长区间的次数，$d_i=a_{bL+i}(i\le bR-bL)$。令这个块对 $b_i$ 的贡献为 $res_i$，则有 $\displaystyle res_i=\sum_{j=1}^i c_jd_{i-j}$，可以卷积。
复杂度为 $O(mB+\dfrac{(n\log n+m)n}B)$，取 $B=O(\sqrt\dfrac{n^2\log n+nm}m)$ 得到最优复杂度 $O(n\sqrt{m\log n}+m\sqrt n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=131072,mod=998244353;
namespace Init{
int fac[N],ifac[N],inv[N],G[17][N];
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline void getG(){
for(int i=0;i<17;i++){
int *P=G[i],W=1<<i;
P[0]=1;
P[1]=qpow(3,(mod-1)/(1<<i+1));
const int tmp=P[1];
for(int j=2;j<W;j++)
P[j]=1ll*P[j-1]*tmp%mod;
}
}
inline void Prefix(int L){
fac[0]=1;
for(int i=1;i<=L;i++)
fac[i]=1ll*fac[i-1]*i%mod;
ifac[L]=qpow(fac[L],mod-2);
for(int i=L;i>=1;i--)
ifac[i-1]=1ll*ifac[i]*i%mod;
for(int i=1;i<=L;i++)
inv[i]=1ll*fac[i]*ifac[i-1]%mod;
}
}
using namespace Init;
namespace Poly{
int lim,rev[N];
int F[N],G[N],H[N];
inline void init(int n,int mode=1){
if(mode){
int l=0;
for(lim=1;lim<=n;lim<<=1)l++;
for(int i=1;i<lim;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
}else{
for(lim=1;lim<=n;lim<<=1);
}
}
inline void NTT(int *a,int T){
for(int i=0;i<lim;i++)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(int i=1,o=0;i<lim;i<<=1,o++){
const int *P=::G[o];
for(int j=0;j<lim;j+=(i<<1)){
int t1,t2;
for(int k=0;k<i;k++){
t1=a[j+k];
t2=1ll*P[k]*a[i+j+k]%mod;
a[j+k]=(t1+t2)%mod;
a[i+j+k]=(t1-t2+mod)%mod;
}
}
}
if(T==1) return ;
int Inv=qpow(lim,mod-2);
reverse(a+1,a+lim);
for(int i=0;i<lim;i++)
a[i]=1ll*a[i]*Inv%mod;
}
inline void Mul(int *a,int *b){
for(int i=0;i<lim;i++)
F[i]=b[i];
NTT(a,1),NTT(F,1);
for(int i=0;i<lim;i++)
a[i]=1ll*a[i]*F[i]%mod;
NTT(a,-1);
}
}
const int T=1e5+10,Q=1e6+10,sq=sqrt(1.0*T*T*log2(T)/Q+Q)*2;
int n,q,blk,a[T],b[T],c[N],d[N],bel[T],bl[T],br[T];
struct Query{
int l,bL,bR,L;
}que[Q];
inline void solve(int bL,int bR){
int D=bel[bL],len=bR-bL+1;
for(int i=0;i<=Poly::lim;i++)
c[i]=d[i]=0;
for(int i=1;i<=q;i++)
if(que[i].bL<=D&&D<=que[i].bR)
c[que[i].L+bL-que[i].l]++;
for(int i=1;i<=len;i++)
d[i-1]=a[bL+i-1];
Poly::Mul(c,d);
for(int i=1;i<=n;i++)
b[i]+=c[i];
}
int main(){
n=read();
getG(),Poly::init(n+2000);
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i+=sq){
blk++;
bl[blk]=i,br[blk]=min(i+sq-1,n);
for(int j=bl[blk];j<=br[blk];j++)
bel[j]=blk;
}
q=read();
for(int i=1;i<=q;i++){
int l=read(),r=read(),L=read();
int bL=bel[l],bR=bel[r];
if(bL==bR){
for(int j=l;j<=r;j++)
b[L+j-l]+=a[j];
}else{
for(int j=l;j<=br[bL];j++)
b[L+j-l]+=a[j];
for(int j=bl[bR];j<=r;j++)
b[L+j-l]+=a[j];
que[i]={l,bL+1,bR-1,L};
}
}
for(int i=1;i<=blk;i++)
solve(bl[i],br[i]);
for(int i=1;i<=n;i++)
write(b[i]),putc('\n');
flush();
}
```
再见 qwq~