# 数据结构-莫队二次离线()-其他

## 数据结构-莫队二次离线()

### 莫队二次离线

$$n,m\leq 1e5$$

### 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=1e5+10;
ll n,m,a[M],lsh[M],cnt,pos[M],lim,lazy[M],sum[M<<2];
ll sum1[M],sum2[M],f1[M],f2[M],now_ans,ans[M];//1是前缀，2是后缀
struct Q{
ll l,r,id;
}q[M];
vector<Q> L[M],R[M];
bool cmp(Q x,Q y){
if(pos[x.l]==pos[y.l])return x.r<y.r;
else return pos[x.l]<pos[y.l];
}
ll lowbit(ll x){
return x&(-x);
}
for(;x<=cnt;x+=lowbit(x))sum[x]+=val;
}
ll res=0;
for(;x;x-=lowbit(x))res+=sum[x];
return res;
}
void init(){//处理形如前缀和的逆序对，减数
memset(sum,0,sizeof sum);
memset(lazy,0,sizeof lazy);
for(ll i=0;i<n;i++){
for(auto now:L[i]){
for(ll j=now.l;j<=now.r;j++){
f1[now.id]+=sum[a[j]]+lazy[pos[a[j]]];
}
}
for(ll j=a[i+1]-1;j>=lim*(pos[a[i+1]]-1)+1;j--)sum[j]++;
for(ll j=1;j<=pos[a[i+1]]-1;j++)lazy[j]++;//处理整块前缀和
}
memset(sum,0,sizeof sum);
memset(lazy,0,sizeof lazy);
for(ll i=n+1;i>=2;i--){
for(auto now:R[i]){
for(ll j=now.l;j<=now.r;j++){
f2[now.id]+=sum[a[j]]+lazy[pos[a[j]]];
}
}
for(ll j=a[i-1]+1;j<=lim*pos[a[i-1]];j++)sum[j]++;
for(ll j=pos[a[i-1]]+1;j<=pos[cnt];j++)lazy[j]++;
}
}
void remove(ll now){//莫队
if(q[now].r>q[now-1].r)now_ans+=sum1[q[now].r]-sum1[q[now-1].r]-f1[now];
if(q[now].r<q[now-1].r)now_ans-=sum1[q[now-1].r]-sum1[q[now].r]-f1[now];
if(q[now].l>q[now-1].l)now_ans-=sum2[q[now-1].l]-sum2[q[now].l]-f2[now];
if(q[now].l<q[now-1].l)now_ans+=sum2[q[now].l]-sum2[q[now-1].l]-f2[now];
}
int main(){
scanf("%lld%lld",&n,&m);
lim=sqrt(n);
for(ll i=1;i<=n;i++)pos[i]=(i-1)/lim+1;
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
lsh[i]=a[i];
}
sort(lsh+1,lsh+1+n);
cnt=unique(lsh+1,lsh+1+n)-lsh-1;
for(ll i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+1+cnt,a[i])-lsh;
//预处理被减数
for(ll i=1;i<=n;i++){
}
memset(sum,0,sizeof sum);
for(ll i=n;i>=1;i--){
}
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
q[0].l=1,q[0].r=0;
for(ll i=1;i<=m;i++){//将差分后的询问挂在节点上
if(q[i].r>q[i-1].r)L[q[i-1].l-1].push_back((Q){q[i-1].r+1,q[i].r,i});
if(q[i].r<q[i-1].r)L[q[i-1].l-1].push_back((Q){q[i].r+1,q[i-1].r,i});
if(q[i].l>q[i-1].l)R[q[i].r+1].push_back((Q){q[i-1].l,q[i].l-1,i});
if(q[i].l<q[i-1].l)R[q[i].r+1].push_back((Q){q[i].l,q[i-1].l-1,i});
}
init();
for(ll i=1;i<=m;i++){
remove(i);
ans[q[i].id]=now_ans;
}
for(ll i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}

————————

### 莫队二次离线

$$n,m\leq 1e5$$

### 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=1e5+10;
ll n,m,a[M],lsh[M],cnt,pos[M],lim,lazy[M],sum[M<<2];
ll sum1[M],sum2[M],f1[M],f2[M],now_ans,ans[M];//1是前缀，2是后缀
struct Q{
ll l,r,id;
}q[M];
vector<Q> L[M],R[M];
bool cmp(Q x,Q y){
if(pos[x.l]==pos[y.l])return x.r<y.r;
else return pos[x.l]<pos[y.l];
}
ll lowbit(ll x){
return x&(-x);
}
for(;x<=cnt;x+=lowbit(x))sum[x]+=val;
}
ll res=0;
for(;x;x-=lowbit(x))res+=sum[x];
return res;
}
void init(){//处理形如前缀和的逆序对，减数
memset(sum,0,sizeof sum);
memset(lazy,0,sizeof lazy);
for(ll i=0;i<n;i++){
for(auto now:L[i]){
for(ll j=now.l;j<=now.r;j++){
f1[now.id]+=sum[a[j]]+lazy[pos[a[j]]];
}
}
for(ll j=a[i+1]-1;j>=lim*(pos[a[i+1]]-1)+1;j--)sum[j]++;
for(ll j=1;j<=pos[a[i+1]]-1;j++)lazy[j]++;//处理整块前缀和
}
memset(sum,0,sizeof sum);
memset(lazy,0,sizeof lazy);
for(ll i=n+1;i>=2;i--){
for(auto now:R[i]){
for(ll j=now.l;j<=now.r;j++){
f2[now.id]+=sum[a[j]]+lazy[pos[a[j]]];
}
}
for(ll j=a[i-1]+1;j<=lim*pos[a[i-1]];j++)sum[j]++;
for(ll j=pos[a[i-1]]+1;j<=pos[cnt];j++)lazy[j]++;
}
}
void remove(ll now){//莫队
if(q[now].r>q[now-1].r)now_ans+=sum1[q[now].r]-sum1[q[now-1].r]-f1[now];
if(q[now].r<q[now-1].r)now_ans-=sum1[q[now-1].r]-sum1[q[now].r]-f1[now];
if(q[now].l>q[now-1].l)now_ans-=sum2[q[now-1].l]-sum2[q[now].l]-f2[now];
if(q[now].l<q[now-1].l)now_ans+=sum2[q[now].l]-sum2[q[now-1].l]-f2[now];
}
int main(){
scanf("%lld%lld",&n,&m);
lim=sqrt(n);
for(ll i=1;i<=n;i++)pos[i]=(i-1)/lim+1;
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
lsh[i]=a[i];
}
sort(lsh+1,lsh+1+n);
cnt=unique(lsh+1,lsh+1+n)-lsh-1;
for(ll i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+1+cnt,a[i])-lsh;
//预处理被减数
for(ll i=1;i<=n;i++){
}
memset(sum,0,sizeof sum);
for(ll i=n;i>=1;i--){
}
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
q[0].l=1,q[0].r=0;
for(ll i=1;i<=m;i++){//将差分后的询问挂在节点上
if(q[i].r>q[i-1].r)L[q[i-1].l-1].push_back((Q){q[i-1].r+1,q[i].r,i});
if(q[i].r<q[i-1].r)L[q[i-1].l-1].push_back((Q){q[i].r+1,q[i-1].r,i});
if(q[i].l>q[i-1].l)R[q[i].r+1].push_back((Q){q[i-1].l,q[i].l-1,i});
if(q[i].l<q[i-1].l)R[q[i].r+1].push_back((Q){q[i].l,q[i-1].l-1,i});
}
init();
for(ll i=1;i<=m;i++){
remove(i);
ans[q[i].id]=now_ans;
}
for(ll i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}