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; }