HDU 5273 Dylans loves sequence【树状数组】-白红宇

HDU 5273 Dylans loves sequence【树状数组】

阅读量：5329 次

发布时间：2019-06-14

本文共 1627 字，大约阅读时间需要 5 分钟。

题意：给出n个数，再给出q个询问，求L到R的逆序对的个数

先自己写的时候，是每次询问都重新插入来求sum(r)-sum(l)

果断T

后来还是看了别人的代码----

预处理一下，把所有可能的区间的询问都求出来（1000*1000），然后询问就是O(1)了

然后想自己这样写超时，是因为询问太多了----

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std;12 13 typedef long long LL;14 const int INF = (1<<30)-1;15 const int mod=1000000007;16 const int maxn=1005;17 18 int a[maxn];19 int c[maxn];//树状数组20 int n,m;21 int ans[maxn][maxn];22 23 struct node{24 int x,id;25 }p[maxn];26 27 int cmp(node n1,node n2){28 return n1.x < n2.x;29 }30 31 int lowbit(int x){ return x &(-x);}32 33 int sum(int x){34 int ret=0;35 while(x>0){ 36 ret += c[x];x-=lowbit(x); 37 }38 return ret;39 }40 41 void add(int x,int d){42 while(x<=n){43 c[x]+=d;x+=lowbit(x);44 }45 }46 47 int main(){48 while(scanf("%d %d",&n,&m) != EOF){49 memset(c,0,sizeof(c));50 memset(a,0,sizeof(a));51 memset(ans,0,sizeof(ans));52 for(int i=1;i<=n;i++) {53 scanf("%d",&p[i].x);54 p[i].id=i;55 }56 sort(p+1,p+n+1,cmp);57 for(int i=1,j=0;i<=n;i++){58 if(i==1||p[i].x != p[i-1].x) j++;59 a[p[i].id]=j;60 }61 62 // for(int i=1;i<=n;i++)63 // printf("a[%d]=%d\n",i,a[i]);64 65 for(int i=1;i<=n;i++){66 memset(c,0,sizeof(c));67 int res=0;68 for(int j=i;j<=n;j++){69 res+=(j-i)-sum(a[j]);70 add(a[j],1);71 ans[i][j] = res;72 }73 }74 75 while(m--){76 int l,r;77 scanf("%d %d",&l,&r);78 printf("%d\n",ans[l][r]);79 }80 } 81 return 0;82 }