[线段树]poj 3368

题意

      给出一串数字，有m次询问，每次询问[ab]区间内出现次数最多的数字出现了多少次。

 

思路

      一开始用线段树+延迟标记超时到死，后来发现只用哈希+区间极值做就可以

      例如   11111【1111222233444488】888  求【】内的时候就把区间内的串分为1111    2222334444   88对中间的串哈希+区间极值再和两边的串长度进行比较

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
const int nMax = 100010;
int num[nMax];
struct{
    int l,r,val;
}node[3*nMax];

map<int,pair<int,int> >mp;
int has[nMax];

void build(int left ,int right ,int u){
    node[u].l = left;
    node[u].r = right;
    if(left == right){
        node[u].val = mp[left].second - mp[left].first + 1;
        return;
    }
    int m = (left + right) >> 1;
    build(left ,m ,2*u);
    build(m+1 ,right ,2*u + 1);
    node[u].val = max(node[2*u].val ,node[u*2 + 1].val);
}
int query(int left ,int right ,int u){
    if(left == node[u].l && right == node[u].r){
        return node[u].val;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(right <= m){
        return query(left ,right ,u*2);
    }
    if(left >= m+1){
        return query(left ,right ,u*2 + 1);
    }
    int a = query(left ,m ,u*2 );
    int b = query(m+1 ,right ,u*2 + 1);
    return max(a ,b);
}
int main(){
    int n ,m ,a ,b ,i ,k;
    while(scanf("%d",&n)!=EOF && n){
        scanf("%d",&m);
        num[0] = 100001;
        k=0;
        for(i = 1 ;i <= n ;i++ ){
            scanf("%d",&num[i]);
            if(num[i] != num[i-1]){
                has[i] = ++k;
                mp[k].first = i;
                mp[k].second = i;
            }else{
                mp[k].second = i;
                has[i] = k;
            }
        }
        build(1 ,k ,1);
        while(m -- ){
            scanf("%d%d",&a,&b);
            if(has[a] == has[b]){
                printf("%d\n",b - a + 1);
                continue;
            }
            int la = mp[has[a]].second;
            int lb = mp[has[b]].first;
            if(lb == la + 1){
                la = max(la - a + 1,b - lb + 1);
                printf("%d\n",la);
                continue;
            }
            int lc = query(has[a]+1 ,has[b] -1 ,1);
            la = max(lc ,max(la - a + 1,b - lb + 1));
            printf("%d\n",la);
//            printf("%d\n",query(a ,b ,1));
        }
    }
    return 0;
}

 

//TLE代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
const int nMax = 100010;
int num[nMax];
struct{
    int l,r,val,late;
}node[3*nMax];

void build(int left ,int right ,int u){
    node[u].l = left;
    node[u].r = right;
    node[u].late = 1;
    if(num[node[u].l] == num[node[u].r]){
        node[u].late = 0;
        return;
    }
    int m =(node[u].l + node [u].r)>>1;
    build(node[u].l , m ,u*2);
    build(m + 1 ,node[u].r ,u*2 + 1);
}
map<int,pair<int,int> >mp;
int query(int left ,int right ,int u){
    if(node[u].late == 0 || num[left] == num[right]){
        return right - left + 1;
    }
    int m =(node[u].l + node[u].r)>>1,aa;
    if(right <= m){
        aa=query(left ,right ,u*2);
//        cout<<left<<" "<<right<<" "<<aa<<endl;
        return aa;
    }
    if(left >= m+1){
        aa = query(left ,right ,u*2 + 1);
//        cout<<left<<" "<<right<<" "<<aa<<endl;
        return aa;
    }
    int a = query(left ,m ,u*2 );
    int b = query(m + 1 ,right , u*2 + 1);
    if(num[m] == num[m+1]){
        int la = max(mp[num[m]].first ,left);
        int lb = min(mp[num[m]].second ,right);
//        cout<<left<<" "<<right<<" "<<max((lb - la + 1),max(a,b))<<endl;
        return max((lb - la + 1),max(a,b));
    }else{
//        cout<<left<<" "<<right<<" "<<max(a,b)<<endl;
        return max(a,b);
    }
}
int main(){
    int n ,m ,a ,b ,i;
    while(scanf("%d",&n)!=EOF && n){
        scanf("%d",&m);
        num[0] = 100001;
        for(i = 1 ;i <= n ;i++ ){
            scanf("%d",&num[i]);
            if(num[i] != num[i-1]){
                mp[num[i]].first = i;
                mp[num[i]].second = i;
            }else{
                mp[num[i]].second = i;
            }
        }
        build(1 ,n ,1);
        while(m -- ){
            scanf("%d%d",&a,&b);
            printf("%d\n",query(a ,b ,1));
        }
    }
    return 0;
}