\(\\\)

\(Description\)

---

給定長度為\(2N\)的序列，\(1\text ~N\)各出現(xiàn)過\(2\)次，\(i\)第一次出現(xiàn)位置記為\(a_i\)，第二次記為\(b_i\)，求滿足\(a_i<a_j<b_i<b_j\)的\((i,j)\)對數(shù)。

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

\(\\\)

\(Solution\)

---

考慮以一個數(shù)作為\(i\)出現(xiàn)在答案里，對應(yīng)的\(j\)應(yīng)滿足\(a_j\in (a_i,b_i),b_j>b_i\)。也就是說，我們需要對每一個數(shù)統(tǒng)計它兩次出現(xiàn)的位置構(gòu)成的區(qū)間里，有多少個數(shù)字是第一次出現(xiàn)。

考慮樹狀數(shù)組的做法，第一次遇到一個數(shù)時，在出現(xiàn)位置打標(biāo)記，記錄下這個數(shù)第一次出現(xiàn)的位置，便于詢問。

當(dāng)?shù)诙斡龅竭@個數(shù)時，直接查詢區(qū)間\((a_i,b_i)\)的區(qū)間和即可。因為這個數(shù)已經(jīng)出現(xiàn)了兩次，不能對后續(xù)的詢問做出貢獻了，所以要將之前的打標(biāo)記處撤銷標(biāo)記。

\(\\\)

\(Code\)

---

#include<map> #include<cmath> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 50010 #define R register #define gc getchar using 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/SGCollin/p/9740980.html

總結(jié)

以上是生活随笔為你收集整理的[ USACO 2017 FEB ] Why Did the Cow Cross the Road III (Gold)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。