这道题目的意思是对于每个要删除的数字，向前或向后找到一块连续的数字，而它是其中最小的；
很容易看出对于所有要先删除的数字要从大到小删除；
然后对于每个要删除的字母，要找到比他小的，但是在原数列中又靠它最近的数字；
这样的话，很直观最多只能用lg n的复杂度来处理这个问题；
可以用二分查找，也可以用set来代替；
考虑到前面删除的一些数字不能计算进去，还要一个快速计算区间和的算法，用树状数组和线段树都可以；
不过看到tags，上面写着还可以用dsu（disjoint set union）并查集来做；
感觉挺神奇的，想到了之后再补上！
#include<cstdio>
#include<cstring>
#include<set>
#include<iostream>
#define maxn 1000009
using namespace std;
int n,m;
int pos[maxn];
bool vis[maxn];
long long value[maxn];
set<int>st;
set<int>::iterator it; void add(int x,int v)
{
while(x<=n)
{
value[x]+=v;
x+=x&(-x);
}
} long long sum(int x)
{
long long ret=;
while(x>)
{
ret+=value[x];
x-=x&(-x);
}
return ret;
} int main()
{
int num;
long long ans=;
scanf("%d%d",&n,&m);
st.insert();
st.insert(n+);
for(int i=;i<=n;i++)
{
scanf("%d",&num);
pos[num]=i;
add(i,);
}
for(int i=;i<=m;i++)
{
scanf("%d",&num);
vis[num]=;
}
for(int i=;i<=n;i++)
{
if(vis[i]==)//need be moved
{
it=st.upper_bound(pos[i]);
int r=*it-;
int l=*(--it);
ans+=sum(r)-sum(l);
add(pos[i],-);
}
else
{
st.insert(pos[i]);
}
}
cout<<ans;
}
经过hza大神的指点才明白用并差集的方法来做；
其实这个思路也比较简单。
我们从小到大来顺序来消灭数字的时候，我们总是找到它左右两边比它小的数字；
由于是从小到大的顺序，所以找到的数组只可能是不能被消灭的；
这样的话，就可以把整个数组分成几个小片。
就可以用并差集来处理；
最后从大到小来处理结果；
#include<cstdio>
#include<iostream>
#define maxn 1000006
using namespace std;
int n,m;
int pos[maxn];
bool can[maxn];
int size[maxn];
int f[maxn];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
} void dsu_union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)return;
f[b]=a;
size[a]+=size[b];
size[b]=;
} void interval_union(int p)
{
if(p>&&!can[p-])
dsu_union(p,p-);
if(p<n&&!can[p+])
dsu_union(p,p+);
} int main()
{
int num,p;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&num);
pos[num]=i;
f[i]=i;
}
for(int i=;i<=m;i++)
{
scanf("%d",&num);
can[pos[num]]=;
}
for(int i=;i<=n;i++)
if(!can[i])
interval_union(i);
long long ans=;
for(int i=n;i>=;i--)
{
p=pos[i];
num=find(p);
size[num]++;
if(!can[p])
ans+=size[num];
else
{
can[p]=;
interval_union(p);
}
}
cout<<ans;
}