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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2741]【FOTILE模拟赛】L  

2015-03-16 21:05:51|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2741: 【FOTILE模拟赛】L

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 1401  Solved: 359
[Submit][Status][Discuss]

Description

FOTILE得到了一个长为N的序列A,为了拯救地球,他希望知道某些区间内的最大的连续XOR和。
即对于一个询问,你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj),其中l<=i<=j<=r。
为了体现在线操作,对于一个询问(x,y):
l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
其中lastans是上次询问的答案,一开始为0。

Input

第一行两个整数N和M。
第二行有N个正整数,其中第i个数为Ai,有多余空格。
后M行每行两个数x,y表示一对询问。

Output

共M行,第i行一个正整数表示第i个询问的结果。

Sample Input

3 3 1 4 3 0 1 0 1 4 3

Sample Output

5 7 7

HINT

N=12000,M=6000,x,y,Ai在signed longint范围内。

Solution

如果固定(l,r)内的某个端点,那么这个端点所构成的最大答案用贪心+可持久化Trie从高位到低位二分就可以求出来
O(n sqrt(n) log(Bit))做法:
分成sqrt(n)块
预处理第l块到第r块的答案,用可持久化Trie,复杂度为O((sqrt(n)^3 *log(Bit)) = O(n sqrt(n) log(Bit))
询问时先统计完全包含在(l,r)里面的大区间,答案可以一次性算出。
至于边角料,最多不会超过O(sqrt(n))个,复杂度为O(m sqrt(n) log(Bit))

Code

/**************************************************************
    Problem: 2741
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:8916 ms
    Memory:28276 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 120
#define L 32
using std::max;
int root[N*N],f[N][N*N],n,m,q,l,r,a[N*N],i,j,tot,kk[N*N],ans;
struct T{int ls,rs,cnt;}t[N*N*N];
int mkt(int g,int p,int x){
    int now=++tot;t[tot]=t[g];t[tot].cnt++;
    p--;if(p==-1)return now;
    if(x&(1<<p))t[now].rs=mkt(t[g].rs,p,x);
    else t[now].ls=mkt(t[g].ls,p,x);
    return now;
}
int ask(int lg,int rg,int x,int p){
    p--;if(p==-1)return 0;
    if(x&(1<<p)){
        if(t[t[rg].ls].cnt>t[t[lg].ls].cnt)return ask(t[lg].ls,t[rg].ls,x,p)+(1<<p);
        else return ask(t[lg].rs,t[rg].rs,x,p);
    }
    else if(t[t[rg].rs].cnt>t[t[lg].rs].cnt)return ask(t[lg].rs,t[rg].rs,x,p)+(1<<p);
    else return ask(t[lg].ls,t[rg].ls,x,p);
}
void calc(){
    for(int i=1;i<=kk[n];i++)
    for(int j=(i-1)*m+1;j<=n;j++)
    f[i][j]=max(f[i][j-1],ask(root[(i-1)*m],root[j],a[j],L));
}
void vio(int l,int r,int x,int y){
    /*l~r < a~b*/
    for(int i=l;i<=r;i++)ans=max(ans,ask(root[x],root[y],a[i],L));
}
void query(int l,int r){
    ans=0;l--;
    if(kk[l]==kk[r])vio(l,r,l,r);
    else vio(l,kk[l]*m,l,r),ans=max(ans,f[kk[l]+1][r]);
}
char B[1<<15],*S=B,*T=B;char getc(){
    return S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++;
}int aa;char ch;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}char buf[1<<18],*O=buf,stk[20];int ts;void P(int x){
    if(!x)*O++=48;else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=48+stk[ts--]);
    }*O++='\n';
}
int main(){
    n=F(),q=F(),m=sqrt(n*2);root[0]=mkt(0,L,0);
    for(i=1;i<=n;i++)kk[i]=(i-1)/m+1;
    for(i=1;i<=n;i++)a[i]=F()^a[i-1];
    for(i=1;i<=n;i++)root[i]=mkt(root[i-1],L,a[i]);
    for(calc();q--;P(ans),ans%=n){
        l=(F()+ans)%n+1,r=(F()+ans)%n+1;
        if(l>r)i=l,l=r,r=i;
        query(l,r);
    }*--O=0,puts(buf);
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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