CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）F

题面

F比较友善(相较于E)，我们发现如果i和j是满足条件的两个下标，那么:

a[i]-2*b[i] + a[j]-2*b[j] >=0 或者 b[i]-2*a[i] + b[j]-2*a[j] >=0。

又因为两个条件不可能同时成立(你把左边式子的不等号左边全移到右边试试)，所以我们可以分开算两种情况并最后把答案加起来。。。(其实两种情况是对称的，所以可以直接用一个函数解决，两次调用之间把所有 a[]与b[] swap一下就好啦)

对于每种情况，我们不妨把下标小的移项到右边，然后发现这就是一个简单的二维偏序问题啦，树状数组轻松过w

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int ha=1e9+7,N=1e5+5;

int a[N],b[N],c[N],n,m,f[N*2];

int p[N][2],num[N*2],ky,ans;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}

inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int read(){

    int x=0; char ch=getchar();

    for(;!isdigit(ch);ch=getchar());

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

    return x;

}

inline void update(int x,int y){

	for(;x<=ky;x+=x&-x) ADD(f[x],y);

}

inline int query(int x){

	int an=0;

	for(;x;x-=x&-x) ADD(an,f[x]);

	return an;

}

inline void solve(){

	memset(f,0,sizeof(f)),ky=0;

	for(int i=1;i<=n;i++){

		p[i][0]=a[i]-2*b[i],p[i][1]=-p[i][0];

		num[++ky]=p[i][0],num[++ky]=p[i][1];

	}

	sort(num+1,num+ky+1),ky=unique(num+1,num+ky+1)-num-1;

	for(int i=1;i<=n;i++)

	    for(int j=0;j<2;j++) p[i][j]=lower_bound(num+1,num+ky+1,p[i][j])-num;

	for(int i=1;i<=n;i++) update(p[i][1],c[i]),ADD(ans,c[i]*(ll)query(p[i][0])%ha);

}

int main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read();

	solve();

	for(int i=1;i<=n;i++) swap(a[i],b[i]);

	solve();

	printf("%d\n",ans);

	return 0;

}