Time Limit: 40 Sec (Total)

Memory Limit: 128 MB

莫队+树状数组维护

类(jiu)似(shi)冒泡排序的过程

注意优化时间

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iterator>
using namespace std;

int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0;
struct asksx
{
	int codex,lx,rx,ans;
}ask[100010]={0};
int nowans=0;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int BinSearch(int val)
{
	int l=1,r=setlen,mid;
	while (1)
	{
		mid=(l+r)>>1;
		if (setx[mid]==val) return mid;
		else if (setx[mid]>val) r=mid-1;
		else l=mid+1;
	}
}

inline void process1()
{
	setlen=n;
	memcpy(setx,seq,sizeof(seq));
	sort(setx+1,setx+n+1);
	for (int i=1;i<=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; }
	sort(setx+1,setx+n+1);
	for (int i=1;i<=n;i++) seq[i]=BinSearch(seq[i]);
}

inline bool cmp1(asksx a,asksx b)
{
	if ((a.lx/blksz)==(b.lx/blksz)) return a.rx<b.rx;
	else return a.lx<b.lx;
}
inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void update(int pos,int val)
{
	while (pos<=setlen)
	{
		fwt[pos]+=val;
		pos+=(pos&(-pos));
	}
}

inline int query(int pos)
{
	int sum=0;
	while (pos)
	{
		sum+=fwt[pos];
		pos-=(pos&(-pos));
	}
	return sum;
}

int main()
{
	readx(n); blksz=sqrt(n);
	for (int i=1;i<=n;i++) readx(seq[i]);
	readx(m);
	for (int i=1;i<=m;i++)
	{
		ask[i].codex=i;
		readx(ask[i].lx); readx(ask[i].rx);
	}
	process1();
	sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0;
	for (int i=1;i<=m;i++)
	{
		while (rpos<ask[i].rx)
		{
			rpos++;
			update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos]));
		}
		while (rpos>ask[i].rx)
		{
			update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos]));
			rpos--;
		}
		while (lpos<ask[i].lx)
		{
			update(seq[lpos],-1); nowans-=query(seq[lpos]-1);
			lpos++;
		}
		while (lpos>ask[i].lx)
		{
			lpos--;
			update(seq[lpos],1); nowans+=query(seq[lpos]-1);
		}
		
		ask[i].ans=nowans;
	}
	
	sort(ask+1,ask+m+1,cmp2);
	for (int i=1;i<=m;i++) printf("%d\n",ask[i].ans);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.