题面

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

  

最新文章

  1. python数据类型详解
  2. Sprint1(第三天11.16)
  3. 在数据库中如果组合主键(假设为stuID和stuName)存在则更新,不存在则新增
  4. 在Java中直接调用js代码(转载)
  5. 远离腰痛的好方法&mdash;&mdash;如何锻炼腰背部肌肉?
  6. MySql存储引擎特性对比
  7. Tornado 中的 get() 或 post() 方法
  8. Yii防注入攻击笔记
  9. Web-Scale IT:对企业的影响
  10. 打包jar类库与使用jar类库
  11. Akka(10): 分布式运算:集群-Cluster
  12. Hibernate框架_搭建第一个Hibernate框架
  13. CMMI摘要
  14. 2017-12-14python全栈9期第一天第二节之初始计算机系统
  15. iOS 渐变提示。错误弹出提示 几秒自动消失
  16. 深入浅析Spring的AOP实现原理
  17. struts2访问web资源
  18. 处理 Maven 项目名称红色感叹号的问题
  19. SD从零开始19-20
  20. Angularjs乱记

热门文章

  1. 【openpyxl】 关于 单元格背景色 的疑惑
  2. Python与用户的交互
  3. 【spring boot】3.spring boot项目,绑定资源文件为bean并使用
  4. Sql Server--如何自动备份数据
  5. c++ 性能优化策略
  6. luogu题解P2486[SDOI2011]染色--树链剖分+trick
  7. 豆瓣网post 爬取带验证码
  8. (๑•̀ㅂ•́)و✧QQ用户信息管理系统
  9. 分布式缓存Redis+Memcached经典面试题和答案
  10. c#类生成表