BZOJ 3289: Mato的文件管理莫队+BIT

2023-02-28 12:22:28

3289: Mato的文件管理

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次移到最后。

题解：

　　莫队处理询问

　　每次对一个区间，我们假设已知[l,r] 如何移位得到 [l+1,r], [l,r+1]的答案

　　利用树状数组求逆序对即可

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include<vector>

#include <algorithm>

using namespace std;

const int N = 5e4+, M = 4e4+, mod = 1e9+, inf = 0x3f3f3f3f;

typedef long long ll;

int C[N * ],n,ans = ,a[N],an[N],b[N],belong[N];

struct ss{int l,r,id;}Q[N * ];

bool operator < (ss a,ss b) {

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

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

}

int ask(int x) {

    int s = ;

    for(int i = x; i > ; i -= i&(-i)) s += C[i];

    return s;

}

void add(int x,int c) {

    //cout<<x<<endl;

    for(int i = x; i < N; i += (i&(-i))) C[i] += c;

}

int main()

{

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

        b[i] = a[i];

    }

    sort(b+,b+n+);

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

    int q;

    scanf("%d",&q);

    for(int i = ; i <= q; ++i) {

        scanf("%d%d",&Q[i].l, &Q[i].r);

        Q[i].id = i;

    }

    int t = sqrt(n);

    for(int i = ; i <= q; ++i) belong[i] = (i-)/t + ;

    sort(Q + , Q + q + );

    int l = , r = ;

    for(int i = ; i <= q; ++i) {

        for(;r<Q[i].r;r++) ans += (r-l+-ask(a[r+])), add(a[r+],);//if(i == 1) cout<<l<<" "<<r<<endl;

        for(;l>Q[i].l;l--) ans += ask(a[l-]-) , add(a[l-],);

        for(;r>Q[i].r;r--) ans -= (r-l+ - ask(a[r])) ,add(a[r],-);

        for(;l<Q[i].l;l++) ans -= ask(a[l]-) , add(a[l],-);

        an[Q[i].id] = ans;//break;

      ///  cout<<ans<<endl;

    }

    for(int i = ; i <= q; ++i) printf("%d\n",an[i]);

}

码农公寓