首页 > 代码库 > 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