BZOJ 4481
2024-09-07 15:34:56
思路:
等比数列求和 (无穷项)
+线段树找逆序对
//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);
}
最新文章
- C#设计模式之桥接
- java和android的环境变量配置
- 攻城狮在路上(叁)Linux(十五)--- 文件与目录的默认权限与隐藏权限
- pair work-Elevator Schedule附加题
- 基于visual Studio2013解决C语言竞赛题之1048打印矩阵
- iOS开发之自定义弹出的键盘
- JAVA IO流结构图
- new 、 delete 、 malloc 、 free 关系
- sphinx+reStructuredText制作文档
- struts 中自定义action访问方法
- Python学习第五篇——如何访问字典
- Java 中数组的内存分配
- redmine3.3基于bitnami集成快速安装
- cp -rf 提示覆盖解决办法
- 学习技巧-如何在IBM官网寻找学习资料
- 使用ES(elasticsearch) 搜索引擎
- kinect 2 for xbox畸变矫正
- 一文弄懂神经网络中的反向传播法——BackPropagation【转】
- Delphi Delay 延时计数的功能。 下面的方法都是思路,但是没有用在项目上
- 【Codevs1922】骑士共存问题(最小割,二分图最大独立集转最大匹配)
热门文章
- linux whereis-查找二进制程序、代码等相关文件路径
- chrome://plugins 无法打开的解决方法,同时解决“该网页已屏蔽插件-adobe flash player”
- PAT 1020. Tree Traversals
- BNUOJ 33898 Cannon
- Leetcode 135.分糖果
- Leetcode 93.复制IP地址
- Android NumberProgressBar:动态移动显示百分比进度的进度条
- HDU 1234 简单模拟题
- php处理管道文件流
- HTTP自学心得