傳送門

?

1.每個(gè)數(shù)的左右位置預(yù)處理出來(lái)，按照左端點(diǎn)排序，因?yàn)樽蠖它c(diǎn)是從小到大的，我們只需要知道每條線段包含了多少個(gè)前面線段的右端點(diǎn)即可，可以用樹狀數(shù)組

2.如果 ai < bj < bi， 也就是說(shuō)在兩個(gè)i之間只有一個(gè)j那么對(duì)答案的貢獻(xiàn)為1，所以可以用樹狀數(shù)組，當(dāng)?shù)谝淮纬霈F(xiàn)一個(gè)數(shù)的時(shí)候，那個(gè)位置+1，當(dāng)?shù)诙纬霈F(xiàn)的時(shí)候，第一次出現(xiàn)的位置再-1，也就是把它對(duì)答案的貢獻(xiàn)去掉，同樣是樹狀數(shù)組統(tǒng)計(jì)答案

?

#include <cstdio> #include <iostream> #define N 200001int n, ans; int sum[N], vis[N];inline int read() {int x = 0, f = 1;char ch = getchar();for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';return x * f; }inline int query(int x) {int ret = 0;for(; x; x -= x & -x) ret += sum[x];return ret; }inline void add(int x, int d) {for(; x <= n; x += x & -x) sum[x] += d; }int main() {int i, x;n = read() * 2;for(i = 1; i <= n; i++){x = read();if(!vis[x])vis[x] = i, add(i, 1);elseans += query(i) - query(vis[x]), add(vis[x], -1);}std::cout << ans;return 0; }

　　

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

總結(jié)

以上是生活随笔為你收集整理的[BZOJ4994] [Usaco2017 Feb]Why Did the Cow Cross the Road III（树状数组）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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