## Spring Practices 03 心得&題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 前言

這次難了好多... D 好難賽裡沒寫出來，沒有人賽中破台。

### pA

排序 Pair 們，依照起點來排序，如果能排我們就暫時放入那個區間，然後記得他現在的尾端，而這裡因為我們已經把他依起點排序，所以在沒有這個活動的情況下後面的一定是都排得進去的。

然後如果發現結束時間比目前暫時放進去的早的話，那就把他替換掉。

bottle-neck 是排序，時間複雜度 $O(nlgn)$。

Code :

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;
mt19937 rng(114514);
const int mod1 = 998244353;
int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

bool cmp(pii f, pii s){
    return f.f < s.f;
}
int main() {
    IOS;
    int n;
    int x, y;
    cin >> n;
    vector<pii> S(n);
    for(int i = 0; i < n;i++){
        cin >> x >> y;
        S[i] = make_pair(x,y);
    }
    sort(S.begin(), S.end(), cmp);

    int last = -1, ans = 0 ;
    for(int i = 0; i < n; i++){
        
        if(last > S[i].f){
            last = min(last, S[i].s);
        }
        else{
           ans ++;
           last = S[i].s;
        }
    }
    cout << ans << '\n';
}

### pB

紀錄說 「過小的」最大值、 「過大的」 最小值，以及正確答案的值，看關係合不合理就可以了。

時間複雜度 O(line)
Code :

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;
mt19937 rng(114514);
const int mod1 = 998244353;
int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

bool cmp(pii f, pii s){
    return f.f < s.f;
}
int main() {
    IOS;
    string nn;
    int mux = 0, mun = 11, right = -1, n;
    string s, s2;
    while(1){
        cin >> nn;
        n = stoi(nn);
        if(n == 0) break;
        cin >> s >> s2;
        if(s2 == "on"){
            if(mux < n && n < mun){
                cout << "Stan may be honest\n";
            }
            else{
                cout << "Stan is dishonest\n";
            }
            mux = 0; mun = 11; right = -1;
            
        }
        if(s2 == "low"){
            mux = max(mux, n);
        }
        if(s2 == "high"){
            mun = min(mun, n);
        }
    }
}

### pC

模擬一個 stack 就可以了，拿到左括號是加入就 push 進去，拿到右就 pop，然後看一不一樣。

時間複雜度 $O(N)$。

我沒發現有可能有輸入是整個空的，用```cin string```會吃不到，吃一堆 WA。

然後我吃毒用 ```gets()``` 準備被紀老師當掉，後來才知道有 ```cin.ignore()``` ，請大家不要學我這個小丑，請用別的來輸入。

Code :

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;
mt19937 rng(114514);
const int mod1 = 998244353;
int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

