求助分块
查看原帖
求助分块
394167
Cure_Wing楼主2023/8/16 22:07

一直 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
2023/8/16 22:07
加载中...