因為這兩天在寫線性代數的作業，沒怎么寫題……
P1438 無聊的數列
題目背景
無聊的 YYB 總喜歡搞出一些正常人無法搞出的東西。有一天，無聊的 YYB 想出了一道無聊的題：無聊的數列。。。
題目描述
維護一個數列?ai?，支持兩種操作：
-
1 l r K D：給出一個長度等于?r?l+1?的等差數列，首項為?K，公差為?D，并將它對應加到?[l,r]?范圍中的每一個數上。即：令?al?=al?+K,al+1?=al+1?+K+D…ar?=ar?+K+(r?l)×D。 -
2 p：詢問序列的第?p?個數的值?ap?。
輸入格式
第一行兩個整數數?n,m?表示數列長度和操作個數。
第二行?n?個整數，第?i?個數表示?ai?。
接下來的?m?行，每行先輸入一個整數?opt。
若?opt=1?則再輸入四個整數?l?r?K?D；
若?opt=2?則再輸入一個整數?p。
輸出格式
對于每個詢問，一行一個整數表示答案。
輸入輸出樣例
輸入 #1復制
5 2 1 2 3 4 5 1 2 4 1 2 2 3
輸出 #1復制
6
說明/提示
數據規模與約定
對于?100%?數據，0≤n,m≤105,?200≤ai?,K,D≤200,1≤l≤r≤n,1≤p≤n。
思路：
最要注意的是他的結果會超過int型，所以要用 long long 來記錄結果
-
等差數列的分解：
-
等差數列可以分解為常數項和線性項：
-
常數項：A = K - l × D
-
線性項系數：D
-
-
位置 i 的增加值：add(i) = (K - l × D) + (i - l) × D = A + D × i
-
-
兩個樹狀數組維護：
-
樹狀數組 tr1：維護常數項（A）
-
在 l 處加 A
-
在 r+1 處減 A（若 r+1 ≤ n）
-
-
樹狀數組 tr2：維護線性項系數（D）
-
在 l 處加 D
-
在 r+1 處減 D（若 r+1 ≤ n）
-
-
-
查詢計算：
-
位置 p 的值 = 初始值 + tr1 的前綴和(p) + tr2 的前綴和(p) × p
-
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {long long k, d;int l, r;
}a[400005];
int b[100005];
void XiaFang(int i) {a[i * 2].k += a[i].k;a[i * 2].d += a[i].d;a[i * 2 + 1].k += a[i].k + (a[i * 2 + 1].l - a[i].l) * a[i].d;a[i * 2 + 1].d += a[i].d;a[i].k = 0;a[i].d = 0;
}
void Chu(int l, int r, int i) {a[i].l = l, a[i].r = r, a[i].d = 0;if (l == r) {a[i].k = b[a[i].l];return;}a[i].k = 0;int mid = (l + r) >> 1;Chu(l, mid, i * 2);Chu(mid + 1, r, i * 2 + 1);
}
void ChaRu(int l, int r, int k, int d,int i) {if (a[i].l >= l && a[i].r <= r) {a[i].k += k + (a[i].l - l) * d;a[i].d += d;return;}int mid = (a[i].l + a[i].r) >> 1;if (a[i].d != 0 || a[i].k != 0) {XiaFang(i);}if (l<=mid ) {ChaRu(l, r, k, d, i * 2);}if (mid+1 <= r) {ChaRu(l, r, k, d, i * 2 + 1);}
}
long long Cha(int p, int i) {if (a[i].l == p&&a[i].r==p) {return a[i].k;}int mid = (a[i].l + a[i].r) >> 1;if (a[i].d != 0 || a[i].k != 0) {XiaFang(i);}if ( p<=mid ) {return Cha(p, i * 2);}else {return Cha(p, i * 2 + 1);}
}
int p, l, r, k, d, n, m, q;
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin與cout綁定cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i];}Chu(1,n,1);for (int i = 0; i < m; i++) {cin >> q;if (q == 1) {cin >> l >> r >> k >> d;ChaRu(l, r, k, d, 1);}else {cin >> p;cout << Cha(p, 1) << endl;}}return 0;
}?P1253 扶蘇的問題
題目描述
給定一個長度為?n?的序列?a，要求支持如下三個操作：
- 給定區間?[l,r]，將區間內每個數都修改為?x。
- 給定區間?[l,r]，將區間內每個數都加上?x。
- 給定區間?[l,r]，求區間內的最大值。
輸入格式
第一行是兩個整數，依次表示序列的長度?n?和操作的個數?q。
第二行有?n?個整數，第?i?個整數表示序列中的第?i?個數?ai?。
接下來?q?行，每行表示一個操作。每行首先有一個整數?op，表示操作的類型。
- 若?op=1，則接下來有三個整數?l,r,x，表示將區間?[l,r]?內的每個數都修改為?x。
- 若?op=2，則接下來有三個整數?l,r,x，表示將區間?[l,r]?內的每個數都加上?x。
- 若?op=3，則接下來有兩個整數?l,r，表示查詢區間?[l,r]?內的最大值。
輸出格式
對于每個?op=3?的操作，輸出一行一個整數表示答案。
輸入輸出樣例
輸入 #1復制
6 6 1 1 4 5 1 4 1 1 2 6 2 3 4 2 3 1 4 3 2 3 1 1 6 -1 3 1 6
輸出 #1復制
7 6 -1
輸入 #2復制
4 4 10 4 -3 -7 1 1 3 0 2 3 4 -4 1 2 4 -9 3 1 4
輸出 #2復制
0
說明/提示
數據規模與約定
- 對于?10%?的數據，n=q=1。
- 對于?40%?的數據，n,q≤103。
- 對于?50%?的數據，0≤ai?,x≤104。
- 對于?60%?的數據，op=1。
- 對于?90%?的數據，n,q≤105。
- 對于?100%?的數據，1≤n,q≤106，1≤l,r≤n，op∈{1,2,3}，∣ai?∣,∣x∣≤109。
提示
請注意大量數據讀入對程序效率造成的影響。
思路：
-
線段樹節點設計：
-
每個節點包含三個字段：
setv（區間賦值標記）、addv（區間加法標記）和?maxv（區間最大值）。 -
setv?為?LLONG_MIN?時表示該節點沒有賦值標記。 -
addv?為 0 時表示沒有加法標記。
-
-
標記下傳）：
-
如果當前節點有賦值標記（
setv != LLONG_MIN），則將其下傳到子節點，并清除子節點的加法標記。 -
如果當前節點有加法標記（
addv != 0），則根據子節點的標記類型進行更新：-
如果子節點有賦值標記，則將加法標記加到賦值標記上。
-
否則，將加法標記加到子節點的加法標記上。
-
-
更新子節點的最大值并清除當前節點的標記。
-
-
標記上傳：
-
用子節點的最大值更新當前節點的最大值。
-
-
區間賦值操作：
-
當節點區間完全被目標區間覆蓋時，設置節點的?
setv?為指定值，清除?addv，并更新?maxv。 -
否則，下傳標記后遞歸處理子節點，最后更新當前節點的最大值。
-
-
區間加法操作：
-
當節點區間完全被目標區間覆蓋時：
-
如果有賦值標記，則更新賦值標記。
-
否則，更新加法標記。
-
-
更新節點的最大值。
-
否則，下傳標記后遞歸處理子節點，最后更新當前節點的最大值。
-
-
區間最大值查詢：
-
當節點區間完全被查詢區間覆蓋時，直接返回?
maxv。 -
否則，下傳標記后遞歸查詢子節點，并返回子節點中的最大值。
-
然后就是他這個題目的結構體還是有一點說法 的，如果你把x放進去記錄那比較好些一點，但你一開始向我一樣懶的話就只能在op1下滑時a[i * 2+1].Max0 = a[i].Max0-a[i].op2;（先op1在op2)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {int l, r;long long Max0;long long op2;bool op1;
}a[4000006];
long long b[1000006];
void Chu(int l, int r, int i) {a[i].l = l, a[i].r = r;a[i].op2 = 0, a[i].op1 = false;if (l == r) {a[i].Max0 = b[l];return;}int mid = (l + r) >> 1;Chu(l, mid, i * 2);Chu(mid + 1, r, i * 2 + 1);a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
void OOp1(int i) {if(a[i].l!=a[i].r) {a[i * 2].Max0 = a[i].Max0-a[i].op2;a[i * 2].op2 = 0;a[i * 2].op1 = true;a[i * 2+1].Max0 = a[i].Max0-a[i].op2;a[i * 2+1].op2 = 0;a[i * 2+1].op1 = true;}a[i].op1 = false;
}
void OOp2(int i) {if (a[i].l != a[i].r) {a[i * 2].Max0 += a[i].op2;a[i * 2].op2 += a[i].op2;a[i * 2 + 1].Max0 += a[i].op2;a[i * 2 + 1].op2 += a[i].op2;}a[i].op2 = 0;
}
void Op1(int l, int r, long long x,int i) {if (a[i].l >= l && a[i].r <= r) {a[i].Max0 = x;a[i].op2 = 0;a[i].op1 = true;return;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能為負數OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;if (l <= mid) {Op1(l, r,x, i * 2);}if (mid + 1 <= r) {Op1(l, r, x, i * 2 + 1);}a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
void Op2(int l, int r, long long x, int i) {if (a[i].l >= l && a[i].r <= r) {a[i].Max0 += x;a[i].op2 += x;return;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能為負數OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;if (l <= mid) {Op2(l, r, x, i * 2);}if (mid + 1 <= r) {Op2(l, r, x, i * 2 + 1);}a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
long long Op3(int l, int r, int i) {if (a[i].l >= l && a[i].r <= r) {return a[i].Max0;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能為負數OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;long long w = LLONG_MIN;if (l <= mid) {w = max(w, Op3(l, r, i * 2));}if (mid + 1 <= r) {w = max(w, Op3(l, r, i * 2 + 1));}return w;
}
int n, m, l, r, op;
long long x;
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin與cout綁定cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i];}Chu(1, n, 1);for (int i = 1; i <= m; i++) {cin >> op;switch (op){case 1:cin >> l >> r >> x;Op1(l, r, x, 1);break;case 2:cin >> l >> r >> x;Op2(l, r, x, 1);break;case 3:cin >> l >> r;cout << Op3(l, r, 1) << endl;break;default:break;}}return 0;
}?
