「BZOJ3289」Mato的文件管理

2014年12月3日7,1814

Description

Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？

Input

第一行一个正整数n，表示Mato的资料份数。
第二行由空格隔开的n个正整数，第i个表示编号为i的资料的大小。
第三行一个正整数q，表示Mato会看几天资料。
之后q行每行两个正整数l、r，表示Mato这天看[l,r]区间的文件。

Output

q行，每行一个正整数，表示Mato这天需要交换的次数。

Sample Input

4
1 4 2 3
2
1 2
2 4

Sample Output

0
2

HINT

Hint
n,q <= 50000
样例解释：第一天，Mato不需要交换
第二天，Mato可以把2号交换2次移到最后。

题解

离线后用树状数组是最简单的做法吧

例如在区间末尾添加一个数就在树状数组中查询大于它的数的个数

主席树也是可以的

据说还有俩log的做法。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#include<vector>
#include<set>
#include<cmath>
#include<algorithm>
#define inf 1000000000
#define ll long long
#define eps 1e-5
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
unsigned int now,ans[50005];
int n,m;
int a[50005],disc[50005],belong[50005];
int t[50005];
struct query{int l,r,id;}q[50005];
bool operator<(query a,query b)
{
	if(belong[a.l]==belong[b.l])return a.r<b.r;
	return belong[a.l]<belong[b.l];
}
void add(int x,int val)
{
	for(int i=x;i<=n;i+=i&-i)
		t[i]+=val;
}
unsigned int query(int x)
{
	unsigned int sum=0;
	for(int i=x;i;i-=i&-i)
		sum+=t[i];
	return sum;
}
void solve()
{
	sort(q+1,q+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l)
			add(a[l],-1),now-=query(a[l]-1),l++;
		while(r>q[i].r)
			add(a[r],-1),now-=r-l-query(a[r]),r--;
		while(l>q[i].l)
			l--,add(a[l],1),now+=query(a[l]-1);
		while(r<q[i].r)
			r++,add(a[r],1),now+=r-l+1-query(a[r]);
		ans[q[i].id]=now;
	}
}
int main()
{
	n=read();
	int t=sqrt(n);
	for(int i=1;i<=n;i++)disc[i]=a[i]=read();
	sort(disc+1,disc+n+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(disc+1,disc+n+1,a[i])-disc;
	m=read();
	for(int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	for(int i=1;i<=n;i++)
		belong[i]=(i-1)/t+1;
	solve();
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<map>

#include<ctime>

#include<vector>

#include<set>

#include<cmath>

#include<algorithm>

#define inf 1000000000

#define ll long long

#define eps 1e-5

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

unsigned int now,ans[50005];

int n,m;

int a[50005],disc[50005],belong[50005];

int t[50005];

struct query{int l,r,id;}q[50005];

bool operator<(query a,query b)

{

if(belong[a.l]==belong[b.l])return a.r<b.r;

return belong[a.l]<belong[b.l];

}

void add(int x,int val)

{

for(int i=x;i<=n;i+=i&-i)

t[i]+=val;

}

unsigned int query(int x)

{

unsigned int sum=0;

for(int i=x;i;i-=i&-i)

sum+=t[i];

return sum;

}

void solve()

{

sort(q+1,q+m+1);

int l=1,r=0;

for(int i=1;i<=m;i++)

{

while(l<q[i].l)

add(a[l],-1),now-=query(a[l]-1),l++;

while(r>q[i].r)

add(a[r],-1),now-=r-l-query(a[r]),r--;

while(l>q[i].l)

l--,add(a[l],1),now+=query(a[l]-1);

while(r<q[i].r)

r++,add(a[r],1),now+=r-l+1-query(a[r]);

ans[q[i].id]=now;

}

int main()

{

n=read();

int t=sqrt(n);

for(int i=1;i<=n;i++)disc[i]=a[i]=read();

sort(disc+1,disc+n+1);

for(int i=1;i<=n;i++)a[i]=lower_bound(disc+1,disc+n+1,a[i])-disc;

m=read();

for(int i=1;i<=m;i++)

q[i].l=read(),q[i].r=read(),q[i].id=i;

for(int i=1;i<=n;i++)

belong[i]=(i-1)/t+1;

solve();

for(int i=1;i<=m;i++)

printf("%d\n",ans[i]);

return 0;

}

« 「BZOJ1145」[CTSC2008] 图腾totem NOI2011阿狸的打字机 »

做这道题，来看题解&%%% h学长

Sky_sys

主席树怎么做

doubi

求教两个log的做法

hzwer

我也不知道

hzwer.com _ Home | http://hzwer.com

「BZOJ3289」Mato的文件管理

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论