oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/1902 直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。 p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥 #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <utility> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); auto maxi = [](auto &a, auto b) { a = std::max(a, b); }; int n, q; std::cin >> n >> q; std::vector<uint32_t> a(1); std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a)); std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor()); struct Q { int l, r, id; Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {} }; static constexpr int K = 128; std::vector<std::vector<Q>> qs((n + K - 1) / K); for (int ...

題目連結: https://tioj.infor.org/problems/2027 不知道多久沒來這裡了XD，來提供一下兩個這題的做法。 一個是gamegame跟我講的做法，我覺得我應該以前都沒想過，所以紀錄一下這個有趣的作法。 這裡我們將一棵二元樹的節點集合用$\mathbb{T}$表示，並且定義幾個函數 $\text{lch}:\mathbb{T}\rightarrow\mathbb{T}, \text{lch}(x)=\text{left child of }x$ $\text{rch}:\mathbb{T}\rightarrow\mathbb{T}, \text{rch}(x)=\text{right child of }x$ $\text{sz}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{sz}(x)=\text{size of }x$ $\text{w}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{w}(x)=\min(\text{sz}(\text{lch}(x)), \text{sz}(\text{rch}(x)))$ 那首先有個引理：對於任意二元樹$T$都有$\displaystyle\sum_{u \in T}\text{w}(u) = \mathcal{O}(\text{sz}(T) \log \text{sz}(T))$，證明的部分就留給讀者好了(X) 白話文講一點就是如果有一個$N$個節點的二元樹，而我們對於他每個節點作的演算法都只跟那個節點小的子樹的大小有關的話，複雜度就會是$\mathcal{O}(N \log N \cdot \text{單一操作的複雜度} )$。 回到這題，可以發現如果一個區間$[L, R]$的最大值是$a_i$若且唯若$L \in [j, i]$（其中$j$是使得$j a_i$發生的最大的$j$）跟$R \in [i, j]$（其中$j$是使得$i a_i$發生的最小的$j$），而若是我們把這種性質拿去建成一棵二元樹（也就是讓可能的編號$L$都在$i$的左子樹，可能的編號$R$都在$i$的右子樹）的話我們就會拿到 笛卡爾樹 。 有了笛卡爾樹後，我們還需要一個支援插入、刪除、統計有多...

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(...

題目連結: http://tioj.infor.org/problems/1446 稍微想一下就會發現這題就等價於塞到trie後的DFS的順序，但是因為建棵trie有點麻煩，所以在想個兩下就會發現建棵trie再DFS其實跟你直接排序再扣掉相鄰的人的LCP等價，所以就這樣做吧XD #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; string ss[N]; int main(){ int n, ans=0; cin>>n; for(int i=0;i<n;i++){ cin>>ss[i]; ans+=ss[i].size(); } sort(ss, ss+n); for(int i=1;i<n;i++){ int sz = min(ss[i].size(), ss[i-1].size()); int lcp; for(lcp=0;lcp<sz and ss[i][lcp]==ss[i-1][lcp];lcp++); ans-=lcp; } cout<<ans*2+n<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/842/D 寫過類似的題目，一看到就認出來了XD。考慮把所有數字塞到bitwise的trie上，這樣xor一個數字時就變成交換左右子樹了，而且其實也不用真的把每個子樹都換過一遍，只要再走下去的時候看一下要誰當左右子樹即可。那這樣就只要在一棵樹上找mex值就好了，這也不難，只要維護一下每個子節點的大小，先看左子樹是不是空的，若是就直接回傳0，因為表示往左走都沒東東了，再看一下左子樹是不是滿的，若是就只能走右邊，不然就繼續走左子樹即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 300000 + 5; const int MEM = 20*N; class Trie{ private: struct node{ node *l, *r; int size; node(){l=r=nullptr;size=0;} }; node *root, pool[MEM]; int _mem; node* newnode(){ assert(_mem<MEM); pool[_mem]=node(); return &pool[_mem++]; } int size(node *x){return x?x->size:0;} void insert(int x, node *&cur, int d){ if(!cur) cur=newnode(); ...