思路:

等比数列求和 (无穷项)

+线段树找逆序对

//By SiriusRen
#include <bits/stdc++.h>
const int N=;
int n,m,vis[N],now=;
double p,r[N],tree[N*],ans;
struct Node{int x,y;}node[N];
bool cmp(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
void insert(int l,int r,int pos,int num,double wei){
if(l==r){tree[pos]+=wei;return;}
int mid=(l+r)>>,lson=pos<<,rson=pos<<|;
if(mid<num)insert(mid+,r,rson,num,wei);
else insert(l,mid,lson,num,wei);
tree[pos]=tree[lson]+tree[rson];
}
double query(int l,int r,int pos,int L,int R){
if(L>R)return ;
if(l>=L&&r<=R)return tree[pos];
int mid=(l+r)>>,lson=pos<<,rson=pos<<|;
if(mid<L)return query(mid+,r,rson,L,R);
else if(mid>=R)return query(l,mid,lson,L,R);
else return query(l,mid,lson,L,R)+query(mid+,r,rson,L,R);
}
double w(int now,int t){return p*r[t-]/(-r[vis[node[now].x]]);}
int main(){
scanf("%d%d%lf",&n,&m,&p),r[]=;
for(int i=;i<=;i++)r[i]=r[i-]*(-p);
for(int i=;i<=m;i++)scanf("%d%d",&node[i].x,&node[i].y),vis[node[i].x]++;
std::sort(node+,node++m,cmp);
for(int i=,t=;i<=n;i++,t=)while(node[now].x==i)
t++,insert(,n,,node[now].y,w(now,t)),
ans+=w(now,t)*query(,n,,node[now].y+,n),now++;
printf("%.2f\n",ans);
}

最新文章

  1. C#设计模式之桥接
  2. java和android的环境变量配置
  3. 攻城狮在路上(叁)Linux(十五)--- 文件与目录的默认权限与隐藏权限
  4. pair work-Elevator Schedule附加题
  5. 基于visual Studio2013解决C语言竞赛题之1048打印矩阵
  6. iOS开发之自定义弹出的键盘
  7. JAVA IO流结构图
  8. new 、 delete 、 malloc 、 free 关系
  9. sphinx+reStructuredText制作文档
  10. struts 中自定义action访问方法
  11. Python学习第五篇——如何访问字典
  12. Java 中数组的内存分配
  13. redmine3.3基于bitnami集成快速安装
  14. cp -rf 提示覆盖解决办法
  15. 学习技巧-如何在IBM官网寻找学习资料
  16. 使用ES(elasticsearch) 搜索引擎
  17. kinect 2 for xbox畸变矫正
  18. 一文弄懂神经网络中的反向传播法——BackPropagation【转】
  19. Delphi Delay 延时计数的功能。 下面的方法都是思路,但是没有用在项目上
  20. 【Codevs1922】骑士共存问题(最小割,二分图最大独立集转最大匹配)

热门文章

  1. linux whereis-查找二进制程序、代码等相关文件路径
  2. chrome://plugins 无法打开的解决方法,同时解决“该网页已屏蔽插件-adobe flash player”
  3. PAT 1020. Tree Traversals
  4. BNUOJ 33898 Cannon
  5. Leetcode 135.分糖果
  6. Leetcode 93.复制IP地址
  7. Android NumberProgressBar:动态移动显示百分比进度的进度条
  8. HDU 1234 简单模拟题
  9. php处理管道文件流
  10. HTTP自学心得