3289: Mato的文件管理

Time Limit: 40 Sec  Memory Limit: 128 MB

Submit: 1539  Solved: 665

[][][]

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

 

题解：

多次查询，不修改，一看就是莫队。。。

每次交换相邻的元素，这不是逆序对吗。。。

于是，直接胡搞一个莫队＋逆序对。。。

逆序对可以用树状数组维护，可以看一下我的上一篇博客

Poj 2299就是求逆序对。(可以先做一下)

1A了很开心。。。

1 #include
       
         2 using namespace std; 3 #define MAXN 50010 4 int N,sz[MAXN],color[MAXN],BIT[MAXN],pos[MAXN],ans1[MAXN]; 5 struct node 6 { 7     int l,r,id; 8 }q[MAXN]; 9 int read()10 {11     int s=0,fh=1;char ch=getchar();12     while(ch<'0'||ch>'9'){
     if(ch=='-')fh=-1;ch=getchar();}13     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}14     return s*fh;15 }16 bool cmp(node aa,node bb)17 {18     if(pos[aa.l]==pos[bb.l])return aa.r
        
         0)34     {35         sum+=BIT[o];36         o-=Lowbit(o);37     }38     return sum;39 }40 int main()41 {42     int L,R,Q,i,ans,block,wz,tot;43     N=read();44     for(i=1;i<=N;i++)sz[i]=read(),color[i]=sz[i];45     sort(sz+1,sz+N+1);46     tot=unique(sz+1,sz+N+1)-(sz+1);47     block=(int)sqrt(N);48     Q=read();49     for(i=1;i<=Q;i++)50     {51         q[i].l=read();q[i].r=read();q[i].id=i;52     }53     for(i=1;i<=N;i++)pos[i]=(int)(i-1)/block+1;54     L=1;R=0;memset(BIT,0,sizeof(BIT));55     sort(q+1,q+Q+1,cmp);56     ans=0;57     memset(ans1,0,sizeof(ans1));58     for(i=1;i<=Q;i++)59     {60         while(L
         
          q[i].l)69         {70             L--;71             wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;72             ans+=Sum(wz-1);73             Update(wz,1);74         }75         while(R
          
           q[i].r)83         {84             wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;85             ans-=(Sum(N)-Sum(wz));86             Update(wz,-1);87             R--;88         }89         ans1[q[i].id]=ans;90     }91     for(i=1;i<=Q;i++)printf("%d\n",ans1[i]);92     return 0;93 }