題目鏈接

給一個非遞減數列， n個數， m個詢問， 每個詢問給出區間[L, R]， 求這個區間里面出現次數最多的數的次數。

非遞減數列， 這是最關鍵的一個條件...

需要保存一個區間最左邊的數， 最右邊的數， 最長前綴， 最長后綴， 和這個區間里面次數最多的數的次數。

一個區間出現最多的數的次數， 應該是左區間和右區間里面取一個最大值。 如果左區間最右邊的數和右區間最左邊的數相同， 還需要判斷這個數左右區間加起來的數量是否大于最大值。

合并的時候需要判斷左區間最右邊的數和右區間最左邊的數是否相同， 具體看代碼。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 1e5+5; 20 int lnum[maxn<<2], rnum[maxn<<2], maxx[maxn<<2], pre_max[maxn<<2], suf_max[maxn<<2]; 21 void pushUp(int rt, int m) { 22 maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]); 23 lnum[rt] = lnum[rt<<1]; 24 rnum[rt] = rnum[rt<<1|1]; 25 suf_max[rt] = suf_max[rt<<1|1]; 26 if(suf_max[rt] == (m>>1)&&lnum[rt<<1|1] == rnum[rt<<1]) //如果左區間最右邊的數和右區間最左邊的數相等 27 suf_max[rt] += suf_max[rt<<1]; //并且左區間的后綴長度等于這段區間的長度 28 pre_max[rt] = pre_max[rt<<1]; 29 if(pre_max[rt] == m-(m>>1) && rnum[rt<<1] == lnum[rt<<1|1]) 30 pre_max[rt] += pre_max[rt<<1|1]; 31 if(lnum[rt<<1|1] == rnum[rt<<1]) 32 maxx[rt] = max(maxx[rt], pre_max[rt<<1|1]+suf_max[rt<<1]); 33 } 34 void build(int l, int r, int rt) { 35 if(l == r) { 36 scanf("%d", &lnum[rt]); 37 rnum[rt] = lnum[rt]; 38 maxx[rt] = pre_max[rt] = suf_max[rt] = 1; 39 return ; 40 } 41 int m = l+r>>1; 42 build(lson); 43 build(rson); 44 pushUp(rt, r-l+1); 45 } 46 int query(int L, int R, int l, int r, int rt) { 47 if(L<=l&&R>=r) { 48 return maxx[rt]; 49 } 50 int m = l+r>>1; 51 if(R<=m) 52 return query(L, R, lson); 53 if(L>m) 54 return query(L, R, rson); 55 int tmp1 = query(L, m, lson); 56 int tmp2 = query(m+1, R, rson); 57 int tmp3 = 0; 58 if(lnum[rt<<1|1] == rnum[rt<<1]) 59 tmp3 = min(pre_max[rt<<1|1], R-m)+min(suf_max[rt<<1], m-L+1); 60 return max(tmp1, max(tmp2, tmp3)); 61 } 62 int main() 63 { 64 int n, m; 65 while(cin>>n&&n) { 66 cin>>m; 67 build(1, n, 1); 68 while(m--) { 69 int x, y; 70 scanf("%d%d", &x, &y); 71 printf("%d\n", query(x, y, 1, n, 1)); 72 } 73 } 74 return 0; 75 }

?

轉載于:https://www.cnblogs.com/yohaha/p/5067773.html

總結

以上是生活随笔為你收集整理的hdu 1806 Frequent values 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。