Why Did the Cow Cross the Road III bzoj-4994 Usaco-2017 Feb

題目大意：給定長度為$2N$的序列，$1~N$各處現過$2$次，$i$第一次出現位置記為$a_i$，第二次記為$b_i$，求滿足$a_i<a_j<b_i<b_j$的對數。

注釋：$1\le n\le 10^5$。

---

想法：顯然樹狀數組。

但是如何樹狀數組還是卡了我好半天。

不能像之前的題一樣，一個數出現的第一個位置是正標記，第二個位置是負標記。

這次我們考慮第一次遇到這個數的時候打上正標記，第二次遇到這個數的時候把第一次遇到時打的正標記刪除即可。

Code：

#include <bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; int tr[N<<2],vis[N],a[N<<1],n; inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;} int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;} inline int lowbit(int x) {return x&(-x);} void update(int x,int val) {for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=val;} ll query(int x) {ll ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tr[i]; return ans;} int main() {ll ans=0; n=rd()*2; for(int i=1;i<=n;i++) a[i]=rd(); for(int i=1;i<=n;i++)if(!vis[a[i]]) update(i,1),vis[a[i]]=i;else ans+=query(i)-query(vis[a[i]]),update(vis[a[i]],-1);cout << ans << endl ;return 0; }

小結：樹狀數組的小應用。

轉載于:https://www.cnblogs.com/ShuraK/p/10098087.html

總結

以上是生活随笔為你收集整理的[bzoj4994][Usaco2017 Feb]Why Did the Cow Cross the Road III_树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。