正題

題目鏈接:https://www.luogu.com.cn/problem/CF297E

---

題目大意

$2?n$個點的圓，$n$條圓上不交的弦，選擇三條使得每條弦對應(yīng)的弧上的點數(shù)量相等。

---

解題思路

就這5種情況，其中滿足條件的是$2$和$5$，我們用容斥去掉$1,3,4$即可。

對于每條弦，我們用樹狀數(shù)組維護出在它左邊和右邊且不與他相交的弦的數(shù)量$x,y$，然后與它相交的數(shù)量就是$z=n?1?x?y$。

第一種情況的個數(shù)就是$x?y$，第$3,4$種的和就是$z?(x+y)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const int N=2e5+10; ll n,ans; struct node{ll l,r; }p[N]; struct Tree_Array{ll t[N];void Change(ll x,ll val){while(x<=2*n){t[x]+=val;x+=lowbit(x);}return;}ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;} }Ta,Tp; bool cmp(node x,node y) {return x.r<y.r;} int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld%lld",&p[i].l,&p[i].r);if(p[i].r<p[i].l) swap(p[i].l,p[i].r);}sort(p+1,p+1+n,cmp);for(ll i=1;i<=n;i++)Ta.Change(p[i].l,1);ans=n*(n-1)*(n-2)/6ll;for(ll i=1;i<=n;i++){Ta.Change(p[i].l,-1);ll z=Tp.Ask(p[i].l)+Ta.Ask(p[i].r)-Ta.Ask(p[i].l);ll x=(p[i].r-1-p[i].l-z)/2,y=n-1-z-x;ans-=x*y+z*(x+y)/2;Tp.Change(p[i].l,1);Tp.Change(p[i].r,-1);}printf("%lld",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

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