cdoj 841 休生伤杜景死惊开逆序数/树状数组-白红宇

cdoj 841 休生伤杜景死惊开逆序数/树状数组

阅读量：4551 次

发布时间：2019-06-08

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

休生伤杜景死惊开

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

陆伯言军陷八卦阵之中，分明只是一条直路，却怎的也走不到尽头。阵中尽是石堆，以某一石堆为参考，无论向走还是向右，总是会回到出发的石堆,最后幸得一黄姓老翁带路才得脱出。

陆伯言逃离八卦阵后，来到山顶观察此阵，记从左往右第i堆石堆的高度为Ai，发现任何两堆较矮的石堆都能和它们之间的一座较高的石堆形成"八卦锁"，将其中之人牢牢锁住，无从逃脱。

根据石堆的情况，陆伯言大致计算了“八卦锁”的数量（即 Ai<Aj>Ak,i<j<k 的组合数），不禁心中一惊,对孔明惊为天人，遂放弃追击，收兵回吴。

“有劳岳父了。” “为何将其放走？” “...一表人才，何必浪费于此。”

Input

第一行一个整数n，表示石堆堆数。

接下来一行，n个整数，第i个数表示从左到右第i堆石堆的高度Ai。

1≤n≤50000,1≤Ai≤32768

Output

一个整数，“八阵锁”的数目。

Sample input and output

Sample Input

1 2 3 4 1

Sample Output

题意：

让你寻找多少对满足i<j<k,a[i]<a[j],a[j]>a[k]

题解

我们对于每一个数，直接去寻找看在这个数前面，有多少个数比这个数小，在这个数后面，有多少个数比这个数下，然后乘起来相加就好啦

利用树状数组或者线段树啥，归并都能做到logn的时间搞定

~\(≧▽≦)/~啦啦啦

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 100001#define mod 10007#define eps 1e-9const int inf=0x7fffffff; //无限大/*inline ll read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}*///**************************************************************************************int d[maxn];int c[maxn];int n;int t;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int lowbit(int x){ return x&-x;}void update(int x,int y){ while(x<=t) { d[x]+=y; x+=lowbit(x); }}int sum(int x){ int s=0; while(x>0) { s+=d[x]; x-=lowbit(x); } return s;}int num[maxn];int main(){ n=read(); for(int i=0;i
                  
                   =0;j--) { ans2[j]=sum(num[j]-1); update(num[j],1); } for(int i=0;i

转载于:https://www.cnblogs.com/qscqesze/p/4362446.html

你可能感兴趣的文章