题解:P7448 [Ynoi2007] rdiq
更好的阅读体验
十分具有技巧性,个人认为最终的做法还是非常令人惊叹的。书接上回。
我们先来研发一个数据结构,需要支持在一个
保证插入的点
只能做到半在线,即所有询问涉及的矩形,会在所有加/删点操作之前给出。本质不同的询问矩形只有
为了解决这个问题,我们考虑将这个
我们同样需要将答案拆成若干个左下角矩形求和。
那么我们对于所有红块维护二维前缀和;对于每个
容易发现,当加入一个点时,
- 红色的整块(大块):总共
O(\sqrt n) 个,只需要修改O(\sqrt n) 个位置。 - 蓝色的整块(中块):总共
O(n^{1/4} \cdot n^{1/4}) = O(\sqrt n) 个,只要修改O(\sqrt n) 个位置。 - 黄色的整块(中块):同上,总共
O(\sqrt n) 个,只要修改O(\sqrt n) 个位置。 - 绿色的整块(小块):总共
O(n^{1/4} \cdot n^{1/4}) = O(\sqrt n) 个,只要修改O(\sqrt n) 个位置。
因此一次修改操作可以在
维护出二维前缀和后,对于一个询问(如上图中五角星所表示的),我们可以在
然而灰色的散块部分的点权和不好求。在博丽灵梦使用的二维分块中,我们通过枚举散块内部的点来使复杂度正确,然而在这个数据结构中不行。
考虑到允许半在线,我们可以在加入一个点的时候更新所有满足,这个点在该矩形的散块内部,的矩形的答案。
具体怎么更新呢?我们可以先用 vector 之类的东西把每个询问矩形挂到
这个为什么是对的?注意到由于插入的点
至此,查询可以在
接下来看这个题:区间本质不同逆序对计数。由于不弱于区间逆序对,且分块维护“本质不同”的限制较为困难,因此考虑莫队。
莫队的指针移动有四种情况,接下来我们讨论其中的两种。
第一种:
这是右端点扩展的情况;右端点收缩的情况与之是相对称的。则
那么如何处理逆序对和先前都不同这个条件呢?我们假设
那么假设我们现在有一个有序二元组
- 显然
i 和r 首先要构成逆序对,即a_i \isin (a_r, n] 。 - 其次如果
i < r' ,那么(i, r') 一定已经被计入答案了。所以必须满足i \isin (r', r) 。 - 对于所有满足上述两个条件,且
a_i 相同的i ,它们总共只会被计入答案一次。所以我们选择a_i 这种颜色在[l, r-1] 这个区间中第一次出现的位置计入答案,对于其他i 不计入答案。
为了方便处理,我们将条件 1 的左端点的等号取上,并将条件 2 的右端点的等号取上。最后只需要特判
我们考虑以
由于莫队的端点会扩展
具体地,我们将每个点的
因此变成了左下角
第二种:
假设
- 首先要是一个逆序对,因此必须满足
a_i < a_l ,即a_i \isin [1, a_l) 。 - 其次如果
i > l' ,那么(l', i) 已经被计入答案过了。因此需要保证i \isin (l, l') 。 - 同上,我们这里直接选定
i 是a_i 在区间内最后一次出现。
同样的,我们把条件 1,2 的开区间都取闭,最后再特判即可。我们照样对区间中所有是当前颜色出现最后一次的
发现左下角和右上角的坐标中同时包含
新矩形已在图中标出,这里不在赘述。这个矩形内部的点数可以差分成
假设
#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
#define M 500006
using namespace std;
using i64=long long;
int n,q,B,a[N],bel[N],cnt[N],pre[N],nxt[N],buc[N];
i64 ans[M],o[M];
struct Ask {int l,r,id;} ask[M];
struct Node {int l,r,v,id;};
vector<Node> vl[N],vr[N];
namespace ds {
constexpr int all=104976,Big=5832,Small=324,Div=18;
i64 s1[all/Big+5][all/Big+5];
i64 s2[all/Big+5][all/Small+5];
i64 s3[all/Small+5][all/Big+5];
i64 s4[all/Small+5][all/Small+5];
i64 s[all+5]; int tot,rx[all+5],ry[all+5],ix[all+5],iy[all+5];
void clear()
{
for(int i=0;i<all/Big+5;i++)
for(int j=0;j<all/Big+5;j++)s1[i][j]=0;
for(int i=0;i<all/Big+5;i++)
for(int j=0;j<all/Small+5;j++)s2[i][j]=0;
for(int i=0;i<all/Small+5;i++)
for(int j=0;j<all/Big+5;j++)s3[i][j]=0;
for(int i=0;i<all/Small+5;i++)
for(int j=0;j<all/Small+5;j++)s4[i][j]=0;
for(int i=0;i<all+5;i++)
s[i]=rx[i]=ry[i]=ix[i]=iy[i]=0;
tot=0;
}
void add_rec(int x,int y) {ix[x]=iy[y]=++tot,rx[tot]=x,ry[tot]=y;}
void insert(int x,int y,i64 val)
{
int x_b=(x-1)/Big+1,y_b=(y-1)/Big+1;
int x_s=(x-1)/Small+1,y_s=(y-1)/Small+1;
for(int i=x_b;i<=all/Big;i++)
for(int j=y_b;j<=all/Big;j++)s1[i][j]+=val;
for(int i=x_b;i<=all/Big;i++)
for(int j=y_s;j<=y_b*Div;j++)s2[i][j]+=val;
for(int i=x_s;i<=x_b*Div;i++)
for(int j=y_b;j<=all/Big;j++)s3[i][j]+=val;
for(int i=x_s;i<=x_b*Div;i++)
for(int j=y_s;j<=y_b*Div;j++)s4[i][j]+=val;
for(int i=x;i<=x_s*Small;i++)
if(ix[i]&&ry[ix[i]]>=y)s[ix[i]]+=val;
for(int i=y;i<=y_s*Small;i++)
if(iy[i]&&rx[iy[i]]>x_s*Small)s[iy[i]]+=val;
}
i64 query(int id)
{
int x=rx[id],y=ry[id];
int x_b=(x-1)/Big+1,y_b=(y-1)/Big+1;
int x_s=(x-1)/Small+1,y_s=(y-1)/Small+1;
i64 ret=s1[x_b-1][y_b-1];
if((y_s-1)%Div)ret+=s2[x_b-1][y_s-1];
if((x_s-1)%Div)ret+=s3[x_s-1][y_b-1];
if(((y_s-1)%Div)&&((x_s-1)%Div))ret+=s4[x_s-1][y_s-1];
return ret+s[id];
}
}
inline int rev(int x) {return n-x+1;}
main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)pre[i]=buc[a[i]],buc[a[i]]=i;
for(int i=1;i<=n;i++)buc[i]=0;
for(int i=n;i;i--)nxt[i]=buc[a[i]],buc[a[i]]=i;
scanf("%d",&q),B=max<int>(1,n/pow(q,0.5));
for(int i=1;i<=q;i++)
scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].id=i;
for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1;
sort(ask+1,ask+1+q,[](Ask x,Ask y) {
if(bel[x.l]!=bel[y.l])return x.l<y.l;
return bel[x.l]&1?x.r<y.r:x.r>y.r;
});
for(int i=1,l=1,r=0;i<=q;i++)
{
if(ask[i].l<l)vl[r].push_back({ask[i].l,l-1,1,i}),l=ask[i].l;
if(ask[i].r>r)vr[l].push_back({r+1,ask[i].r,1,i}),r=ask[i].r;
if(ask[i].l>l)vl[r].push_back({l,ask[i].l-1,-1,i}),l=ask[i].l;
if(ask[i].r<r)vr[l].push_back({ask[i].r+1,r,-1,i}),r=ask[i].r;
}
for(int i=1;i<=n;i++)cnt[a[i]]++;
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
for(int i=1;i<=n;i++)a[i]=cnt[a[i]]--;
for(int i=1;i<=n;i++)ds::add_rec(i,rev(a[i]));
for(int i=n;i;i--)
{
if(nxt[i])ds::insert(nxt[i],rev(a[nxt[i]]),-1);
ds::insert(i,rev(a[i]),1);
for(auto j:vr[i])
{
int l=j.l,r=j.r,v=j.v,id=j.id; i64 s=0;
for(int k=r;k>=l;k--)
s+=ds::query(k)-(pre[k]?ds::query(pre[k]):0ll)-(pre[k]<i);
ans[id]+=s*v;
}
}
ds::clear();
for(int i=1;i<=n;i++)ds::add_rec(rev(i),a[i]);
for(int i=1;i<=n;i++)
{
if(pre[i])ds::insert(rev(pre[i]),a[pre[i]],-1);
ds::insert(rev(i),a[i],1);
for(auto j:vl[i])
{
int l=j.l,r=j.r,v=j.v,id=j.id; i64 s=0;
for(int k=l;k<=r;k++)
s+=ds::query(k)-(nxt[k]?ds::query(nxt[k]):0ll)-(nxt[k]>i||!nxt[k]);
ans[id]+=s*v;
}
}
for(int i=1;i<=q;i++)
ans[i]+=ans[i-1],o[ask[i].id]=ans[i];
for(int i=1;i<=q;i++)printf("%lld\n",o[i]);
return 0;
}