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

ydc的博客

 
 
 

日志

 
 

陈立杰 middle  

2013-05-16 20:21:11|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一道不裸的函数式线段树
算法见陈立杰题解
感受到了其神奇
在bzoj上是能过的,但在清橙上却只有30分?
求解释
最近做题总是遇到这种灵异事件

今天终于知道原因了
数组开小了
大家如果要用代码,请自觉把数组开大
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 20010
using namespace std;
struct msgnode
{
int maxpre,maxsuf,sum;
msgnode() {}
msgnode(int v)
{
maxpre=v;
maxsuf=v;
sum=v;
}
friend msgnode operator + (const msgnode &a,const msgnode &b)
{
msgnode c;
c.maxpre=max(a.maxpre,a.sum+b.maxpre);
c.maxsuf=max(b.maxsuf,a.maxsuf+b.sum);
c.sum=a.sum+b.sum;
return c;
}
};
int q[10];
pair<int,int> temp[maxn];
int n,m,digit[maxn],root[maxn],tot;
int lson[maxn*20],rson[maxn*20];
msgnode msg[maxn*20];
int sign(int p,int k)
{
if(p>=k)
return 1;
return -1;
}
void newnode(int p)
{
lson[p]=++tot;
rson[p]=++tot;
}
int update(int l,int r)
{
++tot;
lson[tot]=l,rson[tot]=r;
msg[tot]=msg[l]+msg[r];
return tot;
}
int insert(int p,int id,int v,int l,int r)
{
if(l==r)
{
++tot;
msg[tot]=msgnode(v);
return tot;
}
if(lson[p]==0)
newnode(p);
int mid=(l+r)>>1;
if(id<=mid)
return update(insert(lson[p],id,v,l,mid),rson[p]);
else
return update(lson[p],insert(rson[p],id,v,mid+1,r));
}
msgnode Query(int p,int a,int b,int l,int r)
{
if(a>b)
return msgnode(0);
if(l==a&&r==b)
return msg[p];
int mid=(l+r)>>1;
if(b<=mid)
return Query(lson[p],a,b,l,mid);
else if(mid<a)
return Query(rson[p],a,b,mid+1,r);
else
return Query(lson[p],a,mid,l,mid)+Query(rson[p],mid+1,b,mid+1,r);
}
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&digit[i]);
temp[i]=make_pair(digit[i],i);
}
sort(temp+1,temp+n+1);
for(int i=1;i<=n;i++)
root[1]=insert(root[1],i,1,1,n);
for(int i=2;i<=n;i++)
root[i]=insert(root[i-1],temp[i-1].second,-1,1,n);
}
bool check(int p)
{
int p1,p2,p3;
p1=Query(root[p],q[1],q[2],1,n).maxsuf;
p2=Query(root[p],q[2]+1,q[3]-1,1,n).sum;
p3=Query(root[p],q[3],q[4],1,n).maxpre;
return p1+p2+p3>=0;
}
int Find(int l,int r)
{
while(l<r)
{
int mid=(l+r)>>1;
check(mid)?l=mid+1:r=mid;
}
return temp[l-1].first;
}
void ask()
{
int lastans=0;
scanf("%d",&m);
for(int i=1,a,b,c,d;i<=m;i++)
{
scanf("%d %d %d %d",&a,&b,&c,&d);
q[1]=(lastans+a)%n+1,q[2]=(lastans+b)%n+1,q[3]=(lastans+c)%n+1,q[4]=(lastans+d)%n+1;
sort(q+1,q+5);
lastans=Find(1,n+1);
printf("%d\n",lastans);
}
}
int main()
{
read();
ask();
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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