bool cmp(pii f, pii s){
    return f.f < s.f;
}
int main() {
    //IOS;
    char s[1024];
    int t, n, ptr = -1, maxn = 1024;
    int st[maxn];
    gets(s);
    t = stoi(s);
    while(t--){
        gets(s);
        
        ptr = -1;
        for(int i = 0; i < maxn; i++){
            st[i] = 0;
        }
        int ans = 1;
        for(int i = 0 ; s[i] != '\0'; i++){
            if(s[i] == '('){
                st[++ptr] = 1;
            }
            if(s[i] == '['){
                st[++ptr] = 2;
            }
            if(s[i] == ')'){
                if(ptr <= -1) {
                    ans = 0; break;
                }
                if(st[ptr] != 1){
                    ans = 0; break;
                } 
                ptr --; 
            }
            if(s[i] == ']'){
                if(ptr <= -1) {
                    ans = 0; break;
                }
                if(st[ptr] != 2){
                    ans = 0; break;
                } 
                ptr --;
            }
           // cout << ptr << '\n';
        }
        if(ans && (ptr == -1)){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
}

### pD

可以發現這題的輸入長得非常畸形。

其實不用想太多，這不是數學家題，題目只是找理由說讓你覺得這 $H$ 生成方式很合理 (?，阿為什麼他不好好輸入只是因為輸入量有點大，用 cin 不用 fread 之類的可能會 TLE。

像下面 [這題](https://atcoder.jp/contests/abc344/tasks/abc344_g) 就講得很明白，跟你說 $Q$ 大的感人所以請你自己生。

那反正就是照題目說的產生 $G, H$，然後對所有滿足 $A \times B$ 的 $H$ 的子陣列做事。

如果直接照題目的做，對 $AB$ 個格子取最小，時間複雜度是 $O(NMAB)$，看似會 TLE，實際真的會 TLE，所以要想更好的方法。

那這個二維的我覺得很麻煩，所以我想先做一維的，那問題會變這樣 :

> 給你一個長度 $n$ 的非負整數序列 $a$ 和 $k$，求 $MIN(a_1, a_2, ..., a_k)+MIN(a_2, a_3, ..., a_{k+1})+...+MIN(a_{n-k+1}, a_{n-k+2}, ..., a_n)$

我們試著找比 $O(n^2)$ 更好的方法 :

我們維護一個 deque ，這個 deque 裡面裝 pair $(x,y)$，$x$ 代表放進來的時間、$y$ 代表他的值，我們希望他能有個單調 (monotone) 性質， 從左到右 $x$ 能越來越大、而 $y$ 也越來越大。

考慮以下測資 :

$(n, k) = (5,2)$

一開始我們希望我們先把前兩個值放進去，從第三個開始要注意左邊的值要拿掉
那麼，我們的 deque 會做下列事情 :


然後因為我們維護了最小的值出現在左邊，所以最左邊的 $1$ 是答案!

那我們接著放入第三個元素 :


接著我們一樣從左邊拿答案，但是注意最左邊的已經超出範圍了! (編號 1 現在在我們要的範圍外面了)，我們把它丟掉，然後取下一個，也就是 $2$。


下一個是放入第四個元素，一樣的過程 :


最後放入第五個元素，但因為它滿小的，所以不太一樣喔 !

我們不斷檢查右端的元素是否比它大，是的話就丟掉，直到找到有人比他小又或著 deque 變空的。


維護 deque 的總時間複雜度就是 $O(n)$。

--------------------------

回到原題，二維的，我們想一個小性質 :

這兩個是不是根本一樣的(各顏色代表該區塊最小值) ?

確實其實是一樣的。

那我們可以用前面的維護 $n$ 個這樣的長條東西，用前面一維的方法應該就可以 $O(m)$ 維護一個長條從左掃到最右邊，每一次的值了吧 !

維護了這個值後，每個長條化成一個值而已，那這個問題想成另個方向就又變成另一個相同的一維的問題。

最後我們可以 $O(nm)$ 解決。

Code :

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;
mt19937 rng(114514);
const int mod1 = 998244353;
int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

bool cmp(pii f, pii s){
    return f.f < s.f;
}

int add(int i, int l, int r, int v, pii* q, int* pl, int* pr){
    while(v <= q[pr[i]].s && pl[i] <= pr[i]) pr[i]--;
    ++pr[i];
    q[pr[i]] = make_pair(r, v);
    while(l > q[pl[i]].f) pl[i]++;
    return q[pl[i]].s;
}

int main() {
    IOS;
    int n, m, a, b;

    cin >> n >> m >> a >> b;
    
    int nm = (n+5) * (m+5), sz = n+1, qsz = max(n,m) + 5;
    i64 g[nm];
    pii q[sz][qsz]; // q -> (idx, v) (monotone deque)
    int l[sz], r[sz]; // 0 -> whole 1~n -> a row
    int com[n+5];
    int h[n+5][m+5];
    i64 x, y, z, ans = 0;
    
    
    cin >> g[0] >> x >> y >> z;
    
    for(int i = 1; i < nm; i++){
        g[i] = (g[i-1] * x + y) % z; // cal g
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            h[i][j] = g[(i-1) * m + (j-1)]; // find h
        }
    }
    
    for(int i = 0; i < sz; i++){
        l[i] = 0;
        r[i] = -1;// init
    }
    
    for(int j = 1; j < b; j++){
        for(int i = 1; i <= n; i++){
            add(i, -1, j, h[i][j], q[i], l, r);
        }
    }
    
    for(int j = b; j <= m; j++){
        for(int i = 1; i <= n; i++){
            com[i] = add(i, j - b + 1, j, h[i][j], q[i], l, r);
        }
        
        l[0] = 0;
        r[0] = -1;// init
        
        for(int i = 1; i < a; i++){
            add(0, -1, i, com[i], q[0], l, r);
        }
        
        for(int i = a; i <= n; i++){
            ans += add(0, i - a + 1, i, com[i], q[0], l, r);
        }
    }
    cout << ans << '\n';
 
}

### pE

實作用 map (dict) 把字串轉成 id，就變成一個二維陣列排序題。

然後 Python 比較好做就用 Python 了。

時間複雜度 $O(NlgN+Q)$

Code (Python) :

# Author : rickytsung
n = int(input())
hsah = 0
dicc = {}
arr = []
for i in range(n):
  s = input().split(" ")
  if(dicc.get(s[0]) is None):
    dicc[s[0]] = hsah
    hsah += 1
    arr.append([])
  arr[dicc[s[0]]].append(int(s[1]))

for i in range(len(arr)):
  (arr[i]).sort()
  
q = int(input())
for i in range(q):
  s = input().split(" ")
  print(arr[dicc.get(s[0])][int(s[1])-1])