Dylans loves sequence

  
  

   
   3 2
3 2 1
1 2
1 3
  
  

  
  

   
   1
3


   
   

    
    

     
     Hint
    
    
You shouldn't print any space in each end of the line in the hack data.

   
   
   
    
  
  

附上该题对应的中文题

Dylans得到了$N$个数$a[1]...a[N]$。
有$Q$个问题，每个问题形如$(L,R)$
他需要求出$L-R$这些数中的逆序对个数。
更加正式地，他需要求出二元组$(x,y)$的个数，使得$L\le x,y\le R$且$x<y$且$a[x]>a[y]$

第一行有两个数$N$和$Q$。
第二行给出$N$个数字$a[1]...a[N]$。
接下来的$Q$行，每行给出两个数$L,R$。

N leq 1000,Q leq 100000,L leq R,1 leq a[i] leq 2^{31}-1N≤1000,Q≤100000,L≤R,1≤a[i]≤2​31​​−1

对于每个询问，输出逆序对个数。

3 2
3 2 1
1 2
1 3

1 
3

hack数据里读入的每一行末尾不应该有多余的空格。

貌似涉及到这方面的题目，讲起来总是有点混乱，不过大家可以多多交流，这样能够理解得更透彻

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 1005;
const int inf = 1000000000;
int s[N][N],a[N];
int main()
{
    int n,q,i,j,k,l,r;
    while(~scanf("%d%d",&n,&q))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                s[i][j]+=s[i][j-1];
                if(a[j]<a[i])
                    s[i][j]++;
            }
        for(i=n;i>0;i--)
            for(j=i-1;j>0;j--)
                s[j][i]+=s[j+1][i];
        for(i=0;i<q;i++)
        {
            scanf("%d%d",&l,&r);
            printf("%dn",s[l][r]);
        }
    }
    return 0;
}

另一种方法就是用树状数组来进行预处理(虽然此题用树状数组稍显麻烦)

因为区间[l,r]之间的逆序对个数s[l][r]=区间[l,r-1]之间的逆序对个数+区间[l,r-1]加入第r个数a[r]所增加的逆序对个数

区间[l,r-1]之间的逆序对个数是已知的，关键就在于怎么用树状数组来求区间[l,r-1]加入第r个数a[r]所增加的逆序对个数

现在可以这么思考，我要想知道加入a[r]之后，增加了多少的逆序对，只要知道区间[l,r-1]内有多少比a[r]来得大的数即可，而这一步就可以用到树状数组。

在计算a[r]时，前面的a[l]到a[r-1]都已经对树状数组进行更新

比如说3 2 1，计算[1,2]时，[1,1]已经求出，且3已经对树状数组进行更新，当你加入第2个数2时，树状数组中比2大的数有1个，即3，树状数组总的和-小于等于2的数的个数就是大于2的数的个数，那就是加入2之后增加的逆序对个数

可能举例之后你还是不太明白我到底在说什么，但是不要紧，有问题可以提，我会尽快予以解答

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 1005;
const int inf = 1000000000;
int a[N],b[N],c[N],s[N][N];
int lowbit(int t) //计算c[t]展开的项数
{
    return t&(-t);
}
int Sum(int n) //求前n项的和.
{
    int sum=0;
    while(n>0)
    {
        sum+=c[n];
        n-=lowbit(n);
    }
    return sum;
}
void update(int i)
{
    while(i<=b[0])
    {
        c[i]++;
        i+=lowbit(i);
    }
}
int main()
{
    int i,j,m,n,p,q,l,r;
    while(~scanf("%d%d",&n,&q))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+n+1);//将数组b排序
        b[0]=unique(b+1,b+n+1)-(b+1);//去除数组b中相邻的重复元素
        for(i=1;i<=n;i++)
            a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
            //姑且可以叫做数据压缩吧，因为只要考虑大小关系，所以1 5 8完全可以记为1 2 3，减小树状数组的整体大小
        for(i=1;i<=n;i++)
        {
            memset(c,0,sizeof(c));
            for(j=i;j<=n;j++)
            {
                s[i][j]=s[i][j-1]+Sum(b[0])-Sum(a[j]);
                update(a[j]);
            }
        }
        while(q--)
        {
            scanf("%d%d",&l,&r);
            printf("%dn",s[l][r]);
        }
    }
}

菜鸟成长记

最后

以上就是落寞学姐为你收集整理的HDU 5273 Dylans loves sequence——BestCoder Round #45(DP or 树状数组) Dylans loves sequence Dylans loves sequence的全部内容，希望文章能够帮你解决HDU 5273 Dylans loves sequence——BestCoder Round #45(DP or 树状数组) Dylans loves sequence Dylans loves sequence所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。