BZOJ 3289 Mato的文件管理 莫隊算法+樹狀數組

BZOJ 3289 Mato的文件管理 莫隊算法+樹狀數組

題目大意：給定一個序列，多次詢問區間內逆序對的數量

總算是明白城市旅行是如何RE的了……尼瑪BZOJ坑爹 ostream輸出流過大居然會RE！輸出時順手用了cout結果各種RE不止……原來是這樣

建議各位在死活RE就是找不到原因的時候檢查一下是否大輸出用了cout

這題用莫隊可以很簡單搞掉 逆序對用樹狀數組就可以維護 一會去想想強制在線怎麼搞

#include 
#include 
#include 
#include 
#include 
#define M 50500
using namespace std;
struct abcd{
	int l,r,pos;
	bool operator < (const abcd x) const;
}q[M];
int n,m,l=1,r=0,tot,block,a[M],c[M];
pairb[M];
long long now,ans[M];
bool abcd :: operator < (const abcd x) const
{
	if( (l-1)/block == (x.l-1)/block )
		return r < x.r;
	return (l-1)/block < (x.l-1)/block;
}
void Update(int x,int y)
{
	for(;x<=tot;x+=x&-x)
		c[x]+=y;
}
int Get_Ans(int x)
{
	int re=0;
	for(;x;x-=x&-x)
		re+=c[x];
	return re;
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		scanf("%d",&b[i].first),b[i].second=i;
	sort(b+1,b+n+1);
	for(i=1;i<=n;i++)
	{
		if(i==1||b[i].first!=b[i-1].first)
			++tot;
		a[b[i].second]=tot;
	}
	block=(int)ceil(sqrt(n));
	cin>>m;
	for(i=1;i<=m;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].pos=i;
	sort(q+1,q+m+1);
	for(i=1;i<=m;i++)
	{
		while(l>q[i].l)
			now+=Get_Ans(a[--l]-1),Update(a[l],1);
		while(rq[i].r)
			Update(a[r],-1),now-=Get_Ans(tot)-Get_Ans(a[r--]);
		ans[q[i].pos]=now;
	}
	for(i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
}