[DS记录]P7601 [THUPC2021] 区间本质不同逆序对
command_block
2021-06-03 22:33:46
**题意** ： 给定一个长为 $n$ 的序列 $a$。
有 $m$ 次询问，每次询问给定一个区间 $[l,r]$，求 $\Big|\big\{(a_i,a_j) : l\le i<j\le r \wedge a_i>a_j\big\}\Big|$。
$n\leq 10^5,m\leq 5\times 10^5$ ，时限$\texttt{4s}$ ，空限 $\texttt{512Mb}$。
- [P7448 [Ynoi2007] rdiq](https://www.luogu.com.cn/problem/P7448) ：时限$\texttt{3s}$ ，空限 $\texttt{128Mb}$。
------------
考虑莫队。
先考虑左端点移动的贡献。右端点在将序列和值域同时翻转后可以转化为左端点。
记 $nxt_i$ 是 $a_i$ 下一次出现的位置。
当 $l$ 减小至 $l'$ ： $[l,r],[l-1,r],[l-2,r],...,[l',r]$
考虑新增的本质不同逆序对。
当 $l+1$ 移动到 $l$ 时，$a_{l+1\sim r}$ 中 $<a_l$ 的 $a_j$ 会构成逆序对 $(a_l,a_j)$。（当然，不保证全是新的）
而对于所有 $nxt_l<j$ 的 $j$ ，$(a_l,a_j)$ 都必然与 $(a_{nxt_l},a_j)$ 重复。
对于所有 $j\leq nxt_l$ 的 $j$ ，若 $a_j$ 在 $a_{nxt_l+1,r}$ 中出现过，则重复，否则不会重复。
也就是说，我们要计算的是 ： 在 $[l+1,nxt_l]$ 中出现过，但在 $[nxt_l+1,r]$ 中没出现过，且 $<a_l$ 的数的种类数。
记 $f(l,r)=(l,r]$ 内 $<a_{l}$ 的数的种类数。不难发现上面要计算的东西 $=f(l,r)-f(nxt_l,r)$
我们每次需要计算的一组 $f$ 的 $r$ 是相同的。
问题转化为了 $O(n\sqrt{m})$ 个 $f$ 的计算。
将 $a_i$ 看做三维平面上的点 $p_i=(i,a_i,pre_i)$ ，则有 ：
$$f(l,r)=\sum\limits_{i}[l< p_i.x\leq r][p_i.y\leq a_l][p_i.z\leq l]$$
可以先预处理 $S(l)=\sum\limits_{i}[p_i.x\leq l][p_i.y\leq a_l][p_i.z\leq l]$ ，这样上式变为 ：
$$f(l,r)=-S(l)+\sum\limits_{i}[p_i.x\leq r][p_i.y\leq a_l][p_i.z\leq l]$$
这是三维偏序。
先将 $f,p$ 按照 $r$ 排序，逐次加入，消去了 $[p.x\leq r]$ 的约束。
然后我们需要一个维护动态二维偏序的数据结构。
将 $n\times n$ 的二维平面分成 $\sqrt{n}$ 个 $n^{0.75}\times n^{0.75}$ 的块（称作大块）。对这些块维护二维前缀和。（红色）
将每个“大块”（按两个方向）分成 $n^{0.25}$ 个 $n^{0.5}\times n^{0.75}$ 的块（称作“中块”）。对每一行 / 列“大块”维护内部 $n^{0.5}$ 个“中块”的二维前缀和。（蓝色）
又将每个 “大块” 分成 $n^{0.5}$ 个 $n^{0.5}\times n^{0.5}$ 的块（称作“小块”）。对每个“大块”维护内部“小块”的二维前缀和。（绿色）
然后我们剩下的就是 ： 询问两条边界附近宽度不超过 $n^{0.5}$ 的区域。（黄色）
对于黄色部分，我们不再维护前缀和，转而考虑每个点的贡献。
点在某个询问的黄色部分的充要条件 ： 该询问覆盖了该点，但没有完全覆盖该点所在的小块。
注意到询问的端点形如 $(a_l,l)$ ，只有 $O(n)$ 个本质不同的端点，且符合上述条件的端点只有 $O(\sqrt{n})$ 个（需要对 $a$ 进行重标号，避免重复），于是可以暴力枚举并进行贡献。
时间复杂度 $O(n(\sqrt{m}+\sqrt{n}))$ ，空间复杂度 $O(n+m)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define clr(x) memset(x,0,sizeof(x))
#define pb emplace_back
#define ll long long
#define MaxN 100500
#define MaxM 500500
using namespace std;
int n;
struct SumDS_1D
{
int t[MaxN];
#define lbit(x) (x&-x)
void add(int p)
{while(p<=n){t[p]++;p+=lbit(p);}}
int qry(int p){
int ret=0;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
}T1;
struct SumDS_2D
{
int s[28][28],s2[28][405],s3[405][28],s4[405][405],s5[MaxN],tot;
struct Point{int x,y,p;}sp[MaxN];
vector<Point> px[405],py[405];
void ins(int x,int y,int i){
sp[i]=(Point){x,y,i};
px[x>>8].pb(sp[i]);py[y>>8].pb(sp[i]);
}
void add(int x,int y)
{
int bx1=x>>12,by1=y>>12,bx2=x>>8,by2=y>>8;
for (int i=bx1+1;(i<<12)<=n;i++)
for (int j=by1+1;(j<<12)<=n;j++)
s[i][j]++;
int bxr2=(bx1+1)<<4,byr2=(by1+1)<<4;
for (int i=bx1+1;(i<<12)<=n;i++)
for (int j=by2+1;j<byr2;j++)
s2[i][j]++;
for (int i=bx2+1;i<bxr2;i++)
for (int j=by1+1;(j<<12)<=n;j++)
s3[i][j]++;
for (int i=bx2+1;i<bxr2;i++)
for (int j=by2+1;j<byr2;j++)
s4[i][j]++;
vector<Point> &tx=px[bx2],&ty=py[by2];
for (int i=0;i<tx.size();i++)
if (x<=tx[i].x&&y<=tx[i].y)s5[tx[i].p]++;
for (int i=0;i<ty.size();i++)
if (x<=ty[i].x&&y<=ty[i].y&&(ty[i].x>>8)!=bx2)s5[ty[i].p]++;
}
int qry(int i){
int x=sp[i].x,y=sp[i].y;
return s[x>>12][y>>12]+s2[x>>12][y>>8]+s3[x>>8][y>>12]+s4[x>>8][y>>8]+s5[i];
}
void clear(){
clr(s);clr(s2);clr(s3);clr(s4);clr(s5);
for (int i=0;(i<<8)<=n;i++){px[i].clear();py[i].clear();}
}
}T;
struct Data{int l,r,p;};
vector<Data> b2[MaxN];
int pre[MaxN],nxt[MaxN],a[MaxN],cnt[MaxN],o[MaxN];
ll s[MaxN],ans[MaxM];
void calc()
{
for (int i=1;i<=n;i++){T1.add(a[i]);s[i]=T1.qry(a[i]-1);}
for (int i=1;i<=n;i++)cnt[a[i]]++;
for (int i=1;i<=n;i++)o[i]=cnt[i]+=cnt[i-1];
for (int i=1;i<=n;i++)T.ins(--o[a[i]],i,i);
for (int i=1;i<=n;i++){
T.add(cnt[a[i]],pre[i]);
for (int j=0;j<b2[i].size();j++){
Data now=b2[i][j];
for (int k=now.l;k<=now.r;k++){
int sav=(-s[k]+T.qry(k))
-(nxt[k]<=i ? (-s[nxt[k]]+T.qry(nxt[k])) : 0 );
if (now.p<0)ans[-now.p]-=sav;
else ans[now.p]+=sav;
}
}b2[i].clear();
}T.clear();clr(T1.t);
for (int i=1;i<=n;i++)cnt[i]=0;
}
Data b[MaxM];int BS;
bool cmp(const Data &A,const Data &B)
{return A.l/BS==B.l/BS ? (A.l/BS&1 ? A.r<B.r : A.r>B.r) : A.l<B.l;}
int m,las[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
pre[i]=las[a[i]];
las[a[i]]=nxt[pre[i]]=i;
}for (int i=1;i<=n;i++)if (!nxt[i])nxt[i]=n+1;
scanf("%d",&m);
for (int i=1;i<=m;i++){
scanf("%d%d",&b[i].l,&b[i].r);
b[i].p=i;
}
BS=n/sqrt(m)+1;
sort(b+1,b+m+1,cmp);
int l=1,r=0;
for (int i=1;i<=m;i++){
if (b[i].l<l)b2[r].pb((Data){b[i].l,l-1,b[i].p});
if (r<b[i].r)r=b[i].r;
if(l<b[i].l)b2[r].pb((Data){l,b[i].l-1,-b[i].p});
if (b[i].r<r)r=b[i].r;
l=b[i].l;
}
calc();
reverse(a+1,a+n+1);
reverse(nxt+1,nxt+n+1);
reverse(pre+1,pre+n+1);
#define rev(x) x=n-x+1
for (int i=1;i<=n;i++){swap(nxt[i],pre[i]);rev(nxt[i]);rev(pre[i]);rev(a[i]);}
for (int i=1;i<=m;i++){swap(b[i].l,b[i].r);rev(b[i].l);rev(b[i].r);}
l=n+1;r=n;
for (int i=1;i<=m;i++){
if (r<b[i].r)r=b[i].r;
if (b[i].l<l)b2[r].pb((Data){b[i].l,l-1,b[i].p});
if (b[i].r<r)r=b[i].r;
if(l<b[i].l)b2[r].pb((Data){l,b[i].l-1,-b[i].p});l=b[i].l;
l=b[i].l;
}
calc();
for (int i=1;i<=m;i++)ans[b[i].p]+=ans[b[i-1].p];
for (int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
```