Lvat_s Blog

本来想用树状数组+主席树水过去的……20min码完后发现空间炸了

卡了几发空间后发现自己并不会卡空间的高明技巧就弃疗了

后来写了一个CDQ分治就水过去了

主席树做法就不说了

CDQ分治主要就是按照位置划分第一层，按照时间(操作顺序)划分第二层，按照值划分第三层

第一层我们读入进来的就是有序的所以不用管

第二次我们可以用CDQ分治分治第二层

分治时用树状数组统计第三层

最后递归前要还原树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int L[N],R[N],BIT[N],time,n,m,pos[N];
long long ans[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Operation{
int t,a,b;
}a[N],b[N];

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){BIT[x]+=y;x+=lowbit(x);}}
inline int Sum(int x){int ans=0;while(x){ans+=BIT[x];x-=lowbit(x);}return ans;}

void CDQ(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
int Lx=l,Rx=mid+1;
for(register int i=l;i<=r;i++){
	if(a[i].t<=mid)b[Lx++]=a[i];
	else b[Rx++]=a[i];
}
Lx=l,Rx=mid;
for(register int i=mid+1;i<=r;i++){
	for(;Lx<=mid && b[Lx].a<=b[i].a;Lx++)Add(b[Lx].b,1);
	L[b[i].t]+=Lx-l-Sum(b[i].b);
}
for(register int i=l;i<Lx;i++)Add(b[i].b,-1);
for(register int i=r;i>mid;i--){
	for(;Rx>=l && b[Rx].a>b[i].a;Rx--)Add(b[Rx].b,1);
	R[b[i].t]+=Sum(b[i].b-1);
}
for(register int i=Rx+1;i<=mid;i++)Add(b[i].b,-1);
for(register int i=l;i<=r;i++)a[i]=b[i];
CDQ(l,mid);CDQ(mid+1,r);
}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);time=n;
for(register int i=1;i<=n;i++)Read(a[i].b),a[i].a=i,pos[a[i].b]=i;
for(register int i=1;i<=m;i++){int x;Read(x);a[pos[x]].t=time--;}
for(register int i=1;i<=n;i++)if(!a[i].t)a[i].t=time--;
CDQ(1,n);
for(register int i=1;i<=n;i++)ans[i]=ans[i-1]+L[i]+R[i];
for(register int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,BIT[N],cnt,a[N],b[N],ls[N*108],rs[N*108],sum[N*108],q[N],bq[N],pts;
long long ans,an[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Pushup(const int &rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}

void Insert(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]+1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid)Insert(ls[rt],ls[lrt],l,mid,v);
if(v>mid)Insert(rs[rt],rs[lrt],mid+1,r,v);
Pushup(rt);
}

void Delete(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]-1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid){if(sum[ls[rt]]==1){ls[rt]=0;return;}Delete(ls[rt],ls[lrt],l,mid,v);}
if(v>mid){if(sum[rs[rt]]==1){rs[rt]=0;return;}Delete(rs[rt],rs[lrt],mid+1,r,v);}
Pushup(rt);
}

long long FindU(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return sum[rs[rt]]+FindU(ls[rt],l,mid,v);
return FindU(rs[rt],mid+1,r,v);
}

long long FindD(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return FindD(ls[rt],l,mid,v);
return sum[ls[rt]]+FindD(rs[rt],mid+1,r,v);
}

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){Insert(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline void Del(int x,int y){while(x<=n){Delete(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline long long SumU(int x,int y){long long ans=0;while(x){ans+=FindU(BIT[x],1,n,y);x-=lowbit(x);}return ans;}
inline long long SumD(int x,int y){long long ans=0;while(x){ans+=FindD(BIT[x],1,n,y);x-=lowbit(x);}return ans;}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(a[i]);b[a[i]]=i;}
for(register int i=1;i<=m;i++){Read(q[i]);bq[q[i]]=1;}
for(register int i=1;i<=n;i++){
	if(bq[a[i]])continue;
	Add(i,a[i]);
	ans+=SumU(i,a[i])+SumD(n,a[i])-SumD(i-1,a[i]);
}
an[++pts]=ans;
for(register int i=m;i;i--){
	Add(b[q[i]],q[i]);
	ans+=SumU(b[q[i]],q[i])+SumD(n,q[i])-SumD(b[q[i]]-1,q[i]);
    an[++pts]=ans;
}
for(register int i=pts;i>1;i--)printf("%lld\n",an[i]);
return 0;
}