写的CDQ分治

然而以n==EOF||n==-1结束会T,

卡个1s的时就过了

为啥咧Qwq

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
struct Node
{
	int a,b,c;
} d[2145140];
int p[2145140];
int tr[2145140];
ll s[1145140];
int op;

inline int lowbit(int x)
{
	return (-x)&x;
}

inline void add(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	  tr[i]+=k;
}

inline ll ask(int x)
{
	ll res=0;
	for(int i=x;i;i-=lowbit(i))
	  res+=tr[i];
	return res;  
}

inline bool cmp1(Node a,Node b)
{
	if(a.a!=b.a)  return a.a<b.a;
	if(b.a!=b.b)  return a.b>b.b;
	return a.c<b.c;  
}

inline bool cmp2(Node a,Node b)
{
	if(a.a!=b.a)  return a.a>b.a;
	if(b.a!=b.b)  return a.b<b.b;
	return a.c<b.c;
}

inline bool cnmp1(Node a,Node b)
{
	if(a.b!=b.b)  return a.b>b.b;
	return a.c<b.c;
}

inline bool cnmp2(Node a,Node b)
{
	if(a.b!=b.b)  return a.b<b.b;
	return a.c<b.c;
}

void cdq1(int l,int r)
{
	if(l>=r)
	  return ;
	int mid=(l+r)>>1;
	cdq1(l,mid);cdq1(mid+1,r);
	sort(d+l,d+mid+1,cnmp1);
	sort(d+mid+1,d+r+1,cnmp1);
	int cnt=l;
	for(int i=mid+1;i<=r;i++)
	{
		while(d[cnt].b>=d[i].b&&cnt<=mid)
		{
			add(d[cnt].c,1);
			cnt++;//cout<<cnt<<' ';
		}
		s[d[i].c]+=ask(d[i].c);
	}  
	for(int i=l;i<cnt;i++)
	  add(d[i].c,-1);
}

void cdq2(int l,int r)
{
	if(l>=r)
	  return ;
	int mid=(l+r)>>1;
	cdq2(l,mid);cdq2(mid+1,r);
	sort(d+l,d+mid+1,cnmp2);
	sort(d+mid+1,d+r+1,cnmp2);
	int cnt=l;
	for(int i=mid+1;i<=r;i++)
	{
		while(d[cnt].b<=d[i].b&&cnt<=mid)
		{
			add(d[cnt].c,1);
			cnt++;
		}
		s[d[i].c]+=ask(d[i].c);
	}  
	for(int i=l;i<cnt;i++)
	  add(d[i].c,-1);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	while(1)
	{
		memset(s,0,sizeof s);
		memset(d,0,sizeof d);
		cin>>n;
		
		if((double)clock()/CLOCKS_PER_SEC>1)
		  return 0;  
		cin>>m;
		op=n-m;
		for(int i=1;i<=n;i++)
		{
			d[i].a=i;
			cin>>d[i].b;
			p[d[i].b]=i;
		}
		for(int i=1;i<=m;i++)
		{
			int x;
			cin>>x;
			d[p[x]].c=n-i+1;
		}
		for(int i=n;i>=1;i--)
		  if(!d[i].c)
		    d[i].c=op--;
		     
		sort(d+1,d+1+n,cmp1);
		cdq1(1,n);
		sort(d+1,d+1+n,cmp2);
		cdq2(1,n);
		
		/*for(int i=1;i<=n;i++)
		  cout<<s[i]<<' ';  */
		
		for(int i=1;i<=n;i++)
		  s[i]+=s[i-1];
		for(int i=1;i<=m;i++)
		  cout<<s[n-i+1]<<"\n"; 
	}

	
	return 0;
}
/*
3 2
3 4 2 
4
2
*/
/*
3 1
3 4 2
4
*/