e437: Segment Tree 練習2 + 區間修改
Tags : RMQ 線段樹
Accepted rate : 6人/6人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-01 09:41

Content

小華練完 e409 的 線段樹 解 單點更新、區間求最值, 還想練習 區間修改, 所以小西就又幫忙出了一題。
同樣的,又不想太因為 I/O 影響算法,所以讀入少許資料,
跑個產生測資的小函式gen_dat()產生的測資放陣列
有N個正整數A[1...N], 5<N<=10^6, 0<A[i]<1000
有Q個指令,格式為 c x y 或 c x y z, 分別放在陣列 C[1..Q]、X[1..Q]、Y[1..Q]、Z[1..Q], 5<Q<=10^5
其中 C[i] X[i] Y[i] Z[i] 中的C[i]只有0及1 , 1=<x,y,z<=N 如下說明:
0 x y z代表將 A[x]~A[y]這區間的值更新為 z,而 1 x y 代表要查詢 A[X]~A[Y] 和 mod m{sumA} 及 A[X]~A[Y]之中最大值maxA及最小值minA的差
對於 1 x y 請輸出一列,兩個數字 sumA , (maxA-minA) 以空格隔開

=====================需加入 產生測資的部份

const int MaxN = 1000000+5;
const int MaxQ = 100000+5;
int A[MaxN];
bool C[MaxQ];
int X[MaxQ] , Y[MaxQ], Z[MaxQ];
int k,m,N,Q;
void gen_dat()
{
   int i,j;
   for( i=k+1; i<=max(Q,N); ++i )
      A[i] = ( A[i-2]*97 + A[i-1]*3 )%m+1;
   for(i=1,j=max(Q,N); i<=Q; ++i,--j)
   {
      C[i] = A[i]&1;
      X[i] = (A[i]+A[j])%N+1;
      Y[i] = X[i]+ ( (A[i]<<3)+(A[j]<<5)+m )%( N-X[i]+1 );
      if(!C[i]) Z[i] = ((A[i]<<3)+(A[j]<<5))%m+1;
   }
}

============================== 雖然有點醜,應該可以降低 I/O速率影響吧

以範例輸入的資料讀入後,呼叫 gen_dat()之後,產生的資料為
A[1..25]的值如下列
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25]
12 34 56 78 91 23 45 67 89 111 311 340 351 492 359  112 536  30 147 106 512 458 185  79 330
又產生的 15個指令 C[i] X[i] Y[i] Z[i] 如以下15列,你需由陣列中叫用。
0 18 23 378
0 14 19 96
0 17 23 418
0 12 13 133
1 4 13
1 5 6
1 18 23
1 23 23
1 1 6
1 24 25
1 21 23
0 8 23 71
1 3 25
0 8 11 210
1 21 21
=========== 以上資料及指令的處理結果如下說明
第1~第4指令分別更新 A[18]~A[23]=378、 A[14]~A[19]=96、A[17]~A[23]=418、A[12]~A[13]=133, 更新後A陣列如下:
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14][15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25]
12 34 56 78 91 23 45 67 89 111 311 133 133  96  96  96 418 418 418 418 418 418 418  79 330
接著第5個指令查 A[4]~A[13]的和=78+91+23+45+67+89+111+311+133+133=1081再mod541 => 540 , 極值差,即 311-23 = 288 、
第6個指令查 A[5]~A[6]的和 =91+23 => 114 , 極值差,即 91-23 = 68 、
第7查詢A[18]~A[23]的和 =418+418+418+418+418+418=2508%541=>344 , 極值差: 418-418 = 0、
, ... , 第12個指令更新 A[8]~A[23]=71 ,
接著 第13個查 A[3]~A[25]和=56+78+91+23+45+71+71+71+71+71+71+71+71+71+71+71+71+71+71+71+71+79+330=1838%541=>215 , 極值差:330-23 = 307
第14更新 A[8]~A[11]=210 , 接著 第15個查 A[21]~A[21]的和為 71 , 極值差,即 71-71 = 0

 

 

Input

第1列有兩個正整數 k m ,第2列有 k 個正整數, 請讀入放至 A[1..k]
接著讀入第3列的 N Q 兩個正整數,呼叫所附的產生測資程式 gen_dat()
以上 5<k<=n, 5<m<1000;
然後就是解題,依C,X,Y陣列的值 執行更新或查詢

 

Output

對於每一個查詢輸出 兩個數字以空白隔開: 區間和 mod m 及 區間中(最大值-最小值)

 

Sample Input
10 541
12 34 56 78 91 23 45 67 89 111
25 15
Sample Output
540 288
114 68
344 0
418 0
294 79
409 251
172 0
215 307
71 0
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1K
公開 測資點#3 (25%): 1.0s , <1K
Hint :
Tags:
RMQ 線段樹
出處:
[管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」