線段樹做法
AC (0.7s, 16.9MB)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, st[N << 2], tag[N << 2];
//建立segment tree
void build(int pos, int x, int v = 1, int l = 0, int r = n - 1){
if(l == r){
st[v] = x; return;
}
int m = (l + r) >> 1;
if(pos <= m) build(pos, x, v << 1, l, m);
else build(pos, x, v << 1 | 1, m + 1, r);
st[v] = st[v << 1] + st[v << 1 | 1];
}
//將tag的值加入st,並將tag標記下推
void push(int v, int l, int r){
st[v] += tag[v] * (r - l + 1);
if(l != r){
tag[v << 1] += tag[v];
tag[v << 1 | 1] += tag[v];
}
tag[v] = 0;
}
//資料更新,向下設立tag
void upd(int ql, int qr, int x, int v = 1, int l = 0, int r = n - 1){
if(tag[v]) push(v, l, r);
st[v] += x * (qr - ql + 1);
if(ql == l && qr == r){
if(l != r){
tag[v << 1] += x;
tag[v << 1 | 1] += x;
}
return;
}
int m = (l + r) >> 1;
if(qr <= m) upd(ql, qr, x, v << 1, l, m);
else if(ql > m) upd(ql, qr, x, v << 1 | 1, m + 1, r);
else{
upd(ql, m, x, v << 1, l, m);
upd(m + 1, qr, x, v << 1 | 1, m + 1, r);
}
}
//區間查詢
int qry(int ql, int qr, int v = 1, int l = 0, int r = n - 1){
if(tag[v]) push(v, l, r);
if(ql == l && qr == r) return st[v];
int m = (l + r) >> 1;
if(qr <= m) return qry(ql, qr, v << 1, l, m);
else if(ql > m) return qry(ql, qr, v << 1 | 1, m + 1, r);
else return qry(ql, m, v << 1, l, m) + qry(m + 1, qr, v << 1 | 1, m + 1, r);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0; i<n; i++){
int x;
cin>>x;
build(i, x);
}
int q;
cin>>q;
while(q--){
int v;
cin>>v;
if(v == 1){
int x, y, k;
cin>>x>>y>>k;
x--, y--;
upd(x, y, k);
}
else{
int x, y;
cin>>x>>y;
x--, y--;
cout<<qry(x, y)<<'\n';
}
}
return 0;
}
C++
ZeroJudge
Uploading file…_iujrjskv8
Jul 3, 2024C語言學習筆記
Jun 11, 2024a417. 螺旋矩陣 (題目連結) 解題思路 :::info 1.填表 用二維陣列儲存資料,由左上角開始填數字,接下來四個 while 分別表示 : 向右、向下、向左、向上,當 i 或 j 超出範圍或目標格已經有值時,跳出迴圈。一直重複直到全部填完。 2.翻轉 若 m==2 將 matrix[i][j] 和matrix[j][i] 全部交換。
Jan 29, 2023花中judge d001. Jumping Array Puzzle (題目連結) BFS作法 AC (90ms, 8.4MB) #include <bits/stdc++.h> using namespace std; #define int long long #define x first
Jul 25, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up