【Ynoi2010】Brodal queue
分块。
题目大意：
给定一个数列 $a_1,a_2,a_3,\ldots,a_n$，有两种操作：
- 给定 $l,r,x$，把 $a_{l..r}$ 改为 $x$。
- 给定 $l,r$，问有多少数对 $i,j$ 满足 $a_i=a_j$ 且 $l\leq i\lt j\leq r$。
题解：
序列分块。
分块，维护每种数的前缀出现次数，以及每种数的前缀出现次数的平方。
我们需要计算一段区间的每种数的出现次数的平方的和，考虑记录前缀的平方和，使用 $(a-b)^2=a^2-2ab+b^2$ 计算。
维护 $f(i,j)$ 表示 $\sum_x cnt(x,i)\cdot cnt(x,j)$。其中 $cnt(x,k)$ 表示颜色 $x$ 在前 $k$ 个块中的出现次数。
对 $f(i,j)$ 的修改，考虑块 $k$ 处的修改，设这种颜色在前 $i$ 块和前 $j$ 块中的出现次数为 $a,b$，在 块 $k$ 中的出现次数增加了 $x$。
对于 $i\leq k,k\leq j$ 的，他们的变化为 $a(b+x)-ab=ax$。我们对每个左端点为 $i$ 的 $f(i,\texttt*)$ 都记录变化量。
对于 $i<k,j<k$ 的，变化为 $0$。
对于 $k<i,k\leq j$ 的，变化为 $(a+x)(b+x)-ab=ax+bx+x^2$。我们对每个左端点为 $i$ 的 $f(i,\texttt{*})$ 都记录变化量 $ax$，对每个右端点为 $i$ 的 $f(\texttt{*},i)$ 都记录变化量 $bx+x^2$。
这部分可以使用差分的技巧做到 $O(1)$ 修改 $O(\sqrt n)$ 查询。
那么块 $i$ 与 $j$ 之间的所有数的出现次数的平方和，我们只需要知道前 $i$ 个块的平方和，前 $j$ 个块的平方和，$f(i,j)$ 的值，就可以求得。计算的复杂度为 $O(\sqrt n)$。
关于修改操作，边角暴力，中间的如果只有一个数则 $O(1)$ 修改，这会给这个块产生 $O(1)$ 个额外颜色段，否则 $O(\sqrt n)$ 删除块中的段贡献，总产生的颜色数为 $O(n+m)$。此时更新 $f$ 的复杂度为 $O((n+m)\sqrt n)$。
然后对于一个块，如果只有一种颜色，我们不把他计算到 $f$ 中而是在查询的时候计算这个块的贡献。
那么需要计算进 $f$ 的颜色段个数是 $O(n+m)$，所以每次对颜色段进行重新计算前缀信息，时间复杂度 $O((n+m)\sqrt n)$。
总时间复杂度 $O((n+m)\sqrt n)$，空间复杂度 $O(n \sqrt n)$。
Code：
#include<cstdio>
#include<cstring>
#include<cctype>
#define bel(x)(((x-1)/B)+1)
typedef unsigned long long LL;
const int B=1200,N=2e5+5,K=N/B+2,BK=B+2,__=B*(B-1)/2;
char*ss;
struct istream {
static const int size = 1 << 25;
char buf[size], *vin;
inline istream() {
fread(buf,1,size,stdin);
vin = buf - 1;
}
inline istream& operator >> (int & x) {
for(;isspace(*++vin););
for(x = *vin & 15;isdigit(*++vin);) x = x * 10 + (*vin & 15);
return * this;
}
} cin;
struct ostream {
static const int size = 1 << 22;
char buf[size], *vout;
unsigned map[10000];
inline ostream() {
for(int i = 0;i < 10000;++i)
map[i] = i % 10 + 48 << 24 | i / 10 % 10 + 48 << 16 | i / 100 % 10 + 48 << 8 | i / 1000 + 48;
vout = buf + size;
}
inline ~ ostream()
{ fwrite(vout,1,buf + size - vout,stdout); }
inline ostream& operator << (unsigned long long x) {
for(;x >= 10000;x /= 10000) *--(unsigned*&)vout = map[x % 10000];
do *--vout = x % 10 + 48; while(x /= 10);
return * this;
}
inline ostream& operator << (char x) {
*--vout = x;
return * this;
}
}cout;
int pre[N][K],a[N],n,m,blocks,L[K],R[K],dt[N];
int tag[K];
LL sum[K],f[K][K];
unsigned long long _s[N];
LL A1[K][K],A2[K][K];
int sta[BK*3],top;
inline LL sqr(int x){return(LL)x*x;}
void init(){
static bool vis[N];
blocks=bel(n);
for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*B;R[blocks]=n;
for(int i=1;i<=blocks;++i){
for(int j=1;j<=n;++j)pre[j][i]=pre[j][i-1];
top=0;
for(int j=L[i];j<=R[i];++j){
const int&x=a[j];
++pre[x][i];
if(!vis[x])vis[x]=1,sta[++top]=x;
}
sum[i]=sum[i-1];
for(int j=1;j<=top;++j)
sum[i]+=sqr(pre[sta[j]][i])-sqr(pre[sta[j]][i-1]);
for(int j=1;j<=n;++j)
f[i][i]+=(LL)pre[j][i-1]*pre[j][i];
for(int p=1;p<i;++p){
LL&s=f[p][i];
s=f[p][i-1];
for(int j=1;j<=top;++j)
s+=(LL)pre[sta[j]][p-1]*(pre[sta[j]][i]-pre[sta[j]][i-1]);
}
for(int j=1;j<=top;++j)vis[sta[j]]=0;
}
}
inline void Modify_color(int dlt,int id,int x){
int*P=pre[x];
for(int i=1;i<=blocks;++i)A1[id][i]+=(LL)dlt*P[i-1];
for(int i=id;i<=blocks;++i)A2[id][i]+=(LL)dlt*(P[i]+dlt),sum[i]+=sqr(P[i]+dlt)-sqr(P[i]),P[i]+=dlt;
}
inline void modify_all(int id,int x){
if(!tag[id]){
top=0;
for(int i=L[id];i<=R[id];++i)
if(!dt[a[i]]++)sta[++top]=a[i];
for(int i=1;i<=top;++i)Modify_color(-dt[sta[i]],id,sta[i]),dt[sta[i]]=0;;
}
tag[id]=x;
}
void modify(int l,int r,int x){
const int id=bel(l);
if(tag[id]){
for(int i=L[id];i<=R[id];++i)a[i]=tag[id];
Modify_color(R[id]-L[id]-r+l,id,tag[id]);
Modify_color(r-l+1,id,x);
tag[id]=0;
for(int i=l;i<=r;++i)a[i]=x;
}else{
top=0;
for(int i=l;i<=r;++i){
if(!dt[a[i]]++)sta[++top]=a[i];
a[i]=x;
}
for(int i=1;i<=top;++i)Modify_color(-dt[sta[i]],id,sta[i]);
Modify_color(r-l+1,id,x);
for(int i=1;i<=top;++i)dt[sta[i]]=0;
}
}
inline int get(int x){return tag[bel(x)]?tag[bel(x)]:a[x];}
int solve(int l,int r){
int ret=0;
for(int i=l;i<=r;++i)ret+=dt[get(i)]++;
for(int i=l;i<=r;++i)dt[get(i)]=0;
return ret;
}
LL F(int l,int r){
LL ret=f[l][r];
for(int i=1;i<=r;++i)ret+=A1[i][l];
for(int i=1;i<l;++i)ret+=A2[i][r];
return ret;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
init();
unsigned lst=0;
for(int T=1;T<=m;++T){
int op,l,r;
cin>>op>>l>>r;
l^=lst,r^=lst;
if(op==1){
_s[T]=~0;
int x;
cin>>x;
x^=lst;
const int bL=bel(l),bR=bel(r);
if(bL==bR)modify(l,r,x);else{
modify(l,R[bL],x),modify(L[bR],r,x);
for(int i=bL+1;i<bR;++i)
modify_all(i,x);
}
}else{
LL ans=0;
if(r-l+1<=3*B)ans=solve(l,r);else{
const int bL=bel(l),bR=bel(r);
ans=sum[bR-1]+sum[bL]-2*F(bL+1,bR-1);
for(int i=bL+1;i<bR;++i)ans-=!tag[i]*B;
ans>>=1,top=0;
for(int i=R[bL];i>=l;--i){
const int x=get(i);
if(!dt[x])sta[++top]=x;
++dt[x];
}
for(int i=L[bR];i<=r;++i){
const int x=get(i);
if(!dt[x])sta[++top]=x;
++dt[x];
}
for(int i=1;i<=top;++i)
ans+=(LL)dt[sta[i]]*(pre[sta[i]][bR-1]-pre[sta[i]][bL])+(LL)dt[sta[i]]*(dt[sta[i]]-1)/2;
for(int i=bL+1;i<bR;++i)
if(tag[i])ans+=((LL)(dt[tag[i]]+pre[tag[i]][bR-1]-pre[tag[i]][bL])*B)+__,dt[tag[i]]+=B;
for(int i=1;i<=top;++i)dt[sta[i]]=0;
for(int i=bL+1;i<bR;++i)dt[tag[i]]=0;
}
_s[T]=(unsigned long long)ans;
lst=ans;
}
}
for(int i=m;i;--i)if(~_s[i])cout<<'\n'<<_s[i];
return 0;
}