oToToT的code收藏區

題目連結: https://codeforces.com/contest/1051/problem/F 煩人的題目，一開始看到題的時候，忘記字串可以$(N, O(logN))$比較大小，然後想了想，想出一個什麼suffix array上二分搜之類的超噁比大小作法XD 後來發現可以$O(logN)$比大小之後，又因為hash碰撞卡了一段時間，才發現我p, q打反XD 總之，這題應該可以想到一個簡單的DP狀態$dp[i]$代表把後i個弄好的方法數，哪也很明顯的如果$s_i \neq \text{'0'}$，那就是找到一個區間的$j(i \le j \leq n)$使得$L \leq s_i...s_j \leq R$然後明顯$dp[i]=\sum_{j} dp[j]$，因為我們顯然只能把$s_i$跟那些人接在一起，而若$s_i = \text{'0'}$的情況也類似，所以現在變成我們要找到那些j，不過很明顯可以發現若a跟b差不多大，那他們的位數應該也差不多，所以我們只要去比較位數差不多的那個substring，就可以得知他是不是比較大了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; const int qs[] = { 1002939109, 1020288887, 1028798297, 1038684299, 1041211027, 1051762951, 1058585963, 1063020809, 1094763083, 1106384353, 1120154459, 1140593173, 1147930723, 1172520109, 1183835981, 1187659051, 1241251303, 1247184097, 1255940849, 1272759031, 1287027493, 1288511629, 1294632499, 1312650799, 1314753281, 1320080669, 1321970357, 1333133947, 1337684419, 1353508067, 1358715989, 1364961029, 1366

題目連結: https://tioj.infor.org/problems/1941 這題應該可以輕鬆想到$O(N^2)$的DP方式，同時也會發現那樣子太慢。 仔細觀察DP的表格後，發現他是一個單調的表格，也就是由左至右遞增，同時由下至上遞增，接著研究一下每個轉移對DP表格的貢獻，發現他必定會將他自己那個區間的DP值+1，而後面則為了要維護單調的性質，會再跟他取max。 那這類題目，其實我們可以維護每一段的DP值，每次加入一個新的轉移來源後，也代表加入了一個斷點，但是同時也有可能把自身後面的斷點吃光光。 所以複雜度會是$O(N log N)$，因為每個斷點只會出現跟消失一次，而單次新增跟刪除了複雜度都是$O(log N)$ #include <bits/stdc++.h> using namespace std; class BIT{ private: int n; vector<int> arr; inline int lowbit(int x){return x&(-x);} void modify(int p, int x){ for(;p;p-=lowbit(p)) arr[p] += x; } public: void init(int n_){ n = n_; arr.clear(); arr.resize(n); } void modify(int l, int r, int v){ modify(l, -v); modify(r, v); } int query(int x){ int ret = 0; for(;x<n;x+=lowbit(x)) ret += arr[x]; return ret; } } bit; set<int> st; int main(){ int n; scanf("%d", &n); bit.init(n+1); st.insert(n); for(int i=0;i<n;i++){ int l, r; scanf("%d%d", &l, &r); st.insert(l);