[ USACO 2017 FEB ] Why Did the Cow Cross the Road III (Gold)-白红宇

[ USACO 2017 FEB ] Why Did the Cow Cross the Road III (Gold)

阅读量：7094 次

发布时间：2019-06-28

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

\(\\\)

给定长度为\(2N\)的序列，\(1\text ~N\)各出现过\(2\)次，\(i\)第一次出现位置记为\(a_i\)，第二次记为\(b_i\)，求满足\(a_i<a_j<b_i<b_j\)的\((i,j)\)对数。

\(N\in [1,10^5]\)

\(\\\)

\(Solution\)

考虑以一个数作为\(i\)出现在答案里，对应的\(j\)应满足\(a_j\in (a_i,b_i),b_j>b_i\)。也就是说，我们需要对每一个数统计它两次出现的位置构成的区间里，有多少个数字是第一次出现。

考虑树状数组的做法，第一次遇到一个数时，在出现位置打标记，记录下这个数第一次出现的位置，便于询问。

当第二次遇到这个数时，直接查询区间\((a_i,b_i)\)的区间和即可。因为这个数已经出现了两次，不能对后续的询问做出贡献了，所以要将之前的打标记处撤销标记。

\(\\\)

\(Code\)

#include#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 50010#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,ans,p[N];struct BIT{ int c[N]; inline int lowbit(int x){return x&-x;} inline void add(int p,int x){for(;p<=n;p+=lowbit(p))c[p]+=x;} inline int sum(int p){ int res=0; for(;p;p-=lowbit(p)) res+=c[p]; return res; }}bit;int main(){ n=rd()<<1; for(R int i=1,x;i<=n;++i){ x=rd(); if(!p[x]) bit.add((p[x]=i),1); else ans+=bit.sum(i)-bit.sum(p[x]),bit.add(p[x],-1); } printf("%d\n",ans); return 0;}

转载于:https://www.cnblogs.com/SGCollin/p/9740980.html

你可能感兴趣的文章