科学
Source：CF461C Appleman and a Sheet of Paper，*2200。
注意到对于 \(p\le \lfloor \frac {now}{2}\rfloor\)，直接暴力维护的复杂度是对的。
而对于其 \(>\) 的情况，翻转右半边同样是对的。
故维护翻转的标记，暴力做并且维护区间和即可，时间复杂度 \(O(n\log n)\)。
Code
const int N=2e5+5;
int sum[N*4],add[N*4];
void build(int p,int l,int r) {
if(l==r) return sum[p]=1,void();
int mid=(l+r)>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
sum[p]=sum[p*2]+sum[p*2+1];
}
void update(int p,int l,int r,int x,int v) {
if(l==r) {sum[p]+=v;return;}
int mid=(l+r)>>1;
if(x<=mid) update(p*2,l,mid,x,v);
else update(p*2+1,mid+1,r,x,v);
sum[p]=sum[p*2]+sum[p*2+1];
}
int query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return sum[p];
int mid=(l+r)>>1,ret=0;
if(x<=mid) ret+=query(p*2,l,mid,x,y);
if(y>mid) ret+=query(p*2+1,mid+1,r,x,y);
return ret;
}
int main() {
int n,q;scanf("%d %d",&n,&q);
build(1,1,n);int st=1,ed=n,OP=0;
FOR(TTT,1,q) {
int op,x,y,len=ed-st+1;
scanf("%d %d",&op,&x);
if(op==2) {
scanf("%d",&y);
int l=x,r=y-1;
if(OP) l=len-l-1,r=len-r-1,swap(l,r);
printf("%d\n",query(1,1,n,l+st,r+st));
}
else {
int mid=(ed-st+1)/2;
if(x<=mid) {
if(!OP) {
int r=st+2*x-1,z;
FOR(i,1,x) z=query(1,1,n,st+i-1,st+i-1),update(1,1,n,r-i+1,z);
st=st+x;
}
else {
int l=ed-2*x+1,z;
FOR(i,1,x) z=query(1,1,n,ed-i+1,ed-i+1),update(1,1,n,l+i-1,z);
ed=ed-x;
}
}
else {
if(!OP) {
OP^=1;
x=ed-st+1-x;
int l=ed-2*x+1,z;
FOR(i,1,x) z=query(1,1,n,ed-i+1,ed-i+1),update(1,1,n,l+i-1,z);
ed=ed-x;
}
else {
OP^=1;
x=ed-st+1-x;
int r=st+2*x-1,z;
FOR(i,1,x) z=query(1,1,n,st+i-1,st+i-1),update(1,1,n,r-i+1,z);
st=st+x;
}
}
}
}
}
勇者
Source：AT code_festival_2017_quala_f Squeezing Slimes，*3091。
AT *3000+，转手放 T2。
注意到对于每一个 \(a_i\)，其被合出来的步数下界是 \(\lfloor \log_2 a_i\rfloor\)，若不为二的次幂则还需要一次，并且一定可以构造得到这个步数下界。
若每个数之间独立，那答案显然是 \(\sum\lfloor \log_2 a_i\rfloor\)，但是两个数之间可以合在一起处理，考虑这种情况。
设前面可以过来 \(k\) 个操作，现在要做 \(b_i=\lfloor \log_2 a_i\rfloor\) 次，考虑分类讨论，若 \(k<b_i\)，则必须补齐 \(b_i-k\) 个操作，若 \(k>b_i\) 则过渡过来的只有 \(b_i\) 个操作。
注意特判不为二的次幂的情况，时间复杂度 \(O(n)\)。
Code
int main() {
int n;
ll cur=0,ans=0;
n=read();
FOR(i,1,n) {
int x=read();
int w=__lg(x),fl=0;
if((1<<w)!=x) fl=1;
if(cur<w) ans+=w-cur;
if(cur>w) fl=0;
cur=w;
if(fl) ans++,cur++;
}
printf("%lld\n",ans);
}
输出
Source：CF1418G Three Occurrences，*2500。
枚举右端点 \(r\)，考虑维护当前可能为答案为 \(l\)。
分开考虑每一种颜色，求出每一种颜色的合法右端点集合 \(S\)，那么所有集合 \(S\) 的交即为答案。
下记 \(pre_{x,c,k}\) 表示在 \(x\) 前面的第 \(k\) 个颜色为 \(c\) 的位置。
对颜色是否为 \(col_r\) 分类讨论，
- 颜色为 \(col_r\)，那么必须得包含 \(k\) 个这个颜色，故合法集合为 \((pre_{r,col_r,k+1},pre_{r,col_r,k}]\)。
- 颜色不为 \(col_r\)，既可以包含 \(k\) 个，也可以都不包含，故合法集合为上面的加上 \((pre_{r,x,1},r]\)。
注意到一种颜色的合法集合不相交，可以直接区间加维护最大值及最大值个数，做到 \(O(n\log n)\)。
Code
const int N=5e5+5;
int add[N*4];
struct node {int ma,cnt;} tr[N*4];
node operator + (node a,node b) {
node ret;
ret.ma=max(a.ma,b.ma),ret.cnt=0;
if(ret.ma==a.ma) ret.cnt+=a.cnt;
if(ret.ma==b.ma) ret.cnt+=b.cnt;
return ret;
}
void pushadd(int p,int v) {add[p]+=v,tr[p].ma+=v;}
void pushdown(int p) {
if(add[p]) {
pushadd(p*2,add[p]),pushadd(p*2+1,add[p]);
add[p]=0;
}
}
void build(int p,int l,int r) {
if(l==r) {tr[p].cnt=1;return;}
int mid=(l+r)>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
tr[p]=tr[p*2]+tr[p*2+1];
}
void update(int p,int l,int r,int x,int y,int v) {
if(x>y) return;
if(x<=l&&r<=y) return pushadd(p,v);
int mid=(l+r)>>1;pushdown(p);
if(x<=mid) update(p*2,l,mid,x,y,v);
if(y>mid) update(p*2+1,mid+1,r,x,y,v);
tr[p]=tr[p*2]+tr[p*2+1];
}
int id[N],col[N],pre[N],nxt[N],tmp[N],cur[N],colcnt;
int main() {
int n,K;scanf("%d",&n);K=3;
FOR(i,1,n) {
scanf("%d",&col[i]);
id[i]=++tmp[col[i]];
if(tmp[col[i]]==1) cur[col[i]]=i,colcnt++;
}
build(1,1,n);
FOR(i,1,n) tmp[i]=0;
FOR(i,1,n) pre[i]=tmp[col[i]],tmp[col[i]]=i;
FOR(i,1,n) tmp[i]=0;
ROF(i,n,1) nxt[i]=tmp[col[i]],tmp[col[i]]=i;
ll ans=0;
FOR(i,1,n) {
update(1,1,n,i,i,colcnt);
update(1,1,n,pre[i]+1,i,-1);
if(id[i]==K) update(1,1,n,1,cur[col[i]],1);
if(id[i]>K) {
int &pk=cur[col[i]];
update(1,1,n,pre[pk]+1,pk,-1);
update(1,1,n,pk+1,nxt[pk],1);
pk=nxt[pk];
}
if(tr[1].ma==colcnt) ans+=tr[1].cnt;
}
printf("%lld\n",ans);
}
咒术
Source：「BJOI2019」勘破神机。
先做 \(m=2\)。
注意到 \(m=2\) 时答案等价于 \(\sum_{i=l}^r \binom{f_i}{k}\)，\(f_i\) 表示斐波那契数。
考虑推式子：
\[\begin{aligned} \sum_{n=l}^r \binom{f_n}{k} & = \sum_{n=l}^{r}\frac{f_n!}{(f_n-k)!k!}\\ & = \frac{1}{k!}\sum_{n=l}^r f_{n}^{\underline{k}}\\ & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\\i \end{bmatrix} f_n^i\\ \end{aligned} \]考虑使用 \(f_k\) 的通项公式：
\[f_n=\frac{5+\sqrt{5}}{10}(\frac{1+\sqrt{5}}{10})^n+\frac{5-\sqrt{5}}{10}(\frac{1-\sqrt{5}}{10})^n \]记 \(f_n=A\alpha^n+B\beta^n\)，带回上式：
\[\begin{aligned} \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\\i \end{bmatrix} f_n^i & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\\i \end{bmatrix} (A\alpha^n+B\beta^n)^i\\ & = \frac{1}{k!}\sum_{n=l}^r \sum_{i=0}^k (-1)^{k-i} \begin{bmatrix} k\\i \end{bmatrix} \sum_{j=0}^i\binom{i}{j}A^j\alpha^{nj}B^{i-j}\beta^{n(i-j)}\\ & = \frac{1}{k!}\sum_{i=0}^k(-1)^{k-i} \begin{bmatrix} k\\i \end{bmatrix} \sum_{j=0}^i\binom{i}{j} A^iB^{i-j}\sum_{n=l}^r(\alpha^j\beta^{i-j})^n \end{aligned} \]最后一项是一个等比数列求和，直接做就是 \(O(k^2\log r)\) 的，注意特判公比为 \(1\) 的情况。
注意到 \(5\) 在模 \(998244353\) 下不存在二次剩余，故需要手写复数类扩域。
接下来考虑 \(m=3\)，实际上也是一个求递推式的过程，这里的递推式是 \(g_i=4g_{i-1}-g_{i-2}\)，同样可以用特征方程求出类似 \(A\alpha^n+B\beta^n\) 的形式，做到同样复杂度。
上述懒了省略了若干细节，可以参考代码。
Code
const int N=505,mod=998244353;
int inc(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
void Inc(int &x,int y) {x+=y;if(x>=mod) x-=mod;}
int dec(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
void Dec(int &x,int y) {x+=y;if(x<0) x-=mod;}
int mul(int x,int y) {return 1ll*x*y%mod;}
void Mul(int &x,int y) {x=1ll*x*y%mod;}
int fpow(int x,ll y) {
int ret=1;
for(;y;y>>=1) {
if(y&1) Mul(ret,x);
Mul(x,x);
}
return ret;
}
int inv(int x) {return fpow(x,mod-2);}
int V,C[N][N],S[N][N],fac[N],ifac[N];
struct Complex {
int x,y;
Complex operator + (const Complex &a) const {return {inc(x,a.x),inc(y,a.y)};}
Complex operator - (const Complex &a) const {return {dec(x,a.x),dec(y,a.y)};}
Complex operator * (const Complex &a) const {return {inc(mul(x,a.x),mul(V,mul(y,a.y))),inc(mul(x,a.y),mul(y,a.x))};}
Complex operator * (const int &a) const {return {mul(x,a),mul(y,a)};}
} A,B,alph,bt;
Complex fpow(Complex x,ll y) {
Complex ret={1,0};
for(;y;y>>=1) {
if(y&1) ret=ret*x;
x=x*x;
}
return ret;
}
Complex inv(Complex a) {
int tmp=dec(mul(a.x,a.x),mul(V,mul(a.y,a.y)));tmp=inv(tmp);return {mul(a.x,tmp),mod-mul(a.y,tmp)};
}
int main() {
int T=read(),m=read();
if(m==2) V=5;
else V=3;
S[1][1]=1;
FOR(i,0,501) C[i][0]=1;
FOR(i,1,501) FOR(j,1,i) C[i][j]=inc(C[i-1][j-1],C[i-1][j]);
FOR(i,2,501) FOR(j,1,i) S[i][j]=dec(S[i-1][j-1],mul(i-1,S[i-1][j]));
fac[0]=1,ifac[0]=1;
FOR(i,1,501) fac[i]=mul(fac[i-1],i),ifac[i]=inv(fac[i]);
if(m==2) A={inv(2),inv(10)},B={inv(2),mod-inv(10)},alph={inv(2),inv(2)},bt={inv(2),mod-inv(2)};
else A={inv(2),inv(6)},B={inv(2),mod-inv(6)},alph={2,1},bt={2,mod-1};
while(T--) {
ll l=read(),r=read();int k=read();
ll len=r-l+1;
int ans=0;
if(m==3) l=(l+1)>>1,r>>=1;
ll L=r-l+1;
FOR(i,1,k) {
Complex tmp={0,0};
FOR(j,0,i) {
Complex a=fpow(A,j)*fpow(B,i-j),b=fpow(alph,j)*fpow(bt,i-j);
Complex c=(fpow(b,L+1)-b)*inv(b-(Complex){1,0});
if(b.x==1&&b.y==0) c=b*(L%mod);
tmp=tmp+a*c*C[i][j]*fpow(b,l-1);
}
Inc(ans,mul(S[k][i],tmp.x));
}
printf("%d\n",mul(ans,mul(inv(len%mod),ifac[k])));
}
}