//鸣谢litble(kb)Dalao细心地为我讲解cdq分治与这道题,感激不尽啊QvQ

1. 题目

传送门= ̄ω ̄=

2. 题解

典型的cdq分治解决三维偏序问题。

首先我们时光倒流,把所有删除操作转换为插入操作

那么三维分别为:

  • 插入时间$t$
  • 插入在原序列中的位置$x$
  • 插入的值$y$

得到三元组$(t,x,y)$

首先按第一维$t$排序后跑cdq,在cdq内将第二维$x$排序,然后用树状数组维护第三维$y$,每次更新$[mid+1,r]$(右区间)内所有操作的答案。

具体,,,下次让boshiDalao写个CDQ分治的算法文章吧(也可能是我写),这里不做过多赘述。

先贴代码啦(爸妈催ing)

#include <bits/stdc++.h>
#define lowbit(a) (a&-a)
#define NS (100005)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
} 
struct query{LL t,x,y,ans;}Q[NS],t1[NS],t2[NS]; 
LL n,m,num[NS],h[NS],del[NS],cnt,t[NS];
bool book[NS]; 
void add(LL a,LL d){while(a<=n)t[a]+=d,a+=lowbit(a);}
LL sum(LL a){LL tot=0;while(a)tot+=t[a],a-=lowbit(a);return tot;}
void binary(LL l,LL r)
{
    if(l==r)return;
    LL mid=(l+r)>>1;
    binary(l,mid),binary(mid+1,r);
    for(LL i=l;i<=mid;i++)t1[i]=Q[i];
    for(LL i=mid+1;i<=r;i++)t2[i]=Q[i];
    t1[mid+1].x=t2[r+1].x=INT_MAX;
    for(LL i=l,x1=l,x2=mid+1;i<=r;i++)
        if(t1[x1].x<t2[x2].x)Q[i]=t1[x1++];
        else Q[i]=t2[x2++];
    for(LL i=l,tot=0;i<=r;i++)
        if(Q[i].t<=mid)add(Q[i].y,1),tot++;
        else Q[i].ans+=tot-sum(Q[i].y-1);
    for(LL i=l,tot=0;i<=r;i++)if(Q[i].t<=mid)add(Q[i].y,-1);
    for(LL i=r;i>=l;i--)
        if(Q[i].t<=mid)add(Q[i].y,1);
        else Q[i].ans+=sum(Q[i].y-1);
    for(LL i=l,tot=0;i<=r;i++)if(Q[i].t<=mid)add(Q[i].y,-1);
}
inline bool cmp(query a,query b){return a.t<b.t;}
int main()
{
    IN(n),IN(m);
    for(LL i=1;i<=n;i++)IN(num[i]),h[num[i]]=i;
    for(LL i=1;i<=m;i++)IN(del[i]),book[h[del[i]]]=1;
    for(LL i=1;i<=n;i++)if(!book[i])Q[++cnt]=(query){cnt,i,num[i],0};
    for(LL i=m;i>=1;i--)Q[++cnt]=(query){cnt,h[del[i]],del[i],0};
    binary(1,cnt),sort(Q+1,Q+1+cnt,cmp);
    for(LL i=2;i<=cnt;i++)Q[i].ans+=Q[i-1].ans;
    for(LL i=cnt;i>cnt-m;i--)printf("%lld\n",Q[i].ans);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *