# 競程班第四堂社課
[TOC]

## 開始之前

請先看過[這份講義](https://hackmd.io/@tcirc-40th/home/%2FIkrdjh4bQum_Ub1OtNP8xA)的vector部分
記得繳社費

## 位元運算子

和[布林運算子](https://hackmd.io/@tmting39/rJdk5ioxp#%E5%B8%83%E6%9E%97%E9%81%8B%E7%AE%97%E5%AD%90)不一樣。

|$a$|$b$|$a\& b$|$a\|b$|$a^\wedge b$|
|---|---|---|---|---|
|0|0|0|0|0|
|0|1|0|1|1|
|1|0|0|1|1|
|1|1|1|1|0|

位元運算是將兩個數字分別用二進位表示，位元分別進行運算。

例如$9_{(10)}=1001_{(2)}$，$5_{(10)}=101_{(2)}$，則$9_{(10)}|5_{(10)}=1101_{(2)}=13_{(10)}$。

### 關於XOR

可以想成 看兩個位元一不一樣 或 沒有進位的加法。能應用在判斷奇偶性。

以下用$\oplus$表示位元XOR

有一個重要的性質
$$
a\oplus a =0
$$
在數學上，我們會稱$0$是$\oplus$運算的**單位元素**(任何數對單位元素做運算後都不會變)。而一個數和他的**反元素**做運算後會變成單位元素，在XOR運算中，$a$的反元素正好就是$a$。

例如:若
$$
a\oplus b=c
$$
則
$$
a=c\oplus b
$$

## 對答案二分搜

就是帶答案，並縮小範圍

### 範例


若你懶得算，想要從選項代回去，可以從中間的開始代，再看要往小的猜還是大的猜。

先把選項排序: $\{1200,1500,1800,3000\}$。

選中間的開始猜，假設這裡先從1500開始，會發現:
$$
1500\times 0.5 < \frac{1}{2} \times 0.02 \times 300^2
$$

這表示我們要往更大的數字猜。
:::warning
更好的例子是估計平方根
:::

---
[CSES Factory Machines](https://cses.fi/problemset/task/1620)
[題解](https://hackmd.io/@tmting39/rJr8b_jza)

## 前綴和

### 範例
[Static Range Sum Queries](https://cses.fi/problemset/task/1646)

題目大意:
給一個長度$N$的陣列$A$，及$Q$筆詢問，回答$\sum_{i=l}^{r} x_i$。

- $1 \le N,Q \le 2 \cdot 10^5$
- $1 \le A_i \le 10^9$
- $1 \le l \le r \le n$

### 直覺做法

暴力回答詢問

#include<bits/stdc++.h>
#define ll long long
using namespacec std;
int main(){
    int n,q;
    cin>>q;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    while(q--){
        ll ans=0;
        int l,r;
        cin>>l>>r;
        l--;
        r--; // 0-based
        for(int i=l;i<=r;i++) ans+=a[i];
        cout<<ans<<endl;
    }
    return 0;
}

我們來分析一下複雜度，總共有$Q$筆詢問，而每次回答詢問最多都需要遍歷大小為$N$的陣列。所以總時間複雜度為$\text{O}(NQ)$，很明顯無法通過時限。

### 觀察
可以先試著把問題簡化:假設所有的$a$都是$0$。

我們可以一開始就把所有的答案存到陣列裡(因為最多只會有$N$種不同的詢問)，而這非常的容易。
可以開一個陣列$ans$，$ans_i$表示從$A_0$到$A_i$的和，馬上就可以發現$ans_i=ans_{i-1}+A_i$。所以可以在$\text{O}(N)$的時間完成預處理，總時間複雜度$\text{O}(N+Q)$。

接著來想想看當$a\neq 0$的時候該怎麼做

$\sum_{i=l}^{r} a_i=\sum_{i=0}^{r}a_i-\sum_{i=0}^{l-1}a_i$。
藍色=黃色-綠色

### 作法

對於一個數列$A$，定義$A_i$的前綴和$pre_i$為$\sum_{i=0}^{i} A_i$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,q;
    cin>>n>>q;
    vector<ll> a(n),pre(n);
    for(int i=0;i<n;i++) cin>>a[i];
    pre[0]=a[0];
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        if(l==0) cout<<pre[r]<<endl;
        else cout<<pre[r]-pre[l-1]<<endl;
	}
    return 0;
}

:::success
也不一定要再開一個新的陣列
可以直接做`for(int i=1;i<n;i++) a[i]+=a[i-1];`
:::

## 差分

### 範例

有一個長度$N$的陣列$A$初始都是$0$，並且有$Q$筆操作$l$、$r$、$k$，將$A_l,A_{l+1},\cdots ,A_r$都加上$k$。問最後的陣列長怎樣。

- $1 \le N,Q \le 2 \cdot 10^5$
- $1 \le k \le 10^9$
- $1 \le l \le r \le n$

### 觀察

對於一筆操作，會發現該區間中間的**趨勢**並沒有變。可以想成原本是一個平原，將某一個區間拉高成高原(或者反過來)。


若我們可以只記錄趨勢，那麼每一筆操作就只需要改兩個地方就好。

### 作法

差分: 紀錄數列中兩個相鄰數字的差，也可以想成一個折線圖的**斜率**或**趨勢**。

簡單來講就是前綴和的逆運算

要將差分數列變為原數列只要做一次前綴和就好。

vector<int> dif(n),ans(n);
while(q--){
    int l,r,k;
    cin>>l>>r>>k;
    l--;
    r--;
    dif[l]+=k;
    if(r!=n-1) dif[r+1]-=k;
}
ans[0]=dif[0];
for(int i=1;i<n;i++) ans[i]=ans[i-1]+dif[i];

## 前綴和與差分的應用

若將數列改成連續的函式，前綴和以及差分各可以對應到積分和微分

### [Maximum Subarray Sum](https://cses.fi/problemset/task/1643)

給一個陣列，求最大的子區間之和。

可以先預處理前綴和，然後窮舉子區間的左右界，再全部取max，但是這樣的作法是$\text{O}(n^2)$，所以需要一些優化。

int ans=0;
for(int i=1;i<n;i++) pre[i]+=pre[i-1];
for(int i=0;i<n;i++){ //right
    ans=max(ans,pre[i]) // left=0;
    for(int j=0;j<i;j++){ //left-1，題目要求nonempty所以不能等於
        ans=max(ans,pre[i]-pre[j]);
    }
}

對於每個右界，我們需要找一個最小的左界。所以我們可以額外紀錄每一個地方前面的最小前綴和，即令
$$
mn_i=\min_{0\leq j\leq i-1} pre_j
$$
發現到這件事也可以在$\text{O}(n)$內完成，因為可以改寫成
$$
mn_i=\min(mn_{i-1},pre_{i-1})
$$
最後的答案即為
$$
\max_{0\leq i<n} (pre_i-mn_i)
$$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
    int n;
    cin>>n;
    vector<ll> pre(n),mn(n);
    for(int i=0;i<n;i++){
        cin>>pre[i];
        if(i!=0) pre[i]+=pre[i-1];
    }
    ll ans=pre[0];
    for(int i=1;i<n;i++){
        mn[i]=min(mn[i-1],pre[i-1]);
        ans=max(ans,pre[i]-mn[i]);
    }
    cout<<ans<<endl;
}

其實也不一定要存成陣列

#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
    int n;
    ll ans=-1e18,pre=0,mn=0;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        pre+=a;
        ans=max(ans,pre-mn);
        mn=min(mn,pre);
    }
    cout<<ans<<endl;
}

