[DS记录]P6019 [Ynoi2010] Brodal queue
command_block
2021-07-05 23:24:18
**题意** ： 维护一个长为 $n$ 的序列 $A$ ，支持：
- 区间覆盖。
- 给出 $(l,r)$ ，查询有多少二元组 $(i,j)$ 满足 $l\leq i<j\leq r$ 且 $A_i=A_j$。
强制在线，$n,m\leq 10^5$ ，时限$\texttt{3s}$ ，空限$\texttt{1G}$。
------------
> 感谢 @mrsrz 的指导。
记 $c_i$ 为 $i$ 的出现次数，则贡献为 $\binom{c_i}{2}=\frac{c_i^2-c_i}{2}$ 。于是只需计算区间内每种数出现次数的平方和。
## 询问
对于纯色的块，当做散块元素进行特殊处理。
把贡献分为三类 ： “散块+纯块内部”，“散块+纯块 与 非纯块之间”，“非纯块 内部”。
散块+纯块的颜色种类数是 $O(\sqrt{n})$ 的。
- 散块+纯块 内部
容易用桶暴力计算。
- 散块+纯块 与 非纯块之间
记 $o_{i,j}=$ 前 $i$ 个（只考虑非纯块贡献）块内 $j$ 出现的次数。
记整块区间为 $[L,R]$。
对于元素 $j$ ，在散块+纯块中出现了 $c_j$ 次，则贡献为 $c_j(o_{R,j}-o_{L-1,j})$。
- 整块内部
记 $f(i,j)=\sum_xo_{i,x}o_{j,x}$ 。
块 $L\sim R$ 之中的贡献为 $f(R,R)-2f(L-1,R)+f(L-1,L-1)$ 。
## 修改
考虑如何维护 $o,f$。
对于散块，暴力重构。
对于整块，若不是纯色块，暴力重构，若是，则简单打标记。
不难发现，每次对块的暴力重构都会导致分界线减少至少 $1$ 个，每次修改只会增加 $O(1)$ 条分界线，于是总复杂度为 $O((n+m)\sqrt{n})$。
将一次修改描述为“将颜色 $x$ 在块 $k$ 中的出现次数增加了 $c$”。
这样的修改的总次数是 $O(n+m)$ 的。
每次在 $o$ 上重新做一次前缀和，复杂度为 $O\big((n+m)\sqrt{n}\big)$。
对于 $f$ ，考虑 $f(i,j)$ 。
- $i,j<k$ ：变化量为 $0$ 。
- $i<k\leq j$ ：变化量为 $o_{i,x}(o_{j,x}+c)-o_{i,x}o_{j,x}=o_{i,x}c$
- $k\leq i,j$ ：变化量为 $(o_{i,x}+c)(o_{j,x}+c)-o_{i,x}o_{j,x}=c^2+o_{i,x}c+o_{j,x}c$
对 $f(i,j)$ 的增量维护两个方向的差分。对于 $+o_{i,x}c$ ，用 $j$ 维度的划分处理，对于 $+o_{j,x}c$ 用 $i$ 维度的差分处理。
修改复杂度容易做到 $O(\sqrt{n})$。单点查询时只需将两个方向的贡献更新，也是 $O(\sqrt{n})$。
综上，时空复杂度 $O\big((n+m)\sqrt{n}\big)$。
引用题面的一句话（大雾） ：
> 实现真的很复杂，常数真的很大。
有点卡常，把数组维度交换一下提升空间连续性，很快啊，啪的一声就过了，最慢点 $\texttt{2.03s}$。
```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
#define uint unsigned int
#define ll long long
#define MaxN 200500
using namespace std;
int Bcnt;
ll f[392][392],s1[392][392],s2[392][392];
int o[MaxN][392];
void ladd1(int k){
ll now=0;
for (int i=k;i<=Bcnt;i++){
now+=s1[k][i];s1[k][i]=0;
f[k][i]+=now;
}
}
void ladd2(int k){
ll now=0;
for (int i=0;i<=k;i++){
now+=s2[k][i];s2[k][i]=0;
f[i][k]+=now;
}
}
void add(int k,int x,int c)
{
for (int i=0;i<k;i++)s1[i][k]+=o[x][i]*c;
for (int i=k;i<=Bcnt;i++){
s1[i][i]+=o[x][i]*c;
s2[i][k]+=(o[x][i]+c)*c;
}for (int i=k;i<=Bcnt;i++)o[x][i]+=c;
}
ll qry2(int l,int r){
if (l>r)return 0;
ladd1(l-1);ladd1(r);ladd2(l-1);ladd2(r);
return f[r][r]-2*f[l-1][r]+f[l-1][l-1];
}
int BS,e[MaxN],a[MaxN],tg[405];
void cov2(int l,int r,int x)
{
int k=l/BS,bl=k*BS,br=bl+BS;
if (tg[k]){
if (tg[k]==x)return ;
for (int i=bl;i<br;i++)a[i]=tg[k];
for (int i=l;i<=r;i++)a[i]=x;
add(k,x,r-l+1);add(k,tg[k],BS-(r-l+1));
tg[k]=0;
}else {
for (int i=l;i<=r;i++)e[a[i]]++;
for (int i=l;i<=r;i++){
if (e[a[i]]){add(k,a[i],-e[a[i]]);e[a[i]]=0;}
a[i]=x;
}add(k,x,r-l+1);
}
}
void del(int k){
int bl=k*BS,br=bl+BS;
for (int i=bl;i<br;i++)e[a[i]]++;
for (int i=bl;i<br;i++)
if (e[a[i]]){add(k,a[i],-e[a[i]]);e[a[i]]=0;}
}
void cov(int l,int r,int x)
{
if (l/BS==r/BS){cov2(l,r,x);return ;}
int tl=l/BS+1,tr=r/BS-1;
cov2(l,tl*BS-1,x);cov2(tr*BS+BS,r,x);
for (int i=tl;i<=tr;i++){
if (!tg[i])del(i);
tg[i]=x;
}
}
int st[MaxN];
void chk(int k){
if (!tg[k])return ;
int bl=k*BS,br=bl+BS;
for (int i=bl;i<br;i++)a[i]=tg[k];
}
ll qry(int l,int r)
{
int tn=0;ll ret=0;
if (l/BS==r/BS){
chk(l/BS);
for (int i=l;i<=r;i++)if (!e[a[i]]++)st[++tn]=a[i];
for (int i=1;i<=tn;i++)
{ret+=e[st[i]]*e[st[i]];e[st[i]]=0;}
return ret;
}chk(l/BS);chk(r/BS);
int tl=l/BS+1,tr=r/BS-1;
for (int i=l;i<tl*BS;i++)if (!e[a[i]]++)st[++tn]=a[i];
for (int i=tr*BS+BS;i<=r;i++)if (!e[a[i]]++)st[++tn]=a[i];
for (int i=tl;i<=tr;i++)if (tg[i]){
if (!e[tg[i]])st[++tn]=tg[i];
e[tg[i]]+=BS;
}
for (int i=1;i<=tn;i++){
ret+=1ll*e[st[i]]*(e[st[i]]+2*(o[st[i]][tr]-o[st[i]][tl-1]));
e[st[i]]=0;
}return ret+qry2(tl,tr);
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
BS=sqrt(n*1.33)+1;Bcnt=n/BS;
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
a[0]=1;for (int i=n+1;i<Bcnt*BS+BS;i++)a[i]=1;
for (int k=0;k<=Bcnt;k++){
int bl=k*BS,br=bl+BS;
for (int i=bl;i<br;i++)
for (int j=k;j<=Bcnt;j++)
o[a[i]][j]++;
}
for (int k=0;k<=Bcnt;k++){
int bl=k*BS,br=bl+BS;
for (int k2=k;k2<=Bcnt;k2++){
if (k>0)f[k][k2]=f[k-1][k2];
for (int i=bl;i<br;i++)
f[k][k2]+=o[a[i]][k2];
}
}
uint l,r,x,las=0;
for (int i=1,op;i<=m;i++){
scanf("%d%u%u",&op,&l,&r);
l^=las;r^=las;
if (op==1){
scanf("%u",&x);x^=las;
cov(l,r,x);
}else {
ll ans=(qry(l,r)-(r-l+1))/2;
las=ans;
printf("%lld\n",ans);
}
}return 0;
}
```