首页 > 代码库 > 【bzoj3289】Mato的文件管理 离散化+莫队算法+树状数组
【bzoj3289】Mato的文件管理 离散化+莫队算法+树状数组
原文地址：http://www.cnblogs.com/GXZlegend/p/6805224.html
题目描述
Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？
输入
第一行一个正整数n，表示Mato的资料份数。
第二行由空格隔开的n个正整数，第i个表示编号为i的资料的大小。
第三行一个正整数q，表示Mato会看几天资料。
之后q行每行两个正整数l、r，表示Mato这天看[l,r]区间的文件。
输出
q行，每行一个正整数，表示Mato这天需要交换的次数。
样例输入
4
1 4 2 3
2
1 2
2 4
样例输出
0
2
题解
离散化+莫队算法+树状数组
首先有交换次数等于逆序对数
然后问题就转化为如何求一段区间的逆序对数。
由于[l,r]可推出[l-1,r]或[l,r+1]，可以考虑莫队算法。
先将询问排序，然后每次加入或删除元素时统计一下有多少逆序对变化即可，其中细节较多。
注意题中没给资料大小的范围，所以需要先离散化。
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 50010
using namespace std;
struct DATA
{
int num , pos;
}a[N];
struct QUERY
{
int l , r , bl , id;
}q[N];
int st[N] , top , val[N] , f[N] , ans[N];
bool cmp1(DATA a , DATA b)
{
return a.num < b.num;
}
bool cmp2(QUERY a , QUERY b)
{
return a.bl == b.bl ? a.r < b.r : a.bl < b.bl;
}
void update(int x , int a)
{
int i;
for(i = x ; i <= top ; i += i & -i) f[i] += a;
}
int query(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i) ans += f[i];
return ans;
}
int main()
{
int n , m , si , i , lp = 1 , rp = 0 , now = 0;
scanf("%d" , &n) , si = (int)sqrt(n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i].num) , a[i].pos = i;
sort(a + 1 , a + n + 1 , cmp1);
for(i = 1 ; i <= n ; i ++ )
{
if(a[i].num != st[top]) st[++top] = a[i].num;
val[a[i].pos] = top;
}
scanf("%d" , &m);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &q[i].l , &q[i].r) , q[i].bl = (q[i].l - 1) / si , q[i].id = i;
sort(q + 1 , q + m + 1 , cmp2);
for(i = 1 ; i <= m ; i ++ )
{
while(lp < q[i].l) now -= query(val[lp] - 1) , update(val[lp] , -1) , lp ++ ;
while(lp > q[i].l) lp -- , now += query(val[lp] - 1) , update(val[lp] , 1);
while(rp > q[i].r) now -= rp - lp + 1 - query(val[rp]) , update(val[rp] , -1) , rp -- ;
while(rp < q[i].r) rp ++ , now += rp - lp - query(val[rp]) , update(val[rp] , 1);
ans[q[i].id] = now;
}
for(i = 1 ; i <= m ; i ++ ) printf("%d\n" , ans[i]);
return 0;
}
【bzoj3289】Mato的文件管理 离散化+莫队算法+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。