首页 > 代码库 > BZOJ 3289: Mato的文件管理[莫队算法 树状数组]
BZOJ 3289: Mato的文件管理[莫队算法 树状数组]
3289: Mato的文件管理
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 2399 Solved: 988
[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次移到最后。
普通莫队，区间转移时逆序对用树状数组处理 logn
树状数组求哪一块一定要想对了
//// main.cpp// 分块1//// Created by Candy on 2016/12/17.// Copyright © 2016年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=5e4+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,a[N],bl,pos[N],mp[N],m;inline int Bin(int v){ int l=1,r=m; while(l<=r){ int mid=(l+r)>>1; if(mp[mid]==v) return mid; if(v<mp[mid]) r=mid-1; else l=mid+1; } return -1;}struct ques{ int l,r,id; bool operator <(const ques a)const{ if(pos[l]==pos[a.l]) return r<a.r; else return pos[l]<pos[a.l]; }}q[N];int c[N];ll ans,an[N];inline int lowbit(int x){return x&-x;}inline void add(int p,int v){for(int i=p;i<=n;i+=lowbit(i))c[i]+=v;}inline int sum(int p){ int res=0; for(int i=p;i;i-=lowbit(i)) res+=c[i]; return res;}inline int sum(int l,int r){ return sum(r)-sum(l-1);}void solve(){ int l=1,r=0; for(int i=1;i<=Q;i++){ while(r<q[i].r) r++,ans+=sum(a[r]+1,m),add(a[r],1); while(r>q[i].r) ans-=sum(a[r]+1,m),add(a[r],-1),r--; while(l<q[i].l) ans-=sum(1,a[l]-1),add(a[l],-1),l++; while(l>q[i].l) l--,ans+=sum(1,a[l]-1),add(a[l],1); an[q[i].id]=ans; }}int main(int argc, const char * argv[]) { n=read(); bl=sqrt(n); for(int i=1;i<=n;i++) a[i]=mp[i]=read(),pos[i]=(i-1)/bl+1; sort(mp+1,mp+1+n); m=1; for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) a[++m]=a[i]; for(int i=1;i<=n;i++) a[i]=Bin(a[i]); Q=read(); for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+1+Q); solve(); for(int i=1;i<=Q;i++) printf("%lld\n",an[i]); return 0;}
BZOJ 3289: Mato的文件管理[莫队算法 树状数组]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。