牛客CSP-S提高组赛前集训营2 C-维护序列（分块）

$n<=1e5$,时限$6s$
脑阔癌。
真的就是大分块就完了。
考场往上一看6s时限，考虑分块，发现这个存答案很困难，卡空间，考虑分块

跨块询问的很简单，维护每种颜色($a_i$)在每个块内的最左位置和最右位置，然后就可以简单$O(\frac{n}{S})$计算跨块的答案了。
跨块的修改就是打区间覆盖标记。
块内的答案一看（可能？）就只能直接维护$O(S^2)$
额，我指的是每次修改散块（边界的块）的时候可以暴力$O(S^2)$
所以复杂度为$O(q\frac{n}{S}+q{S}^2+S^2\frac{n}{S})$
$q$与$n$同阶，令$S=O(n^{\frac{1}{3}})$，平衡复杂度为$O(n^{\frac{5}{3}})$。
所以貌似所有可以$n^2$的题都可以不用脑子的用这个方法写$n^{\frac{5}{3}}$
但是空间复杂度，因为我们需要对每个块的颜色离散化，需要建立引索，所以是$O(\frac{n^2}{S})$的，所以需要$S=200$左右，实测$S=100$没有$S=200$快。

出题人：可以$O(n^{\frac{3}{2}})$
对于两端的零散块，我们需要重建这两个块。举左侧块为例，设左侧块区间为 $[u,v]$，要修改 $[l,v]$ 之间的点为颜色 $x$。然后我们要更新块内的答案。注意到只有 $x$和 $[l,v]$中出现的颜色的答案会有改变，所以就用这些颜色去枚举块内其他颜色更新答案。这里均摊出现的颜色个数是 $\mathcal{O}(1)$的，然后每种颜色都需要枚举块内其它元素，因此单次操作复杂度仍然为均摊 $\mathcal{O}(\sqrt{n})$。
但是只快了$\frac{1}{4}$

$\mathrm{A}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{O}({\mathrm{n}}^{\frac{5}{3}})$

#include<bits/stdc++.h>
#define maxn 100005
#define S 200
#define B maxn/S+5
#define inf 0x3f3f3f3f
using namespace std;char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
void read(int &res){char ch;for(;!isdigit(ch=getc()););for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
int n,m,f,a[maxn],St[B],Ed[B],ib[maxn];
int L[B][S],R[B][S],Bans[B][S][S],inb[B][maxn],rnb[B][S],tp[B],tg[B],Pr[S];inline void reset(int b){int *in = inb[b] , *rn = rnb[b] , &tp=::tp[b] , *L = ::L[b] , *R = ::R[b];for(;tp;) memset(Bans[b][tp],0x3f,sizeof Bans[b][tp]),in[rn[tp--]] = 0;for(int i=St[b],r=Ed[b]+1;i!=r;i++){if(!in[a[i]]) rn[in[a[i]]=++tp]=a[i],L[tp]=R[tp]=i;int na = in[a[i]];R[na] = Pr[na] = i;for(int j=1,r=tp+1;j!=r;j++)Bans[b][j][na] = Bans[b][na][j] = min(Bans[b][na][j],i-Pr[j]);}for(int i=1,r=tp+1;i!=r;i++) Pr[i]=-inf;
}int main(){memset(Pr,-0x3f,sizeof Pr);memset(Bans,0x3f,sizeof Bans);read(n),read(m),read(f);for(int i=1;i<=n;i++) read(a[i]),ib[i]=((i-1)/S);for(int i=0;i<=ib[n];i++) St[i]=i*S+1,Ed[i]=min((i+1)*S,n),reset(i);for(int op,l,r,x,ans=0;m--;){read(op),read(l),read(r);if(f) l^=ans,r^=ans;if(op==1){read(x);if(f) x^=ans;int ll = ib[l] , lr = ib[r];if(tg[ll]){for(int i=St[ll],r=tg[ll],d=Ed[ll]+1;i!=d;i++) a[i]=r;tg[ll] = 0;}if(tg[lr]){for(int i=St[lr],r=tg[lr],d=Ed[lr]+1;i!=d;i++) a[i]=r;tg[lr] = 0;}if(ll == lr){for(int i=l,d=r+1;i!=d;i++) a[i] = x;reset(ll);}else{for(int i=l,d=Ed[ll]+1;i!=d;i++) a[i]=x;for(int i=St[lr],d=r+1;i!=d;i++) a[i]=x;reset(ll),reset(lr);for(int i=ll+1;i!=lr;i++) tg[i]=x;}}else{ans = inf;int prl=-inf,prr=-inf;for(int i=0,d=ib[n]+1;i!=d;i++)if(tg[i]){if(tg[i] == l){prl = Ed[i] , ans = min(ans , St[i]-prr);if(l == r){ ans=0; break; }}else if(tg[i] == r) prr = Ed[i] , ans = min(ans , St[i]-prl);}else{int na = inb[i][l] , nb = inb[i][r] , tl = prl , tr = prr;(na && nb) ? ans = min(ans , Bans[i][na][nb]) : 0;(na) ? ans = min(ans , L[i][na] - tr) , prl = R[i][na] : 0;(nb) ? ans = min(ans , L[i][nb] - tl) , prr = R[i][nb] : 0;}if(ans > n) ans = -1;printf("%d\n",ans);ans = max(ans , 0);}}
}