一直 TLE,不知道怎么回事。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using std::cin;using std::cout;
constexpr int N=200005,B=1003;
int n,m,a[N],s[N],w,f[N],id[N],l[B],r[B],base,end,out[B];
long long ans;
struct Tree{
int b[N];
inline void clear(){
for(int i=1;i<=n;++i) b[i]=0;
}
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int p){
for(int i=x;i<=n;i+=lowbit(i))
b[i]+=p;
}
inline int query(int x){
int sum=0;
for(int i=x;i;i-=lowbit(i))
sum+=b[i];
return sum;
}
}tree;
inline int query(int x){
int X=f[x],sum=0;
for(int i=l[X];i<x;++i) sum+=(a[i]!=1)&&(a[i]>a[x]);
for(int i=x+1;i<=r[X];++i) sum+=(a[i]!=-1)&&(a[x]>a[i]);
for(int i=0;i<X;++i){
int k=std::upper_bound(s+l[i]+out[i],s+r[i]+1,a[x])-s;
sum+=r[i]-k+1;
// cout<<x<<' '<<i<<' '<<r[i]-k+1<<'\n';
}
for(int i=X+1;i<=end;++i){
int k=std::lower_bound(s+l[i]+out[i],s+r[i]+1,a[x])-s;
sum+=k-l[i]-out[i];
}
a[x]=-1;
for(int i=l[X];i<=r[X];++i) s[i]=a[i];
std::sort(s+l[X],s+r[X]+1);
++out[X];
return sum;
}
signed main(){
// freopen("P3157_1.in","r",stdin);
// freopen("P3157.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
while(cin>>n>>m){
tree.clear();ans=0;
base=sqrt(n);
for(int i=1;i<=n;++i){
cin>>a[i];s[i]=a[i];id[a[i]]=i;
tree.update(a[i],1);
ans+=i-tree.query(a[i]);
f[i]=(i-1)/base;
}
// cout<<' '<<ans<<'\n';
for(int i=1,j=0;i<=n;i+=base,++j){
l[j]=i;r[j]=std::min(i+base-1,n);
std::sort(s+l[j],s+r[j]+1);
end=j;
}
for(int i=1;i<=m;++i){
cout<<ans<<'\n';
cin>>w;int W=id[w];
ans-=query(W);
}
}
return 0;
}
// 10 10
// 1 4 7 3 6 5 9 2 10 8
// 1 2 3 4 5 6 7 8 9 10