## 習題
[Multiplication Table](https://cses.fi/problemset/task/2422)

:::spoiler 解法:
對答案二分搜，尋找最小的$x$使得乘法表中小於等於$x$的數字超過$(n*n-1)/2$個，即$\sum_{i=1}^{n} \min{(n,\lfloor \frac{x}{i}\rfloor)} > \frac{n*n-1}{2}$
:::
:::spoiler code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
bool check(int x){
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=min(x/i,n);
    }
    return cnt>(n*n-1)/2;
}
signed main(){
    cin>>n;
    int l=1,r=n*n+1,mid;
    if(n==1){
        cout<<1<<endl;
        return 0;
    }
    while(r-l>1){
        mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    cout<<r<<endl;
}

:::

---
[Forest Queries](https://cses.fi/problemset/task/1652)

:::spoiler ans:
紅色=黑色-綠色-藍色+桃紅色
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q;
    cin>>n>>q;
    vector<vector<int>> pre(n,vector<int>(n));
    //int pre[n][n]
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<n;j++){
            pre[i][j]=(s[j]=='*');
            if(i>0) pre[i][j]+=pre[i-1][j];
            if(j>0) pre[i][j]+=pre[i][j-1];
            if(i>0&&j>0) pre[i][j]-=pre[i-1][j-1];
        }
    }
    while(q--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a--;b--;c--;d--;
        int ans=pre[c][d];
        if(a>0) ans-=pre[a-1][d];
        if(b>0) ans-=pre[c][b-1];
        if(a>0&&b>0) ans+=pre[a-1][b-1];
        cout<<ans<<endl;
    }
}

:::

---
[Subarray Divisibility](https://cses.fi/problemset/task/1662/)

:::spoiler 解法:
一個區間$[l,r]$的和能被$n$整除若且唯若$pre_{l-1}\equiv pre_{r} \pmod{n}$，換句話說，對於同餘的前綴和，隨意抓兩個出來都能夠組成一個能被$n$整除的區間
:::
:::spoiler code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin>>n;
    vector<int> v(n),cnt(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
        if(i!=0) v[i]+=v[i-1];
        v[i]%=n;
        cnt[(v[i]+n)%n]++;
    }
    cnt[0]++;
    int ans=0;
    for(int i=0;i<n;i++) ans+=((cnt[i]-1)*cnt[i])/2;
    cout<<ans<<endl;
    return 0;
}

