題意：
? ? ? 給你一個初始序列，初始序列長度n,分別為1 2 3 4 5 ....n,有兩種操作
（1）D l r 把l_r之間的數據都復制一遍 1 2 3 4 5 6 D 2 4 = 1 2 2 3 3 4 4 5 6
（2）Q l r 詢問lr之間的數字出現的最大次數 1 2 2 3 3 4 4 4 5 Q 1 3 = 2


思路：
? ? ? 這個題目可以用線段樹來解決，我們可以建一棵樹1--n的，這個題目要注意一點就是無論怎么復制，所有的數字依然是連續的，對于線段樹的每一個節點，我們有兩個權值，區間元素個數，區間元素出現次數最大值，這樣每次遇到一個區間，我們就把這個區間拆成三部分，左邊的點，中間部分，右邊的一個點，兩邊的用點更新，中間部分用段更新，每次給一個范圍我們就可以根據這個范圍找到范圍所涉及到的數字范圍（1--n），比如

11223344445555 現在給出范圍3 13 =則找到的范圍是2-5，這樣點2,5單獨處理，3-4用段更新處理，找的過程中我用的是深搜找的，對于每個點的信息，其實可以再深搜里直接一起找出來，但是我自己當初沒想到，直接又多寫了一個斷詢問，雖然麻煩點，但也AC了，具體的看代碼吧！

#include<stdio.h> #include<string.h>#define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1 #define N_node 200000 __int64 sum[N_node] ,max[N_node] ,mark[N_node];__int64 maxx(__int64 x ,__int64 y) {return x > y ? x : y; }void Pushup(__int64 t) {sum[t] = sum[t<<1] + sum[t<<1|1];max[t] = maxx(max[t<<1] ,max[t<<1|1]); }void Pushdown(__int64 t) {if(mark[t]){mark[t<<1] += mark[t];mark[t<<1|1] += mark[t];sum[t<<1] <<= mark[t];sum[t<<1|1] <<= mark[t];max[t<<1] <<= mark[t];max[t<<1|1] <<= mark[t]; mark[t] = 0;} }void BuidTree(__int64 l ,__int64 r ,__int64 t) {max[t] = sum[t] = mark[t] = 0;if(l == r){max[t] = sum[t] = 1;return;}__int64 mid = (l + r) >> 1;BuidTree(lson);BuidTree(rson);Pushup(t); }void Update_1(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b) {//點更新 if(l == r){max[t] += b;sum[t] += b;return;}Pushdown(t);__int64 mid = (l + r) >> 1;if(a <= mid) Update_1(lson ,a ,b);else Update_1(rson ,a ,b);Pushup(t); }void Update_2(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b) {//段更新 if(a <= l && b >= r){sum[t] *= 2;max[t] *= 2;mark[t] ++;return;}Pushdown(t);__int64 mid = (l + r) >> 1;if(a <= mid) Update_2(lson ,a ,b);if(b > mid) Update_2(rson ,a ,b);Pushup(t); }__int64 Query_1(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b) {//段查找，區間最大值 if(a <= l && b >= r)return max[t];Pushdown(t);__int64 mid = (l + r) >> 1;__int64 now = 0;if(a <= mid) now = Query_1(lson ,a ,b);if(b > mid) now = maxx(now ,Query_1(rson ,a ,b));return now; }__int64 Query_2(__int64 l ,__int64 r ,__int64 t ,__int64 a ,__int64 b) {//段查找，區間和 if(a <= l && b >= r) return sum[t];Pushdown(t);__int64 mid = (l + r) >> 1;__int64 now = 0;if(a <= mid) now = Query_2(lson ,a ,b);if(b > mid) now += Query_2(rson ,a ,b);return now; }__int64 DFS_Find(__int64 l ,__int64 r ,__int64 t ,__int64 now ,__int64 ss) {//深搜查找范圍所在的點 if(l == r) return l;Pushdown(t);__int64 mid = (l + r) >> 1;if(now <= sum[t<<1] + ss)return DFS_Find(lson ,now ,ss);else return DFS_Find(rson ,now ,ss + sum[t<<1]); }int main () {int t ,cas = 1 ,n ,m ,i;__int64 a ,b;char str[5];scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);BuidTree(1 ,n ,1);printf("Case #%d:\n" ,cas ++);for(i = 1 ;i <= m ;i ++){scanf("%s %I64d %I64d" ,str ,&a ,&b);__int64 l = DFS_Find(1 ,n ,1 ,a ,0);__int64 r = DFS_Find(1 ,n ,1 ,b ,0);if(str[0] == 'D'){if(l == r){Update_1(1 ,n ,1 ,l ,b - a + 1);continue;}__int64 ls = Query_2(1 ,n ,1 ,1 ,l) - a + 1;__int64 rs = b - Query_2(1 ,n ,1 ,1 ,r - 1);Update_1(1 ,n ,1 ,l ,ls);Update_1(1 ,n ,1 ,r ,rs);if(r - l > 1)Update_2(1 ,n ,1 ,l + 1 ,r - 1);}else{if(l == r){printf("%I64d\n" ,b - a + 1);continue;}__int64 now = 0;__int64 ls = Query_2(1 ,n ,1 ,1 ,l) - a + 1;__int64 rs = b - Query_2(1 ,n ,1 ,1 ,r - 1); if(r - l > 1) now = Query_1(1 ,n ,1 ,l + 1 ,r - 1);if(now < ls) now = ls;if(now < rs) now = rs;printf("%I64d\n" ,now);}}}return 0; }

總結

以上是生活随笔為你收集整理的hdu4973 线段树（题目不错，用了点，段，更新查找还有DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

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