3289: Mato的文件管理
Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 1539 Solved: 665
[Submit][Status][Discuss]
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
1 4 2 3
2
1 2
2 4
Sample Output
0
2
2
HINT
Hint
n,q <= 50000
样例解释：第一天，Mato不需要交换
第二天，Mato可以把2号交换2次移到最后。
Source
题解：
多次查询，不修改，一看就是莫队。。。
每次交换相邻的元素，这不是逆序对吗。。。
于是，直接胡搞一个莫队＋逆序对。。。
逆序对可以用树状数组维护，可以看一下我的上一篇博客http://www.cnblogs.com/Var123/p/5300334.html
Poj 2299就是求逆序对。(可以先做一下)
1A了很开心。。。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
int N,sz[MAXN],color[MAXN],BIT[MAXN],pos[MAXN],ans1[MAXN];
struct node
{
int l,r,id;
}q[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
bool cmp(node aa,node bb)
{
if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
return aa.l<bb.l;
}
int Lowbit(int o){return o&(-o);}
void Update(int o,int o1)
{
while(o<=N)
{
BIT[o]+=o1;
o+=Lowbit(o);
}
}
int Sum(int o)
{
int sum=;
while(o>)
{
sum+=BIT[o];
o-=Lowbit(o);
}
return sum;
}
int main()
{
int L,R,Q,i,ans,block,wz,tot;
N=read();
for(i=;i<=N;i++)sz[i]=read(),color[i]=sz[i];
sort(sz+,sz+N+);
tot=unique(sz+,sz+N+)-(sz+);
block=(int)sqrt(N);
Q=read();
for(i=;i<=Q;i++)
{
q[i].l=read();q[i].r=read();q[i].id=i;
}
for(i=;i<=N;i++)pos[i]=(int)(i-)/block+;
L=;R=;memset(BIT,,sizeof(BIT));
sort(q+,q+Q+,cmp);
ans=;
memset(ans1,,sizeof(ans1));
for(i=;i<=Q;i++)
{
while(L<q[i].l)
{
wz=lower_bound(sz+,sz+tot+,color[L])-sz;
Update(wz,-);
ans-=Sum(wz-);
L++;
//Update(wz,-1);
}
while(L>q[i].l)
{
L--;
wz=lower_bound(sz+,sz+tot+,color[L])-sz;
ans+=Sum(wz-);
Update(wz,);
}
while(R<q[i].r)
{
R++;
wz=lower_bound(sz+,sz+tot+,color[R])-sz;
ans+=(Sum(N)-Sum(wz));
Update(wz,);
}
while(R>q[i].r)
{
wz=lower_bound(sz+,sz+tot+,color[R])-sz;
ans-=(Sum(N)-Sum(wz));
Update(wz,-);
R--;
}
ans1[q[i].id]=ans;
}
for(i=;i<=Q;i++)printf("%d\n",ans1[i]);
return ;
}