oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1995 噁爛的壓常數題，吳勝福居然原本官方解答是自己手寫3bytes整數，有夠可怕，好加在鄭天鈞夠聰明，讓我們免於這種可怕的地獄。 他的做法是建立一個Sparse Table，然而我們會發現我們正常sparse table會用掉$O(n log n)$記憶體的原因是因為我們要可以應付在線詢問，然而像這題離線的其實可以用$O(n)$的記憶體就好了，而少掉那$logn$也可簡單，就是你每次用完一條就丟掉，因為建立某一條的時候就可以把符合那條區間的詢問全部算好。此外我這裡因為沒把詢問排序好是因為若排序好就要多一條的記憶體來記錄原本誰是誰，所以只好讓詢問退化成$logN$，每建好一條就把所有詢問檢查過一遍。 #include <cstdio> #include <algorithm> using namespace std; const int N = 2500000 + 1; const int M = 1000000 + 1; int L[M], R[M], arr[N]; int main(){ int n, m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&L[i],&R[i]); L[i]--; R[i]--; } for(int i=0;i<n;i++) scanf("%d",&arr[i]); for(int j=0;(1<<j)<=n;j++){ for(int q=0;q<m;q++){ if(R[q]==-1) continue; int logN = 31-__builtin_clz(R[q]-L[q]+1); if(j!=logN) continu...

題目連結: http://tioj.infor.org/problems/1338 先小抱怨個，我因為通常都比較節省記憶體(?所以原本sparse table用vector array，結果卻因為push_back而被一直卡到時限(這題有夠緊的阿QAQ)，還有我不小心算錯範圍...。 正題:首先很明顯的可以知道若$gcd(C_{[L,R)})=C_k$（$L\leq k #include <algorithm> #include "lib1338.h" typedef long long lld; using std::min; using std::__gcd; lld minSTable[21][1000005]; lld gcdSTable[21][1000005]; void init(int N, lld arr[]){ int obov=0; for(int i=0;i<N;i++,obov++){ minSTable[0][obov]=arr[i]; gcdSTable[0][obov]=arr[i]; } for(int i=1;(1<<i)-1<N;i++){ obov=0; for(int j=0;(1<<i)+j-1<N;j++,obov++){ lld mA = minSTable[i-1][j]; lld mB = minSTable[i-1][j+(1<<(i-1))]; lld gA = gcdSTable[i-1][j]; lld gB = gcdSTable[i-1][j+(1<<(i-1))]; minSTable[i][obov]=min(mA,mB); gcdSTable[i][o...

題目連結: http://tioj.infor.org/problems/1871 裸區間極值題(RMQ)，寫個sparse table就好了，這裡附上個我自己debug用時用的lib1871.h lib1871.h #include <utility> #include <stdio.h> namespace futa{ int size; int *arr; int q; int init(){ scanf("%d",&size); arr = new int[size]; return size; } int* momo_gives_you_list_of_futa(){ for(int i=0;i<size;i++){ scanf("%d",&arr[i]); } return arr; } int momo_tells_you_q(){ scanf("%d",&q); return q; } std::pair<int,int> momo_asks(){ int l,r; scanf("%d %d",&l,&r); return std::make_pair(l,r); } void you_tell_momo(int a){ printf("ANS:%d\n",a); } } Main Code: #include "lib1871.h" #include <utility> #in...