# 高二上學期自主學習筆記
###### tags: `highschool` `HS self-learning`
## Atcoder abc217 pE (Queue+Priority Queue實作)Sorting Queries
[題目連結](https://atcoder.jp/contests/abc217/tasks/abc217_e)
他會給你三種要求
1:把X丟到最後面
2:把最前面的東西印出來並pop掉
3:把整個序列由小到大排序好。
AC code：
```cpp=
//code for fun
#include<iostream>
#include<stdio.h>
#include<utility>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int main(){
faster;
priority_queue <long long, vector<long long>, greater<int> > pq;
queue<long long> wait;
int n;
cin>>n;
while(n--){
int request;
cin>>request;
if(request==1){
int value;
cin>>value;
wait.push(value);
}
else if(request==2){
if(!pq.empty()){
cout<<pq.top()<<'\n';
pq.pop();
}
else{
cout<<wait.front()<<'\n';
wait.pop();
}
}
else{
while(wait.size()){
pq.push(wait.front());
wait.pop();
}
}
}
}
```
思路：簡單來說我們將輸入進來的值分兩個區塊存放，一個是wait(queue)暫存區的概念，另一個就是PQ(Priority Queue)排序之後的區域。
所以一開始輸入進去就是進入wait區，當題目要求我們將整個序列排序的時候我們將wait區的所有值都轉移到PQ，這之後輸出的值都由PQ pop出來，除非PQ是空的(pop完了或是題目尚未要求我們排序)，再從Wait中pop出來。
---
## Atcoder abc_212 pD (Priority Queue實作)Querying Multiset
[題目連結](https://atcoder.jp/contests/abc212/tasks/abc212_d)
AC code
```cpp=
//code for fun
#include<iostream>
#include<stdio.h>
#include<utility>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int main(){
faster;
int Q;
cin>>Q;
long long sum=0;
priority_queue<long long, vector<long long>, greater<long long> > bag;
while(Q--){
int query;
cin>>query;
if(query==1){
long long temp;
cin>>temp;
bag.push(temp-sum);
}
else if(query==2){
long long temp;
cin>>temp;
sum+=temp;
}
else{
cout<<bag.top()+sum<<'\n';
bag.pop();
}
}
}
```
思路：簡單來說就是Priority Queue，有個Query是要把所以數字都加X，但是PQ沒有這種功能，所以可以用一個變數來存，在輸出的時候加上去就好了，不過記得後面push進去的球要減掉那個數字。
---
## TIOJ 2208 (BFS實作)走夜路小心遇到鬼，還有女高中生
BFS，有兩種可走的距離(p,q)，要先撿到高中生再走到家裡，所以要兩階段的BFS。
當初我看到的當下看到題目寫最短路徑，然後還有往後走的可能，我就想說可能是bellman ford之類的，又白白送了一百分。
AC code
```cpp=
//code for fun
#include<iostream>
#include<stdio.h>
#include<utility>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<memory.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
bool graph[1005][1005], vis[1005][1005];
int dis[1005][1005];
int main(){
faster;
int N,M,p,q,a,b;
cin>>N>>M>>p>>q>>a>>b;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>graph[i][j];
}
}
int dx[8]={p,q,0,0,-p,-q,0,0};
int dy[8]={0,0,p,q,0,0,-p,-q};
queue< pair<int, int> > bfs;
bfs.push({1,1});
while(!bfs.empty()){
int x=bfs.front().ff, y=bfs.front().ss;
bfs.pop();
for(int i=0;i<8;i++){
int nx=x+dx[i], ny=y+dy[i];
if(nx<1||ny<1||nx>N||ny>M) continue;
if(graph[nx][ny]) continue;
if(vis[nx][ny]) continue;
vis[nx][ny]=1; dis[nx][ny]=dis[x][y]+1;
bfs.push({nx,ny});
if(nx==a&&ny==b) while (!bfs.empty()) bfs.pop();
}
}
if(!vis[a][b]) {cout<<-1;return 0;}
memset(vis,0,sizeof(vis));
bfs.push({a,b});
vis[a][b]=1;
while(!bfs.empty()){
int x=bfs.front().ff, y=bfs.front().ss;
bfs.pop();
for(int i=0;i<8;i++){
int nx=x+dx[i], ny=y+dy[i];
if(nx<1||ny<1||nx>N||ny>M) continue;
if(graph[nx][ny]) continue;
if(vis[nx][ny]) continue;
vis[nx][ny]=1; dis[nx][ny]=dis[x][y]+1;
bfs.push({nx,ny});
if(nx==N&&ny==M) while (!bfs.empty()) bfs.pop();
}
}
if(!vis[N][M]) {
cout << -1; return 0;
}
cout<<dis[N][M];
}
```
思路：因為走每一步有p、q兩種距離可以選擇，所以我將走路的八種可能寫成陣列dx&dy。
利用queue資料結構來實作BFS，並在走的時候同事紀錄走過的點及步數。
題目要求我們先找到高中生再走回家，所以要做兩次BFS。
---
## TIOJ 1288 (DP基礎)三角旅行
[題目連結](https://tioj.ck.tp.edu.tw/problems/1288)
DP基礎題，在資訊讀書會寫的，挺直觀。
AC code
```cpp=
//code for fun
#include<iostream>
#include<stdio.h>
#include<utility>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int dp[1005][1005];
void solve(){
int a;
cin >> a;
for(int i=1;i<=a;i++){
for(int j=1;j<=i;j++){
cin >> dp[i][j];
}
}
for(int i=a-1;i>=1;--i){
for(int j=1;j<=i;j++){
dp[i][j]+=max(dp[i+1][j+1],dp[i+1][j]);
}
}
cout<<dp[1][1];
}
int main(){
faster;
solve();
}
```
思路就是一路往下走，然後對於下面那層的x點來說，一定會有1~2個點可以走向自己，將那些點取max，就可以保證走到最下面一層時是最大的。
---
## TIOJ 1211 圖論之最小生成樹
[題目連結](https://tioj.ck.tp.edu.tw/problems/1211)
很單純的問最小生成樹，我使用disjoint set union實作
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int dsu[10005];
struct edge{
int from;
int to;
int weight;
};
vector<edge> edges;
bool cmp(edge a, edge b){
return a.weight < b.weight;
}
int query(int x){
if(x==dsu[x]) return x;
int tmp=query(dsu[x]);
dsu[x]=tmp;
return tmp;
}
void uni(int x, int y){
int a=query(x) , b=query(y);
if(a>b)dsu[a]=b;
else dsu[b]=a;
}
int main(){
faster;
int n,m;
while(cin>>n>>m&&n!=0){
edges.clear();
for(int i=0;i<n;i++){
dsu[i]=i; //init
}
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
edges.push_back({a-1,b-1,c});
}
sort(edges.begin(),edges.end(),cmp);
int cnt=0,sum=0;
for(int i=0;i<m;i++){
if(query(edges[i].from)!=query(edges[i].to)){
sum+=edges[i].weight;
uni(edges[i].from, edges[i].to);
cnt++;
}
}
if(cnt==n-1) cout<<sum<<'\n';
else cout<<-1<<'\n';
}
}
```
#### 這題我使用Kruskal演算法。
* Kruskal：對一個有權無向圖的邊的權重由小到大排序，從權重最小的邊開始將邊合成子樹，
若加入第$i$個邊會使某子樹出現環，則跳過第$i$個邊。
設最小生成樹有$n$個節點，則此樹有$n-1$個邊，可以用此判斷是否已經找到最小生成樹。
#### 使用DSU(disjoint set union)實作kruskal演算法：
* 首先我們開一個叫做dsu的陣列來記錄某點的父節點，以及一個可以記錄邊的權重以及起始點的結構(edge)。
* 首先需要先初始化，將dsu的所有點的父節點指向自己(代表點現在還沒連起來)，然後將的資料輸入進edge的vector中，並根據權重由小排到大。
* 接下來開始檢查邊，若某邊的起點和終點指向的根節點相同則會造成環，因此我們寫一個query函式來尋找某個點的根節點。
* query函式寫法：若在dsu陣列中，自己指向的父節點為自己，則自己即為根結點，回傳自己即可，若不是，則繼續向上尋找，在向上尋找的過程中，將每個點的父節點都指向根結點，則可以將這顆子樹轉變為一棵高度為2的樹，之後query便不需要遞迴太多次。
* 在判斷完某邊不會形成環之後，我們需要將兩棵樹和在一起，合成的方法很簡單，只需要在uni這個函式中呼叫query尋找起點及終點的根結點，並將終點的根結點的父節點(也就是dsu的值)指向起點的根結點即可將兩棵樹合成。
* 最後檢查是否有n-1個邊即可。
---
## TIOJ 1508 (01背包問題)加減問題
[題目連結](https://tioj.ck.tp.edu.tw/problems/1508)
題目敘述：提供一串數字，問是否能在數字前面加入正負號後使數字總和=0
AC code：
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int a[105];
bool dp[100005];
int main(){
faster;
int m,n;
cin>>m>>n;
while(m--){
for(int i=0;i<105;i++){
a[i]=0;
}
for(int j=0;j<100005;j++){
dp[j]=0;
}
long long target=0;
for(int i=1;i<=n;i++){
cin>>a[i];
target+=a[i];
}
if(target%2){
cout<<"No"<<'\n';
continue;
}
target/=2;
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=target;j>=a[i];j--){
dp[j]=dp[j]|dp[j-a[i]];
}
}
if(dp[target])cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
}
```
題解：
如果我們能湊出數字總和的一半，我們就一定能透過加上負號使總和=0。
因此我們開一個bool的dp陣列，$dp[i]$存的狀態為是否能湊出i元。
轉移的想法為，若我們能在不用$a[i]$的情況下湊出$j-a[i]$元，我們就能保證我們能湊出$j$元。
為了不重覆拿$a[i]$，令$dp[j]=dp[j] | dp[j-a[i]]$，這樣$dp[j]$處理好後，就不會被判斷到。
---
## CSES Two Sets(數學)
[題目連結](https://cses.fi/problemset/task/1092)
給一數字n，問1~n可否分成兩個集合使兩集合的和相同。
若可以，將兩集合中數字輸出。
AC code
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int main(){
faster;
int n;
cin>>n;
vector <int> a,b;
if(n%4!=0&&n%4!=3) cout<<"NO";
else if(n%4==0){
for(int i=1;i<=n/2;i++){
if(i%2==1){
a.push_back(i);
a.push_back(n-i+1);
}
else{
b.push_back(i);
b.push_back(n-i+1);
}
}
cout<<"YES"<<"\n";
cout<<n/2<<'\n';
for(auto i:a)cout<<i<<' ';
cout<<'\n'<<n/2<<'\n';
for(auto i:b)cout<<i<<' ';
}
else{
b.push_back(n);
a.push_back(1);
a.push_back(n-1);
for(int i=2;i<(n+1)/2;i++){
if(i%2==1){
a.push_back(i);
a.push_back(n-i);
}
else{
b.push_back(i);
b.push_back(n-i);
}
}
cout<<"YES"<<"\n";
cout<<n/2+1<<'\n';
for(auto i:a)cout<<i<<' ';
cout<<'\n'<<n/2<<'\n';
for(auto i:b)cout<<i<<' ';
}
}
```
題解：1~n的和的一般式為$\frac{n(n+1)}2$，這個和要可以分成兩份，因此$n(n+1)=4k$，
只有在 $n\equiv 3\pmod 4$或是 $n\equiv 0\pmod 4$時可以滿足。
因此將輸入分成三個case：
* 第一種是$n/4$餘數不等於0或3，直接輸出NO。
* 第二種是$n/4$餘數$=$ 0，則我們可以將$1,n$放進第一個set，$2,n-1$放進第二個set，以此類推。
* 第三種是$n/4$餘數$=$ 3 我們可以發現$1+(n-1)=n$，所以我們可以將$n$放進第一個set中，將$1,n-1$放進第二個set中，則剩餘的數量為$n-3$，$\because n\equiv 3\pmod4 \therefore(n-3)\equiv 0\pmod 4$。
我們可將剩餘的項依照$n\equiv 0\pmod 4$的狀況分成兩組。
---
## TIOJ 1080逆序數對
[題目連結](https://tioj.ck.tp.edu.tw/problems/1080)
題目敘述：對一數列$S$，若$S$的第$i$項與第$j$項符合$S_{i}>S_{j}$ ，並且$i>j$的話，那麼我們說$(i,j)$是一個逆序數對。請問給定$S$，總共有多少個逆序數對呢？
AC code：
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
ll ans;
void merge_sort(int a[], int l, int r) { //[l, r)
if (r - l <= 1) return;
int mid = (l + r) / 2;
merge_sort(a, l, mid);
merge_sort(a, mid, r); //thus, [l, mid) and [mid, r) are sorted
int sorted[r - l];
int ri = mid, ind = 0;
long long m=0;
for (int li = l;li < mid;li++) { //two pointers
ans+=m;
while (ri < r && a[ri] < a[li]) {//a[l]~a[mid],a[mid+1]~a[r]單調
sorted[ind] = a[ri];
ind++; ri++;
m++;ans++;
}
sorted[ind] = a[li];
ind++;
}
while (ri < r) { //insert remaining elements
sorted[ind] = a[ri];
ind++, ri++;
}
for (int i = 0;i < r - l;i++) a[i + l] = sorted[i];
}
int main(){
faster;
int n,cas=1;
while(cin>>n&&n!=0){
ans = 0;
int k = n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
merge_sort(a,0,n);
cout<<"Case #"<<cas<<": "<<ans<<'\n';
cas++;
}
}
```
這是從資訊讀書會學到的，我原本往樹狀數組或是線段樹的方向思考，但是這題會需要離散化才方便運算。
用合併排序就不需要離散化了。
想法：對於兩個單調遞增的數列$L=S_{l}$至$S_{mid}$, $R=S_{mid+1}$至$S_{r}$來說我們可以透過雙指針的方法來比較兩個數列並合併成一單調遞增數列。
在合併的過程中我們可以假設左半邊的數列$L$第$i$項比右半邊數列$R$中的$k$個數字還大，則對於$L_{i}$有$k$個逆序數對，又因為$L$單調遞增，所以$L_{i+1}$至少也有$k$個逆序數對，若有更多，則可以透過雙指針發現，因此我們可以以一個變數$m$來記錄這個k而m在合併排序過程中不須歸零。
---
## 19/11 TOI潛力組pB：潛水(類似最短路徑演算法)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e810)
$AC code：$
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
int adj[505][505];
int dis[505];
int main(){
faster;
int n,m;
cin>>n>>m;
vector<int>record(n,0);
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
adj[a][b]=w;
adj[b][a]=w;
}
for(int i=0;i<=n;i++) dis[i]=1e9;
int start,end;
cin>>start>>end;
queue<int> bfs;
bfs.push(start);
dis[start]=0;
while(!bfs.empty()){
int temp=bfs.front();
bfs.pop();
for(int i=0;i<n;i++){
if(adj[temp][i]!=0&&dis[i]>max(adj[temp][i],dis[temp])){
bfs.push(i);
dis[i]=max(adj[temp][i],dis[temp]);
}
}
}
if(dis[end]==1e9) cout<<-1;
else cout<<dis[end];
}
```
思路：
* 用相鄰矩陣adj\[i\]\[j\]來記錄邊的權重，預設是0。
* 再用一個dis\[i\]陣列來記錄從起點到第i個點的最大權重。
* 因此我們先假設dis都是INT_MAX，然後我們透過bfs來遍歷這張圖。
* 若dis\[i\](此邊的目的地的最大權重)>max(dis\[temp\](通往此邊的起點的最大權重) , adj\[temp\]\[i\])。
* 以此維護dis\[i\]。
* 若最後dis\[終點\]=1e9代表根本走不到
---
## CSES Dynamic Range Minimum Queries(線段樹做法)
[題目連結](https://cses.fi/problemset/task/1649)
AC code
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
long long st[8*100000];
void build(int l,int r,int ind,int a[]){
if(l==r){
st[ind]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,ind*2,a);
build(mid+1,r,ind*2+1,a);
st[ind]=min(st[ind*2],st[ind*2+1]);
}
void mod(int l,int r,int ql,int ind, int val){
if(l==r) st[ind]=val;
else{
int mid=(l+r)/2;
if(ql<=mid){
mod(l,mid,ql,ind*2,val);
}
else{
mod(mid+1,r,ql,ind*2+1,val);
}
st[ind]=min(st[2*ind],st[2*ind+1]);
}
}
int qry(int l,int r, int ql, int qr,int ind){
if(l>qr||r<ql) return 1e9;
if(l>=ql&&r<=qr) return st[ind];
int mid=(l+r)/2;
return min(qry(l,mid,ql,qr,ind*2),qry(mid+1,r,ql,qr,ind*2+1));
}
int main(){
faster;
int l,q;
cin>>l>>q;
int a[l+1];
for(int i=1;i<=l;i++) cin>>a[i];
build(1,l,1,a);
while(q--){
int dem;
cin>>dem;
if(dem==1){
int ql,val;
cin>>ql>>val;
mod(1,l,ql,1,val);
}
else{
int ql,qr;
cin>>ql>>qr;
cout<<qry(1,l,ql,qr,1)<<'\n';
}
}
}
```
作法：
* 線段樹裡的節點代表不同區間，第一個節點代表最大的區間，他的左子節點代表左界到中點的區間，右子節點代表中點+1到右界的區間，以此類推。
* 線段樹只能處理有結合律的性質。
---
## CSES Range Update Queries(懶標線段樹做法)
[題目連結](https://cses.fi/problemset/task/1651/)
AC code：
```cpp=
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
const int N = 2 * 1e5;
long long a[N];
long long st[4*N];
long long tag[4*N];
void upd(int l, int r, int ind, long long val){
st[ind]+=(r-l+1)*val;
tag[ind]+=val;
}
void push(int l,int r,long long ind){
int mid=(l+r)/2;
upd(l,mid,ind*2,tag[ind]);
upd(mid+1,r,ind*2+1,tag[ind]);
tag[ind]=0;//pushed
}
void pull(int ind){
st[ind]=st[ind*2]+st[ind*2+1];
}
void mod(int l,int r,int ql, int qr, int ind, long long val){
if(qr>=r&&ql<=l){//[ql,qr]�]�t[l,r];
upd(l,r,ind,val);
return;
}
int mid=(l+r)/2;
if(qr<=mid) mod(l,mid,ql, qr, ind*2, val);
else if(ql>mid) mod(mid+1,r,ql,qr, ind*2+1,val);
else{
mod(l,mid,ql, qr, ind*2, val);
mod(mid+1,r,ql,qr, ind*2+1,val);
}
pull(ind);
}
long long query(int l,int r,int ind,int ql,int qr){
if(ql>r||qr<l) return 0;
if(ql==l&&qr==r) return st[ind];
int mid=(l+r)/2;
push(l,r,ind);
if(qr<=mid) return query(l, mid, ind*2, ql, qr);
else if(mid<ql) return query(mid+1,r,ind*2+1,ql,qr);
else{
return query(l, mid, ind*2, ql, mid)+query(mid+1,r,ind*2+1,mid+1,qr);
}
}
void build(int l,int r, int ind){
if(l==r){
st[ind]=a[l];
}
else{
int mid=(l+r)/2;
build(l,mid, ind*2);
build(mid+1,r, ind*2+1);
pull(ind);
}
}
int main(){
faster;
int l,q;
cin>>l>>q;
for(int i=1;i<=l;i++){
cin>>a[i];
}
build(1,l,1);
while(q--){
int dem;
cin>>dem;
if(dem==1){
int ql,qr,val;
cin>>ql>>qr>>val;
mod(1,l,ql,qr,1,val);
}
else{
int q;
cin>>q;
cout<<query(1,l,1,q,q)<<'\n';
}
}
}
```
參考講義：[建中資訊讀書會 資料結構](https://hackmd.io/@PeiGan/rkQdWoCBF#/6)
[wiwiho 線段樹hackMD](https://hackmd.io/@wiwiho/CPN-segment-tree)
作法：
* 這題的題目是要區間修改，單點查詢，其實可以用差分前綴來做，但我這邊想練習懶標線段樹。
* 除了原本的線段樹st[ ]，再另外開一個tag[ ]，他的所有節點的區間範圍跟st[ ]相同，用來記錄要在區間加上的值。
* 一開始打上標記之後不需要急著對st[ ]上面的值做修改，等要query的時候再將tag[ ]上面記錄的值拿去修改st[ ]。
* 在每次modify的時候，只要找到剛好包含的區間，在tag[ ]節點上打上懶標，並在找到對的區間的過程中，利用pull()函數來合併修改過的節點的值，將st[ ]的值維護好。
* 在每次query的時候，在找到對的區間之前，利用push()將懶標下推並一併修改st[ ]的值，注意在懶標下推後要將上層的懶標歸零。
---
## APCS 2021/11場 實作 第三題
[zerojudge 題目連結]
(https://zerojudge.tw/ShowProblem?problemid=g597)
* 我有報名到APCS的11月場，原本預計可以拿個300分，但是我看到這題區間修改單點查詢後greedy，我卻吃毒想寫懶標線段樹，但我一直segmentation fault，最後無奈只能爆做拿第一個子題的分數。
$AC$ $Code$
```cpp=
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
long long pa[200005],prefix[200005];
bool cmp(long long a, long long b){
return a>b;
}
int main(){
faster;
int n,m;
cin>>n>>m;
while(m--){
int a,b,val;
cin>>a>>b>>val;
pa[a]+=val;
pa[b+1]-=val;
}
prefix[0]=pa[1];
for(int i=1;i<n;i++){
prefix[i]=pa[i+1]+prefix[i-1];
}
sort(prefix,prefix+n);
long long a[n];
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n,cmp);
long long ans=0;
for(int i=0;i<n;i++){
ans+=prefix[i]*a[i];
}
cout<<ans;
}
```
* 這題因為是單點查詢，所以根本不需要用懶標線段樹，用差分前綴即可。
---
## OJDL 7010 大波城的大波路～其一(最短路徑)
[題目連結](https://ojdl.ck.tp.edu.tw/problem/7010)
* 一題單純的最短路徑的題目，我使用spfa(shortest path fast algorithm)及dijkstra algorithm實作，spfa是一種使用queue優化的bellman ford演算法，而dijkstra則是使用priority queue。
$SPFA$
```cpp=
//code for fun
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
typedef long long ll;
using namespace std;
int INF=1e18;
signed main(){
faster;
int v,e;
cin>>v>>e;
vector< vector<pii> > G(v+1);
vector<int> dis (v+5,INF);
dis[1]=0;
for(int i=0;i<e;i++){
int a,b,w;
cin>>a>>b>>w;
G[a].push_back(make_pair(b,w));
G[b].push_back(make_pair(a,w));
}
queue<int> q;
q.push(1);
while(!q.empty()){
int top=q.front();
q.pop();
for(auto i=G[top].begin();i<G[top].end();i++){
int it=i-G[top].begin();
if(dis[top]+G[top][it].second < dis[G[top][it].first]){
dis[G[top][it].first]=dis[top]+G[top][it].second;
q.push(G[top][it].first);
}
}
}
for(int i=1;i<=v;i++){
cout<<dis[i]<<'\n';
}
}
```
$Dijkstra$
```cpp=
#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(0);
#define pii pair<int, int>
#define vi vector<int>
#define int long long
typedef long long ll;
using namespace std;
int INF=1e18;
int in[10001]={};
signed main(){
faster;
int v,e;
cin>>v>>e;
vector<pair<ll,int>> G[v+5];
vector<ll> dis (v+5,INF);
dis[1]=0;
for(int i=0;i<e;i++){
int a,b;ll w;
cin>>a>>b>>w;
G[a].push_back(make_pair(w,b));
G[b].push_back(make_pair(w,a));
}
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push({0,1});
while(!pq.empty()){
int top=pq.top().second;
pq.pop();
for(auto i=G[top].begin();i<G[top].end();i++){
int it=i-G[top].begin();
if(dis[top]+G[top][it].first < dis[G[top][it].second]){
dis[G[top][it].second]=dis[top]+G[top][it].first;
pq.push(G[top][it]);
}
}
}
for(int i=1;i<=v;i++){
cout<<dis[i]<<'\n';
}
}
```
* 相較於bellman ford盲目的窮舉邊來嘗試鬆弛，spfa則是將鬆弛過的點丟進queue中，每次只遍歷被鬆弛的點的邊，鬆弛之後就pop掉。
* Dijkstra其實也大同小異，只是是將邊丟進Priority queue然後根據權重從小到大排
---
## TIOJ 1706 烏龜暗殺
[題目連結](https://tioj.ck.tp.edu.tw/problems/1706)
題敘：給定一起點及終點，以及一張圖，每條邊從點a到點b及從點b到點a的權重不一定相同，再給每條邊每天的權重變化量(可能為負)，同樣的，每條邊從點a到點b及從點b到點a的權重變化量不一定相同，再給一個天數
(d)，問你在[1,d]的區間中，取一天從起點到終點再回到起點所需要的最小權重和，需在一天內來回。
$AC$ $Code$
```cpp=
#include<bits/stdc++.h>
int INF=1e9;
using namespace std;
vector<pair<int, int> > g1[100005], g2[100005];//first=weight,second=destination
int spfa(auto &g, int s, int t){
vector<int> dis(100005,INF);
dis[s]=0;
priority_queue<pair<int,int> > pq;
pq.push({0,s});
while(!pq.empty()){
pair<int,int> top=pq.top();
pq.pop();
for(auto i:g[top.second]){
if(dis[top.second]+i.first<dis[i.second]){
dis[i.second]=dis[top.second]+i.first;
pq.push(i);
}
}
}
return dis[t];
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
long long v,e,start,end,d;
cin>>v>>e>>start>>end>>d;
for(int i=0;i<e;i++){
int a, b, go_fee, go_grow, back_fee, back_grow;
cin>>a>>b>>go_fee>>go_grow>>back_fee>>back_grow;
g1[a].push_back(make_pair(go_fee, b));
g1[b].push_back(make_pair(back_fee, a));
g2[a].push_back(make_pair(go_fee+go_grow*(d-1),b));
g2[b].push_back(make_pair(back_fee+back_grow*(d-1),a));
}
cout<<min(spfa(g1, start, end)+spfa(g1, end, start), spfa(g2, start, end)+spfa(g2, end, start));
}
```
### 思路：
* 對於每一條能從起點到終點的路徑，我們都一定能將他們每條邊的權重變化量加起來
* 若>0，則這條路徑的權重和會隨時間越來越大
* 相反的，若<0，則這條路徑的權重和會隨時間越來越小
* 利用這個特性我們可以知道任一條路徑的權重和隨時間的變化都是具有單調性的
* 因此我們可以推論任一條路徑的最小權重和一定發生在第一天或是第D天
* 因此我們只要用四次最短路徑演算法求出第一天及第D天從起點到終點及從終點回起點分別需要的權重和，並選擇總和較小的那天即可。
---
Sign in with Wallet
Connect another wallet