首页 > 代码库 > Poj 3368 Frequent values
Poj 3368 Frequent values
/*线段树区间合并维护几个信息 到时候乱搞一下就好了开始T了 有一种情况可以不用递归 直接算出来 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010#define lc (k<<1)#define rc (k<<1)+1#define mid ((l+r)>>1)using namespace std;int n,m,a[maxn],ls[maxn*4],rs[maxn*4],ln[maxn*4],rn[maxn*4],s[maxn*4];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Build(int k,int l,int r){ if(l!=r){ Build(lc,l,mid); Build(rc,mid+1,r); s[k]=max(s[lc],s[rc]); if(rn[lc]==ln[rc]) s[k]=max(s[k],rs[lc]+ls[rc]); ln[k]=ln[lc];rn[k]=rn[rc]; ls[k]=ls[lc];rs[k]=rs[rc]; if(ls[lc]==mid-l+1&&rn[lc]==ln[rc]) ls[k]=max(ls[k],ls[lc]+ls[rc]); if(rs[rc]==r-mid&&rn[lc]==ln[rc]) rs[k]=max(rs[k],rs[rc]+rs[lc]); } else{ ls[k]=rs[k]=1;ln[k]=rn[k]=a[l];s[k]=1; }}int Query(int k,int l,int r,int x,int y){ if(x<=l&&y>=r)return s[k]; int ret=0,L,R; if(y<=mid)return Query(lc,l,mid,x,y); else if(x>mid)return Query(rc,mid+1,r,x,y); else{ if(rn[lc]==ln[rc]){ L=max(mid-rs[lc]+1,x); R=min(mid+ls[rc],y); ret=mid-L+1+R-mid; } //ret=Query(lc,l,mid,max(mid-rs[lc]+1,x),mid) //+Query(rc,mid+1,r,mid+1,min(mid+ls[rc],y));可以只结算出来 QAQ T了好几遍 ret=max(ret,Query(lc,l,mid,x,y)); ret=max(ret,Query(rc,mid+1,r,x,y)); } return ret;}int main(){ while(1){ n=init();if(n==0)break; m=init(); for(int i=1;i<=n;i++)a[i]=init(); Build(1,1,n); while(m--){ int L,R; L=init();R=init(); printf("%d\n",Query(1,1,n,L,R)); } } return 0;}
/*ST表做法 比较巧妙 时间差不多 空间大一些 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010using namespace std;int n,m,a[maxn],c[maxn],f[maxn][25],lst[maxn],p[maxn];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Clear(){ memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); memset(lst,0,sizeof(lst));}void Get_p(){ for(int i=1;i<=maxn-10;i++) for(int j=0;j<=20;j++) if((1<<j)>i){ p[i]=j-1;break; }}void Get_ST(){ for(int i=1;i<=n;i++)f[i][0]=c[i]; for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); }int Query(int l,int r){ if(l>r)return 0; int k=p[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]);}int main(){ Get_p(); while(1){ n=init();if(n==0)break;m=init(); Clear(); for(int i=1;i<=n;i++)a[i]=init(); for(int i=1;i<=n;i++) if(a[i]==a[i-1])c[i]=c[i-1]+1; else c[i]++; for(int i=n;i>=1;i--) if(a[i]==a[i+1])lst[i]=lst[i+1]; else lst[i]=i; Get_ST(); while(m--){ int L,R,mxx=0,mx=0; L=init();R=init(); mxx=Query(lst[L]+1,R); mx=min(lst[L],R)-L+1; printf("%d\n",max(mxx,mx)); } } return 0;}
Poj 3368 Frequent values
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。