注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

CTSC2013 没头脑和不高兴  

2014-03-13 19:33:31|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
期望交换次数就是期望逆序对个数
先看怎么搞期望
和的期望等于期望的和……
考虑i<j,a[i]>a[j]的概率,他们对答案有1的贡献,把这些概率加起来就行了
分情况:
1、i被选,j被选,那么a[i]>a[j]的概率为0
2、i没被选,j没被选,那么a[i]>a[j]的概率为1/2
3、i被选,j没被选,假设选了L个数,i是第k小的被选的数……考虑算概率?
ydc开始在草稿纸上写了一堆含有组合数的式子……懒得化简了,于是继续看艾神的PPT:k/(L+1)
我伙惊……可以理解为我们选了L+1个数之后,第L+1个数比第k小的数大的,所以就是k/(L+1)
4、i没被选,j被选,类似情况3
把这一大坨东西加起来
1、2好搞,3的话……对于一个没被选的j,假如他前面有k个被选的,对答案的贡献就是k(k-1)/2(L+1),我们需要维护Σk^2和Σk
艾神的方法是很厉害……然后证明也很显然
不过其实我们只要维护前缀和的和就能解决了,代码应该更加简单的
维护用线段树
第一问的话……可以用线段树,也可以利用这个思路来推公式,能推出来的
然后是方差
爆枚系数、牛顿差值、拉格朗日插值应该都是可以的吧
如果谁能推公式请受我深情一拜
我是直接抄了艾神ppt里的公式的说……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define it tree[root]
#define lson tree[root<<1]
#define rson tree[root<<1|1]
#define Root tree[1]
#define maxn 100010
using namespace std;
typedef long long LL;
struct Frac
{
LL a,b;
Frac() {}
Frac(LL x,LL y)
{
LL d=__gcd(x,y);
a=x/d,b=y/d;
}
friend Frac operator + (const Frac &a,const Frac &b)
{
LL d=__gcd(a.b,b.b),lcm=a.b/d*b.b;
return Frac(lcm/a.b*a.a+lcm/b.b*b.a,lcm);
}
};
struct msgnode
{
LL size1,size2,S,S2;
friend msgnode operator + (const msgnode &a,const msgnode &b)
{
static msgnode c;
c.size1=a.size1+b.size1;
c.size2=a.size2+b.size2;
c.S=a.S+b.S+a.size1*b.size2;
c.S2=a.S2+b.S2+2*a.size1*b.S+a.size1*a.size1*b.size2;
return c;
}
};
struct Node
{
int same,len;
msgnode msg;
}tree[maxn<<2];
int n,m;
void Build(int root,int l,int r)
{
it.same=-1,it.len=r-l+1;
if(l==r)
{
msgnode &p=it.msg;
if(l&1)
p.size1=1;
else
p.size2=1;
return ;
}
int mid=(l+r)>>1;
Build(root<<1,l,mid),Build(root<<1|1,mid+1,r);
it.msg=lson.msg+rson.msg;
}
void update_set(int root,int col)
{
it.same=col;
msgnode &p=it.msg;
if(col==0)
p.size1=0,p.size2=it.len;
else
p.size1=it.len,p.size2=0;
p.S=p.S2=0;
}
void push_down(int root)
{
if(it.same!=-1)
{
update_set(root<<1,it.same);
update_set(root<<1|1,it.same);
it.same=-1;
}
}
void Set(int root,int l,int r,int x,int y,int col)
{
if(l==x&&r==y)
{
update_set(root,col);
return ;
}
push_down(root);
int mid=(l+r)>>1;
if(y<=mid)
Set(root<<1,l,mid,x,y,col);
else if(mid<x)
Set(root<<1|1,mid+1,r,x,y,col);
else
Set(root<<1,l,mid,x,mid,col),Set(root<<1|1,mid+1,r,mid+1,y,col);
it.msg=lson.msg+rson.msg;
}
void read()
{
Frac p1,p2;
scanf("%d %d",&n,&m);
LL n0=n/2;
if(~n&1)
{
p1=Frac(7*n0*n0-n0,12);
p2=Frac(54*n0*n0*n0+13*n0*n0+23*n0,360);
}
else
{
p1=Frac(7*n0*n0+n0,12);
p2=Frac(54*n0*n0*n0+55*n0*n0-29*n0,360);
}
printf("%lld/%lld\n",p1.a,p1.b);
printf("%lld/%lld\n",p2.a,p2.b);
}
void Query()
{
Build(1,1,n);
Frac ans;
for(int i=1,l,r,t;i<=m;++i)
{
scanf("%d %d %d",&l,&r,&t);
Set(1,1,n,l,r,t);
LL S=Root.msg.S,S2=Root.msg.S2,L=Root.msg.size1;
ans=Frac((n-L)*(n-L-1),4);
ans=ans+Frac(S2+S,2*(L+1));
ans=ans+Frac((L+L*L)*(n-L)-S*(L*2+1)+S2,2*(L+1));
printf("%lld/%lld\n",ans.a,ans.b);
}
}
int main()
{
read();
Query();
return 0;
}

  评论这张
 
阅读(687)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017