Bzoj 3289: Mato的文件管理 莫隊,樹狀數組,逆序對,離散化,分塊

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

Sample Output

0
2

HINT

?

Hint

n,q <= 50000

樣例解釋：第一天，Mato不需要交換

第二天，Mato可以把2號交換2次移到最后。

?

Source

By taorunz

?

題解：

多次查詢，不修改，一看就是莫隊。。。

每次交換相鄰的元素，這不是逆序對嗎。。。

于是，直接胡搞一個莫隊＋逆序對。。。

逆序對可以用樹狀數組維護，可以看一下我的上一篇博客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=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');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=0;
    while(o>0)
    {
        sum+=BIT[o];
        o-=Lowbit(o);
    }
    return sum;
}
int main()
{
    int L,R,Q,i,ans,block,wz,tot;
    N=read();
    for(i=1;i<=N;i++)sz[i]=read(),color[i]=sz[i];
    sort(sz+1,sz+N+1);
    tot=unique(sz+1,sz+N+1)-(sz+1);
    block=(int)sqrt(N);
    Q=read();
    for(i=1;i<=Q;i++)
    {
        q[i].l=read();q[i].r=read();q[i].id=i;
    }
    for(i=1;i<=N;i++)pos[i]=(int)(i-1)/block+1;
    L=1;R=0;memset(BIT,0,sizeof(BIT));
    sort(q+1,q+Q+1,cmp);
    ans=0;
    memset(ans1,0,sizeof(ans1));
    for(i=1;i<=Q;i++)
    {
        while(L<q[i].l)
        {
            wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
            Update(wz,-1);
            ans-=Sum(wz-1);
            L++;
            //Update(wz,-1);
        }
        while(L>q[i].l)
        {
            L--;
            wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
            ans+=Sum(wz-1);
            Update(wz,1);
        }
        while(R<q[i].r)
        {
            R++;
            wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
            ans+=(Sum(N)-Sum(wz));
            Update(wz,1);
        }
        while(R>q[i].r)
        {
            wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
            ans-=(Sum(N)-Sum(wz));
            Update(wz,-1);
            R--;
        }
        ans1[q[i].id]=ans;
    }
    for(i=1;i<=Q;i++)printf("%d\n",ans1[i]);
    return 0;
}

?