:::

---
[B. Karen and Coffee](https://codeforces.com/contest/816/problem/B)
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int n,k,q;
    cin>>n>>k>>q;
    vector<int> cnt(2e5+2);
    // difference array of how many recipes recommand i degree
    while(n--){
        int a,b;
        cin>>a>>b;
        cnt[a]++;
        cnt[b+1]--;
    }
    for(int i=1;i<2e5+2;i++) cnt[i]+=cnt[i-1];
    // differnce array to original array
    for(int i=1;i<2e5+2;i++) cnt[i]=(cnt[i]>=k);
    // cnt[i]=1 if i degree is admissible
    for(int i=1;i<2e5+2;i++) cnt[i]+=cnt[i-1];
    /* original array to prefix sums array
    there are cnt[i] admissible temperatures from 1 to i degrees*/
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<cnt[b]-cnt[a-1]<<endl;
    }
}

:::

---
[A. Greg and Array](https://codeforces.com/contest/295/problem/A)

:::spoiler code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> ans(n),opcnt(m);
    vector<vector<int>> op(m,vector<int>(3));
    //operation information
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        ans[i]+=a;
        if(i!=n-1) ans[i+1]-=a;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<3;j++){
            cin>>op[i][j];
        }
        op[i][0]--;
        op[i][1]--;   
    }
    while(k--){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        opcnt[a]++;
        if(b!=m-1) opcnt[b+1]--;
    }
    for(int i=1;i<m;i++) opcnt[i]+=opcnt[i-1];
    /* difference array to original array
    the i-th operation will be applied opcnt[i] times */
    for(int i=0;i<m;i++){
        ans[op[i][0]]+=op[i][2]*opcnt[i];
        if(op[i][1]!=n-1) ans[op[i][1]+1]-=op[i][2]*opcnt[i];
    }
    cout<<ans[0]<<' ';
    for(int i=1;i<n;i++){
        ans[i]+=ans[i-1];
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

:::

---
[B. Kuriyama Mirai's Stones](https://codeforces.com/contest/433/problem/B)
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<ll> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    vector<ll> u=v;
    sort(u.begin(),u.end());
    for(int i=1;i<n;i++){
        v[i]+=v[i-1];
        u[i]+=u[i-1];
    }
    int q;
    cin>>q;
    while(q--){
        int t,l,r;
        cin>>t>>l>>r;
        l--;
        r--;
        if(t==1){
            if(l==0) cout<<v[r]<<endl;
            else cout<<v[r]-v[l-1]<<endl;
        }
        else{
            if(l==0) cout<<u[r]<<endl;
            else cout<<u[r]-u[l-1]<<endl;
        }
    }
}

:::

---
[g597. 3. 生產線](https://zerojudge.tw/ShowProblem?problemid=g597)

:::spoiler 解法:
先計算出每個位置的工作量，再安排機器的位置，越快的機器做越多事越好。
:::
:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
    int n,m;
    cin>>n>>m;
    vector<int> v(n);
    while(m--){
        int l,r,w;
        cin>>l>>r>>w;
        l--;
        r--;
        v[l]+=w;
        if(r!=n-1) v[r+1]-=w;
    }
    for(int i=1;i<n;i++) v[i]+=v[i-1];
    //differnce array to original array
    sort(v.begin(),v.end());
    vector<int> t(n);
    for(int i=0;i<n;i++) cin>>t[i];
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    ll ans=0;
    for(int i=0;i<n;i++) ans+=t[i]*v[i];
    cout<<ans<<endl;
}

:::

---
[C. Little Girl and Maximum Sum](https://codeforces.com/contest/276/problem/C)
:::spoiler 解法:
和上面那一題差不多
:::

---
[Range Xor Queries](https://cses.fi/problemset/task/1650/)

:::spoiler 解法:
$$
綠色\oplus 藍色=黃色
$$
綠色和黃色可以先用前綴XOR處理，而答案就是
$$
藍色=黃色\oplus 綠色
$$
:::
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q;
    cin>>n>>q;
    vector<int> pre(n);
    for(int i=0;i<n;i++){
        cin>>pre[i];
        if(i!=0) pre[i]^=pre[i-1];
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        if(a==0) cout<<pre[b]<<endl;
        else cout<<(pre[b]^pre[a-1])<<endl;
    }
}

:::

---
[2301 . 社交能量](https://tioj.ck.tp.edu.tw/problems/2301)

:::spoiler code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
    int n;
    ll ans=0;
    cin>>n;
    vector<ll> v(1e6+1);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        v[a]++;
        v[b]--;
    }
    for(int i=1;i<=1e6;i++){
        v[i]+=v[i-1];
        if(v[i]>1) ans+=(v[i]-1)*v[i]/2;
    }
    cout<<ans<<endl;
}

:::