正題

題目鏈接:http://contest-hunter.org:83/contest/0x40%E3%80%8C%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%BF%9B%E9%98%B6%E3%80%8D%E4%BE%8B%E9%A2%98/4201%20%E6%A5%BC%E5%85%B0%E5%9B%BE%E8%85%BE

---

題目大意

給若干個點(diǎn)，求可以得到/\和V的形狀各多少個。

---

解題思路

我們可以用樹狀數(shù)組求逆序?qū)Φ姆椒ㄇ蟪鲆粋€點(diǎn)左邊 小于/大于 和右邊 小于/大于 的數(shù)量各多少個，然后乘一下就好了。

---

code

#include<cstdio> #include<algorithm> #include<cstring> #define lobit(x) x&-x using namespace std; int t[200011],n,x; long long ans1,ans2; void add(int x,int num) {while(x<=n){t[x]+=num;x+=lobit(x);} } int ask(int x) {int sum=0;while(x>0){sum+=t[x];x-=lobit(x);}return sum; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);int k=ask(x-1);ans1+=(long long)(i-k-1)*(n-i-x+k+1);//求以i為中心的/\ans2+=(long long)k*(x-1-k);//求以i為中心的Vadd(x,1);}printf("%lld %lld",ans1,ans2); }

總結(jié)

以上是生活随笔為你收集整理的Ch4201-楼兰图腾【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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