[Codeforces g100247]K. Three Contests

這題目不好找，附上題目連結

真的是可用整體二分解的經典題目，講解起來也輕鬆許多

題目叫我們求有幾對隊伍$t_{1}$、$t_{2}$，$t_{1}.a<t_{2}.a$或$t_{1}.b<t_{2}.b$或$t_{1}.c<t_{2}.c$
其實這就等於全部配對$\frac{N(N-1)}{2}$減掉有幾對$t_{1}.a<t_{2}.a$且$t_{1}.b<t_{2}.b$且$t_{1}.c<t_{2}.c$

我們先把隊伍依照$b$來排序，然後取中間值$a_{m}=\frac{1+N}{2}$，$O(N)$將隊伍分成$a\leq a_{m}$和$a>a_{m}$兩類，可以發現，這兩類中的隊伍已經依照$b$排序好

利用$b$的單調性，我們可以枚舉在$a>a_{m}$這類中的隊伍$t$，然後把$a\leq a_{m}$的隊伍中$b<t.b$的$c$加進$BIT$ ($Binary\ Indexed\ Tree$) 維護，因為兩類隊伍的$b$已經排序好，整個枚舉和維護均攤$O(N\log N)$
然後對於當前枚舉到的$t$，我們就可以對$BIT$進行$query$，$O(\log N)$求出被加進$BIT$的隊伍中有幾個$c<t.c$了
而被加進$BIT$的隊伍中，已經保證$a\leq a_{m}<t.a$且$b<t.b$！

我們已經在區間$[1,N]$中處理好區間$[1,a_{m}]$和$[a_{m}+1,N]$之間的聯繫
接著，就是遞迴處理區間$[1,a_{m}]$和$[a_{m}+1,N]$了
記得先把$BIT$逆向操作還原成初始狀態才能供遞迴下去後使用

將所有$BIT$的$query$得到的答案加起來，就是有幾對$t_{1}.a<t_{2}.a$且$t_{1}.b<t_{2}.b$且$t_{1}.c<t_{2}.c$
答案就是$\frac{N(N-1)}{2}$減掉這個東西

時間複雜度：$O(N\log^{2}N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
struct Team
{
    int a,b,c;
    Team():a(),b(),c(){}
    Team(const int _a,const int _b,const int _c):a(_a),b(_b),c(_c){}
};
struct Bit
{
    int n;
    int data[200001];
    void Clear(const int _n){n=_n;for(int i=1;i<=n;i++)data[i]=0;}
    void Add(int i,const int v){while(i<=n)data[i]+=v,i+=(i&(-i));}
    int Query(int i){int ans=0;while(i)ans+=data[i],i-=(i&(-i));return ans;}
}BIT;
LL ANS;
vector<Team>TEAM;
void Solve(const int l,const int r,const vector<int>&teams)
{
    if(l==r)return;
    const int mid=(l+r)/2;
    vector<int>left_teams,right_teams;
    for(const int &t:teams)(TEAM[t].a<=mid?left_teams:right_teams).push_back(t);
    vector<int>::const_iterator lt=left_teams.begin();
    for(vector<int>::const_iterator rt=right_teams.begin();rt!=right_teams.end();rt++)
    {
        while(lt!=left_teams.end()&&TEAM[*lt].b<TEAM[*rt].b)BIT.Add(TEAM[*lt++].c,1);
        ANS+=BIT.Query(TEAM[*rt].c);
    }
    while(lt!=left_teams.begin())BIT.Add(TEAM[*--lt].c,-1);
    Solve(l,mid,left_teams),Solve(mid+1,r,right_teams);
    vector<int>().swap(left_teams);
    vector<int>().swap(right_teams);
}
int N;
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    TEAM.clear();
    for(int i=0,a,b,c;i<N;i++)scanf("%d%d%d",&a,&b,&c),TEAM.push_back(Team(a,b,c));
    sort(TEAM.begin(),TEAM.end(),[](const Team &a,const Team &b)->bool{return a.b<b.b;});
    vector<int>teams;
    for(int i=0;i<N;i++)teams.push_back(i);
    ANS=0LL;
    BIT.Clear(N);
    Solve(1,N,teams);
    printf("%I64d\n",(LL)N*(N-1LL)/2LL-ANS);
    return 0;
}