e406: Binary Indexed Tree 練習題
Tags : BIT RMQ
Accepted rate : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-01 11:29

Content

普二信的阿華 想要練習 bit (Fenwick Tree),因為剛練習,先不做有變化的,請小西幫忙寫一個題目練習。

就是想練習以 Binary Index Tree 解 單點更新、區間求和, 可是又不想太因為 I/O 影響算法,所以讀入少許資料,跑個產生測資的小函式產生的測資放陣列

有N個正整數A[1...N], 5<N<=10^6, 0<A[i]<1000
有Q個指令,格式為 c x y, 分別放在陣列 C[1..Q]、X[1..Q]、Y[1..Q], 5<Q<=10^5
其中 C[i] X[i] Y[i] 中的C[i]只有0及1 , 1=<x,y<=N 如下說明:
0 x y 代表將 A[x]的值更新為 y,而 1 x y 代表要查詢 A[x]~A[y]的和{含A[x]及A[y]}

對於 1 x y 請輸出一列,只有一個數字 A[x]~A[y]的和 mod m 的值

 
=====================需加入 產生測資的部份 {小西只會C++}
const int MaxN = 1000000+5;
const int MaxQ = 100000+5;
int A[MaxN];
bool C[MaxQ];
int X[MaxQ] , Y[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;
        if(C[i]) Y[i] = X[i]+ ( (A[i]<<3)+(A[j]<<5)+m )%( N-X[i]+1 );
       else Y[i] = ((A[i]<<3)+(A[j]<<5))%m+1;
   }
}
============================== 雖然有點醜,應該可以降低 I/O速率影響吧
以範例輸入的資料讀入後,呼叫 gen_dat()之後,產生的資料為
A[1..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] 如以下15列,你需由陣列中叫用。
0 18 378
0 14 96
0 17 418
0 12 133
1 4 13
1 5 6
1 18 23
1 23 23
1 1 6
1 24 25
1 21 23
0 8 71
1 3 25
0 8 210
1 21 21
=========== 以上資料及指令的處理結果如下說明
第1~第4指令分別更新 A[18]=378、 A[14]=96、A[17]=418、A[12]=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 351 96 359 112 418 378 147 106 512 458 185  79 330
接著第5個指令查 A[4]~A[13]的和,即 78 + 91 + 23 + 45 + 67 + 89 + 111 + 311 + 133 + 351 = 1299 再 mod 541 => 217
第6個指令查 A[5]~A[6]的和,即 91+23 = 114 、 第7查詢A[18]~A[23]的和,即 378+147+106+512+458+185 = 1786%541 => 163
... 第12個指令更新 A[8]=71 , 接著 第13個查 A[3]~A[25]的和
56+78+91+23+45+71+89+111+311+133+351+96+359+112+418+378+147+106+512+458+185+79+330=4539再mod541 => 211
第14更新 A[8]=210 , 接著 第15個查 A[21]~A[21]的和 為 512

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
217
114
163
185
294
409
73
211
512
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
BIT RMQ
出處:
[管理者:
p3a_owhj (阿普二信)
]


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