POJ 3368 Frequent values（線段樹）

這一個題目是求一個區間內重復數字的最大次數。

這題有一個特點，數字是遞增滴，相同的數字肯定是連續的。

將相同的數字看做一個部分，hash保存每個數字屬於哪個部分。對所有的部分建一顆二叉樹，保存此區間內最大的重復數字的個數。

查詢的時候分3中情況

1 在同一個部分，直接 尾 - 頭 + 1就是結果

2 只差一個部分，分開算，在各個部分裡面重復多少次，比較一下

3 中間有很多個部分，那麼可以先根據2計算出兩頭的，在通過二叉樹查詢最大的重復數字個數

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <set>   
#include <map>   
#include <queue>   
#include <stack>   
#include <climits>//形如INT_MAX一類的   
#define MAX 100050   
#define INF 0x7FFFFFFF   
#define REP(i,s,t) for(int i=(s);i<=(t);++i)   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define L(x) x<<1   
#define R(x) x<<1|1   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛   
using namespace std;  
  
struct node {  
    int l,r,mid,value;  
} tree[4*MAX];  
  
struct point {  
    int st,end;  
} cnt[MAX];  
int data[MAX],vis[MAX],maxx;  
  
void up(int num) {  
    tree[num].value = max(tree[L(num)].value ,tree[R(num)].value);  
}  
  
void build(int l,int r,int num) {  
    tree[num].l = l;  
    tree[num].r = r;  
    tree[num].mid = (l+r) >> 1;  
    if(l == r) {  
        tree[num].value = cnt[l].end - cnt[l].st + 1;  
        return ;  
    }  
    build(l,tree[num].mid,L(num));  
    build(tree[num].mid+1,r,R(num));  
    up(num);  
}  
  
int query(int l,int r,int num) {  
    if(l <= tree[num].l && r >= tree[num].r) {  
        return tree[num].value;  
    }  
    if(r <= tree[num].mid) {  
        return query(l,r,L(num));  
    } else if( l > tree[num].mid) {  
        return query(l,r,R(num));  
    } else {  
        return max(query(tree[num].mid+1,r,R(num)),query(l,tree[num].mid,L(num)));  
    }  
}  
  
void test(int n) {  
    for(int i=1; i<=3*n; i++) {  
        printf("l:%d r:%d value:%d\n",tree[i].l,tree[i].r,tree[i].value);  
    }  
}  
int main()  {  
    int i,n,q,a,b;  
    while(scanf("%d",&n)) {  
        if(n == 0)  
            return 0;  
        scanf("%d",&q);  
        for(i=1; i<=n; i++) {  
            scanf("%d",&data[i]);  
        }  
        memset(vis,0,n);  
        int t = 1;  
        cnt[t].st = 1;  
        vis[1] = t;  
        if(n == 1) {  
            cnt[t].end = 1;  
        }  
        for(i=2; i<=n; i++) {  
            if(data[i] != data[i-1]) {  
                cnt[t].end = i-1;  
                t++;  
                cnt[t].st = i;  
                vis[i] = t;  
            } else {  
                vis[i] = t;  
            }  
        }  
        cnt[t].end = n;  
        vis[n] = t;  
  
        build(1,t,1);  
        //test(t);   
        for(i=1; i<=q; i++) {  
            scanf("%d%d",&a,&b);  
            if(vis[a] == vis[b]) {  
                printf("%d\n",b - a+1);  
                continue;  
            }  
            if(vis[b] - vis[a] == 1) {  
                printf("%d\n",max(cnt[vis[a]].end - a+1,b - cnt[vis[b]].st + 1));  
                continue;  
            }  
            int p = max(cnt[vis[a]].end - a+1,b - cnt[vis[b]].st + 1);  
            printf("%d\n",max(p,query(vis[a]+1,vis[b]-1,1)));  
        }  
    }  
    return 0;  
}  

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;

struct node {
    int l,r,mid,value;
} tree[4*MAX];

struct point {
    int st,end;
} cnt[MAX];
int data[MAX],vis[MAX],maxx;

void up(int num) {
    tree[num].value = max(tree[L(num)].value ,tree[R(num)].value);
}

void build(int l,int r,int num) {
    tree[num].l = l;
    tree[num].r = r;
    tree[num].mid = (l+r) >> 1;
    if(l == r) {
        tree[num].value = cnt[l].end - cnt[l].st + 1;
        return ;
    }
    build(l,tree[num].mid,L(num));
    build(tree[num].mid+1,r,R(num));
    up(num);
}

int query(int l,int r,int num) {
    if(l <= tree[num].l && r >= tree[num].r) {
        return tree[num].value;
    }
    if(r <= tree[num].mid) {
        return query(l,r,L(num));
    } else if( l > tree[num].mid) {
        return query(l,r,R(num));
    } else {
        return max(query(tree[num].mid+1,r,R(num)),query(l,tree[num].mid,L(num)));
    }
}

void test(int n) {
    for(int i=1; i<=3*n; i++) {
        printf("l:%d r:%d value:%d\n",tree[i].l,tree[i].r,tree[i].value);
    }
}
int main()  {
    int i,n,q,a,b;
    while(scanf("%d",&n)) {
        if(n == 0)
            return 0;
        scanf("%d",&q);
        for(i=1; i<=n; i++) {
            scanf("%d",&data[i]);
        }
        memset(vis,0,n);
        int t = 1;
        cnt[t].st = 1;
        vis[1] = t;
        if(n == 1) {
            cnt[t].end = 1;
        }
        for(i=2; i<=n; i++) {
            if(data[i] != data[i-1]) {
                cnt[t].end = i-1;
                t++;
                cnt[t].st = i;
                vis[i] = t;
            } else {
                vis[i] = t;
            }
        }
        cnt[t].end = n;
        vis[n] = t;

        build(1,t,1);
        //test(t);
        for(i=1; i<=q; i++) {
            scanf("%d%d",&a,&b);
            if(vis[a] == vis[b]) {
                printf("%d\n",b - a+1);
                continue;
            }
            if(vis[b] - vis[a] == 1) {
                printf("%d\n",max(cnt[vis[a]].end - a+1,b - cnt[vis[b]].st + 1));
                continue;
            }
            int p = max(cnt[vis[a]].end - a+1,b - cnt[vis[b]].st + 1);
            printf("%d\n",max(p,query(vis[a]+1,vis[b]-1,1)));
        }
    }
    return 0;
}