企业官网建设流程全解析

线段树（区间加法 ， 区间求和）

#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define ull unsigned long long #define ld long double const ll INF = 0x3f3f3f3f3f3f3f; const int inf = 0x3f3f3f3f; const int N = 4e5 + 10; ll tree[N];//区间和; ll a[N]; ll lazy[N];//延迟数组 void push_down(int node , int start , int end) { if(lazy[node] != 0 && start != end) { int mid = (start + end)/2; int left = node * 2; int right = node * 2 + 1; tree[left] += lazy[node] * (mid - start + 1); lazy[left] += lazy[node]; tree[right] += lazy[node] * (end - mid); lazy[right] += lazy[node]; lazy[node] = 0; } } void buildtree(int node , int start , int end) { if(start == end) { tree[node] = a[start]; lazy[node] = 0; } else { int mid = (start + end)/2; int left = node*2; int right = node*2 + 1; buildtree(left , start , mid); buildtree(right , mid + 1 , end); tree[node] = tree[left] + tree[right]; lazy[node] = 0;//初始化所有节点为0； } } void uppdate(int node , int start , int end , int l , int r , ll val) { if(r < start || l > end) { return; } if(l <= start && end <= r) { tree[node] += (end - start + 1) * val; lazy[node] += val; return; } //部分重合必须访问子节点，需要先向下更新lazy; push_down(node , start , end); int mid = (start + end)/2; int left = node *2; int right = node * 2 + 1; uppdate(left , start , mid , l , r , val); uppdate(right , mid + 1 , end , l , r , val); tree[node] = tree[left] + tree[right]; return; } ll query(int node , int start , int end , int l , int r) { if(r < start || l > end) { return 0; } if(l <= start && r >= end) { return tree[node]; } push_down(node , start , end); int mid = (start + end) / 2; int left = node * 2; int right = node * 2 + 1; ll left_sum = query(left , start , mid , l , r); ll right_sum = query(right , mid + 1 , end , l , r); return left_sum + right_sum; } void solve() { int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i++) cin >> a[i]; buildtree(1 , 1 , n); for(int i = 1 ; i <= m ; i++) { int op; cin >> op; if(op == 1) { int l , r ; ll val; cin >> l >> r >> val; uppdate(1 , 1 , n , l , r , val); } else if(op == 2) { int l , r; cin >> l >> r; cout << query(1 , 1 , n , l , r) << endl; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0 ; }

线段树2（区间加法和乘法 ， 区间求和）

注意懒标记维护形式;

#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define ull unsigned long long #define ld long double const ll INF = 0x3f3f3f3f3f3f3f; const int inf = 0x3f3f3f3f; const int N = 1e5 + 10; ll a[N]; ll tree[4 * N]; ll add[4 * N]; ll mul[4 * N]; ll bigpow(ll a , ll b , ll mod) { a %= mod; ll res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } void push_down(int node , int start , int end , ll mod) { if((mul[node] != 1 || add[node] != 0) && start != end) { int mid = (start + end)/ 2; int left = 2 * node; int right = 2 * node + 1; tree[left] = (tree[left] * mul[node] + add[node] * (mid - start +1LL))%mod; tree[left] %= mod; mul[left] = (mul[left] * mul[node]) % mod; add[left] = (add[left] * mul[node] + add[node]) % mod; tree[right] = (tree[right] * mul[node] + add[node] * (end - mid))%mod; tree[right] %= mod; mul[right] = (mul[right] * mul[node]) % mod; add[right] = (add[right] * mul[node] + add[node]) % mod; mul[node] = 1; add[node] = 0; } } void buildtree(int node , int start , int end , ll mod) { if(start == end) { tree[node] = a[start]; tree[node] %= mod; mul[node] = 1; add[node] = 0; return; } int mid = (start + end) / 2; int left = 2 * node; int right = 2 * node + 1; buildtree(left , start , mid , mod); buildtree(right , mid + 1 , end , mod); tree[node] = tree[left] + tree[right]; tree[node] %= mod; mul[node] = 1; add[node] = 0; } void uppdate1(int node , int start , int end , int l , int r , ll val , ll mod) { if(start > r || end < l) { return; } else if(start >= l && end <= r) { tree[node] += (end - start + 1LL) * val; tree[node] %= mod; add[node] += val; add[node] %= mod; return; } push_down(node , start , end , mod); int mid = (start + end) / 2; int left = 2 * node; int right = 2 * node + 1; uppdate1(left , start , mid , l , r , val , mod); uppdate1(right , mid + 1 , end , l , r , val , mod); tree[node] = tree[left] + tree[right]; tree[node] %= mod; } void uppdate2(int node , int start , int end , int l , int r , ll val , ll mod) { if(start > r || end < l) { return; } else if(start >= l && end <= r) { tree[node] = (tree[node] * val) % mod; mul[node] = (mul[node] * val) % mod; add[node] = (add[node] * val) % mod; return; } push_down(node , start , end , mod); int mid = (start + end) / 2; int left = 2 * node; int right = 2 * node + 1; uppdate2(left , start , mid , l , r , val , mod); uppdate2(right , mid + 1 , end , l , r , val , mod); tree[node] = tree[left] + tree[right]; tree[node] %= mod; } ll query(int node , int start , int end , int l , int r , ll mod) { if(start > r || end < l) { return 0; } if(start >= l && end <= r) { return tree[node] % mod; } push_down(node , start , end , mod); int mid = (start + end) / 2; int left = 2 * node; int right = 2 * node + 1; ll left_sum = query(left , start , mid , l , r , mod); ll right_sum = query(right , mid + 1 , end , l , r , mod); return (left_sum + right_sum) % mod; } void solve() { int n, q; ll mod; cin >> n >> q >> mod; for(int i = 1; i <= n; i++) { cin >> a[i]; } buildtree(1, 1, n, mod); while(q--) { int op, x, y; ll k; cin >> op; if(op == 1) { cin >> x >> y >> k; uppdate2(1, 1, n, x, y, k % mod, mod); } else if(op == 2) { cin >> x >> y >> k; uppdate1(1, 1, n, x, y, k % mod, mod); } else if(op == 3) { cin >> x >> y; cout << query(1, 1, n, x, y, mod) % mod << endl; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0 ; }

线段树3（动态开点）

当n的值非常大，但是一个区间的值可以用某个公式去计算m是正常的时候可以这样写O(mlog

n)的复杂度。特点在于左右子数不在是简单的2*n，以及2*n+1,我们的树只有当必须用到他的时候才去建立，也就是只有不得不访问左右子树的时候才去创建他们，因为这个区间没改变所以他的值可以直接用公式计算。

#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define int unsigned long long #define ld long double const int INF = 0x3f3f3f3f3f3f3f3f; const int MAX = LLONG_MAX; const int N = 2e6 + 10; int tree[4*N + 1]; int l[4*N + 1]; int r[4*N + 1]; int lazy[4*N + 1]; int tot = 0;//创建的编号 int build_tree(int ql , int qr) { ++tot; tree[tot] = (qr + ql) * (qr - ql + 1) /2; lazy[tot] = 0; l[tot] = 0; r[tot] = 0; return tot; } void push_down(int node , int start , int end) { if(lazy[node] != 0 && start != end) { int mid = (start + end)/2; if(!l[node]) l[node] = build_tree(start , mid); if(!r[node]) r[node] = build_tree(mid + 1 , end); tree[l[node]] += (mid - start + 1LL)* lazy[node]; lazy[l[node]] += lazy[node]; tree[r[node]] += (end - mid) * lazy[node]; lazy[r[node]] += lazy[node]; lazy[node] = 0; } } void update(int &node , int start , int end , int ql , int qr , int val) { if(start > qr || end < ql) { return; } if(!node) node = build_tree(start , end); if(start >= ql && end <= qr) { tree[node] += (end - start + 1LL) * val; lazy[node] += val; } else { push_down(node , start , end); int mid = (start + end) / 2; if(!l[node]) l[node] = build_tree(start , mid); if(!r[node]) r[node] = build_tree(mid + 1 , end); update(l[node] , start , mid , ql , qr , val); update(r[node] , mid + 1 , end , ql , qr , val); tree[node] = tree[l[node]] + tree[r[node]]; } } int query(int node , int start , int end, int ql , int qr) { if(start > qr || end <ql) { return 0; } if(!node) { int L = max(ql , start); int R = min(qr , end); if(L > R) return 0; return (R + L) * (R - L + 1)/2; }//编号为0，即没有创建这个区间 if(start >= ql && end <= qr) { return tree[node]; } else { push_down(node, start , end); int mid = (start + end)/2; int left_sum = query(l[node] , start , mid , ql , qr); int right_sum = query(r[node] , mid + 1 , end , ql , qr); return left_sum + right_sum; } } void solve() { int n , m; cin >> n >> m ; int root = build_tree(1 , n); while(m--) { int op , ql , qr; cin >> op >> ql >> qr; if(op == 1) { int k; cin >> k; update(root , 1 , n , ql , qr , k); } else if(op == 2) { cout << query(root , 1 , n , ql , qr) << endl; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while(t--) { solve(); } return 0 ; }

树状数组1（区间修改，区间求和）

维护俩个数组bit1，bit2。一个为差分数组用于修改。一个为前缀和数组用于求和。

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ull unsigned long long #define ld long double const int INF = 0x3f3f3f3f3f3f3f; const int inf = 0x3f3f3f3f; const int N = 1e5 + 10; int bit1[N], bit2[N];//差分数组和加权差分数组； int lowbit(int x) { return x & (-x); } void add(int bit[N] , int x , int d , int n) { while(x <= n) { bit[x] += d; x += lowbit(x); } } int sum(int bit[N] , int x) { int res = 0; while(x > 0) { res += bit[x]; x -= lowbit(x); } return res; } void solve() { int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i++) { int x; cin >> x; add(bit1 , i , x , n); add(bit1 , i + 1 , -x , n); add(bit2 , i , i*x , n); add(bit2 , i + 1 , -(i + 1)*x , n); } while(m--) { int op; cin >> op; if(op == 1) { int x , y , k; cin >> x >> y >> k; add(bit1 , x , k , n); add(bit1 , y + 1 , -k , n); add(bit2 , x , x*k , n); add(bit2 , y + 1 , - (y + 1)*k , n); } if(op == 2) { int x , y; cin >> x >> y; cout << (y + 1)*sum(bit1 , y) - sum(bit2 , y) - (x*sum(bit1 , x - 1) - sum(bit2 , x - 1)) << endl; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0; }

树状数组2（单点修改，区间求和）

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ull unsigned long long #define ld long double const int INF = LLONG_MAX; const int N = 5e5 + 10; int tree[N]; int lowbit(int x) { return x & (-x); } //用于更新第x个数； void add(int x , int d , int n) { while(x <= n) { tree[x] += d; x += lowbit(x); } } //用于计算前x的和； int sum(int x) { int sum = 0; while(x > 0) { sum += tree[x]; x -= lowbit(x); } return sum; } void solve() { int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i++) { int x; cin >> x; add(i , x , n); }//建树； while(m--) { int op; cin >> op; if(op == 1) { int x , k; cin >> x >> k; add(x , k , n); } if(op == 2) { int x , y; cin >> x >> y; cout << sum(y) - sum(x - 1) << endl; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0 ; }

树状数组3（区间修改，单点查询）

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ull unsigned long long #define ld long double const int INF = LLONG_MAX; const int N = 5e5 + 10; //tree的定义为差分数组diff[i] int tree[N]; int lowbit(int x) { return x & (-x); } //tree[x]加上d void add(int x , int d , int n) { while(x <= n) { tree[x] += d; x += lowbit(x); } } //求tree[x]的前缀和,因为tree是差分数组，因此sum(x)就是a[x]; int sum(int x) { int sum = 0; while(x > 0) { sum += tree[x]; x -= lowbit(x); } return sum; } void solve() { int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i++) { int x; cin >> x; add(i , x , n); add(i + 1 , -x , n); } while(m--) { int op; cin >> op; if(op == 1) { int x , y , k; cin >> x >> y >> k; add(x , k , n); add(y + 1 , -k , n); } if(op == 2) { int x; cin >> x; cout << sum(x) << endl; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0 ; }

字典树（字符串）

O2优化，一颗输tire[i][j]维护节点i有没有指向字符j的边，没有tire[i][j]就为0，有dp[i][j]就是i通过j指向的点tot的节点代数，用于快速获得n个字符串里，多少前缀为目标字符串。

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ull unsigned long long #define ld long double const int INF = 0x3f3f3f3f3f3f3f3f; const int MAX = LLONG_MAX; const int N = 3e6 + 10; const int mod = 998244353; int dx[4] = {1 , -1 , 0 , 0}; int dy[4] = {0 , 0 , 1 , -1}; int tire[N][65]; int tot = 0; int pass[N]; int cnt[N]; int get(char c) { if (c >= 'A' && c <= 'Z') { return c - 'A'; } if (c >= 'a' && c <= 'z') { return c - 'a' + 26; } if (c >= '0' && c <= '9') { return c - '0' + 52; } } void insert(string &s) { int u = 0; for(auto c : s) { int v = get(c); if(!tire[u][v]) tire[u][v] = ++tot; u = tire[u][v]; pass[u]++;//这个前缀出现的次数++ } cnt[u]++;//到这里结束的次数，也就是一个完整单词的次数 } int query(string s) { int u = 0; for(auto c : s) { int v = get(c); if(!tire[u][v]) return 0; u = tire[u][v]; } return pass[u];//返回前缀中有string的数量 } int query2(string s) { int u = 0; for(auto c : s) { int v = get(c); if(!tire[u][v]) return 0; u = tire[u][v]; } return cnt[u];//返回完整string这个单词的数量 } void solve() { for(int i = 0 ; i <= tot ; i++) { for(int j = 0 ; j < 65 ; j++) { tire[i][j] = 0; } pass[i] = 0; } tot = 0; int n , q; cin >> n >> q; for (int i = 1 ; i <= n ; i++) { string s; cin >> s; insert(s); } while (q--) { string s; cin >> s; cout << query(s) << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; cin >> t; while(t--) { solve(); } return 0; }

字典树（异或最大）

把数字转化为01字符串，全看成32位，query的时候尽量选择当前（0/1）的反符

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ull unsigned long long #define ld long double const int INF = 0x3f3f3f3f3f3f3f3f; const int MAX = LLONG_MAX; const int N = 7e6 + 10; const int mod = 998244353; int dx[4] = {1 , -1 , 0 , 0}; int dy[4] = {0 , 0 , 1 , -1}; int bigpow(int a , int b) { int res = 1; while (b > 0) { if(b & 1) res = res * a; a = a * a; b >>= 1; } return res; } int tire[N][2]; int tot = 0; void insert(int x) { int u = 0; for(int i = 31 ; i >= 0 ; i--) { int v = (x >> i) & 1;//x的第i位是0还是1 if(!tire[u][v]) tire[u][v] = ++tot; u = tire[u][v]; } } int query(int x) { int u = 0; int ans = 0; for(int i = 31 ; i >= 0 ; i--) { int v = (x >> i) & 1;//x的第i位是0还是1 if(tire[u][v^1]) { u = tire[u][v^1]; ans += bigpow(2 , i); } else { u = tire[u][v]; } } return ans; } void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1 ; i <= n ; i++) { cin >> a[i]; insert(a[i]); } int ans = 0; for(int i = 1 ; i <= n ; i++) { ans = max(ans , query(a[i])); } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while(t--) { solve(); } return 0; }

线性基（维护异或最大，最小，前k大）

​ #include <bits/stdc++.h> using namespace std; #define int long long struct LinearBasis { int basis[64]; // 存 64 位，支持 long long LinearBasis() { memset(basis, 0, sizeof(basis)); } // ============ 插入 ============ // 返回 true: 插入成功, false: x 能被已有基表示 bool insert(int x) { for (int k = 63; k >= 0; k--) { if (!(x >> k & 1)) continue; // 这一位是 0，跳过 if (!basis[k]) { // 格子空着，占住 basis[k] = x; return true; } x ^= basis[k]; // 撞车，消掉最高位 } return false; // 消成 0 了，多余 } // ============ 异或最大值 ============ // 从高位往低位贪心，能让 res 变大就异或 int maxXor() { int res = 0; for (int k = 63; k >= 0; k--) if ((res ^ basis[k]) > res) res ^= basis[k]; return res; } // ============ 异或最小值 ============ int minXor() { for (int k = 0; k <= 63; k++) if (basis[k]) return basis[k]; return 0; } // ============ 判断 x 能否被异或出来 ============ bool canMake(int x) { for (int k = 63; k >= 0; k--) if (x >> k & 1) x ^= basis[k]; return x == 0; } // ============ 合并两个线性基 ============ void merge(const LinearBasis &other) { for (int k = 63; k >= 0; k--) if (other.basis[k]) insert(other.basis[k]); } // ============ 求第 k 小异或值 ============ // 需要先 rebuild()，再取 k 的二进制位 int tmp[64], cnt; void rebuild() { // 消成行最简形：高位基不包含低位的 1 for (int k = 63; k >= 0; k--) for (int j = k - 1; j >= 0; j--) if (basis[k] >> j & 1) basis[k] ^= basis[j]; // 收集所有非零基 cnt = 0; for (int k = 0; k <= 63; k++) if (basis[k]) tmp[cnt++] = basis[k]; } int kth(int k) { // k 从 0 开始（0 是第 0 小） // 如果有零元素（原始集合有空子集），k 不用减 if (k >= (1LL << cnt)) return -1; // 超范围 int res = 0; for (int i = 0; i < cnt; i++) if (k >> i & 1) res ^= tmp[i]; return res; } }; // ============ 测试 ============ signed main() { LinearBasis lb; // 插入 [3, 5, 6] cout << "插入 3: " << (lb.insert(3) ? "成功" : "多余") << endl; cout << "插入 5: " << (lb.insert(5) ? "成功" : "多余") << endl; cout << "插入 6: " << (lb.insert(6) ? "成功" : "多余") << endl; cout << "\n异或最大值: " << lb.maxXor() << endl; // 6 cout << "异或最小值: " << lb.minXor() << endl; // 3 cout << "4 能造?: " << lb.canMake(4) << endl; // 0 (不能) cout << "6 能造?: " << lb.canMake(6) << endl; // 1 (能) // 第 k 小 lb.rebuild(); cout << "\n第0小: " << lb.kth(0) << endl; // 0 (空子集) cout << "第1小: " << lb.kth(1) << endl; // 3 cout << "第2小: " << lb.kth(2) << endl; // 5 cout << "第3小: " << lb.kth(3) << endl; // 6 // 合并 LinearBasis lb2; lb2.insert(7); lb2.insert(1); lb.merge(lb2); cout << "\n合并后最大: " << lb.maxXor() << endl; // 7 return 0; } [点击并拖拽以移动] ​

对顶堆（动态维护中位素）

还可以用来：

第 k 大 / 第 k 小
第 k 大：小根堆维护前 k 大，堆顶即答案
第 k 小：大根堆维护前 k 小，堆顶即答案

窗口滑动时，需要插入新数 + 删除旧数。用两个堆 + 延迟删除（hash计数）：

堆只能高效删堆顶，但滑动窗口需要删除任意位置的元素（窗口最左边要移走）。

解决：不立即真删，先打标记，等它被顶到堆顶时再删。

意思就是对窗口滑动的时候，对元素打一个标记，然后没被标记过，那么他就是合法的，标记过

// 对顶堆 priority_queue<int> maxHeap; // 大根堆，存小的一半 priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，存大的一半 unordered_map<int, int> lazy; // 延迟删除计数 int maxSize = 0, minSize = 0; // 分别记录两堆有效元素个数 // 清理两个堆顶的"待删元素" void clean() { while (!maxHeap.empty() && lazy[maxHeap.top()] > 0) { lazy[maxHeap.top()]--; maxHeap.pop(); } while (!minHeap.empty() && lazy[minHeap.top()] > 0) { lazy[minHeap.top()]--; minHeap.pop(); } } // 平衡两堆 void balance() { if (maxSize > minSize + 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); maxSize--; minSize++; } else if (minSize > maxSize) { maxHeap.push(minHeap.top()); minHeap.pop(); minSize--; maxSize++; } clean(); // 平衡后也要清理 } // 插入 void add(int x) { if (maxHeap.empty() || x <= maxHeap.top()) { maxHeap.push(x); maxSize++; } else { minHeap.push(x); minSize++; } balance(); } // 删除 void remove(int x) { lazy[x]++; // 只打标记！ if (x <= maxHeap.top()) maxSize--; else minSize--; balance(); } double getMedian() { clean(); if (maxSize == minSize) return ((double)maxHeap.top() + minHeap.top()) / 2; else return maxHeap.top(); }

因子分解

求1e6内所有数的所有因子，因为存所有因子开销太多，只需存最小因子，后续访问时再处理

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ull unsigned long long
#define ld long double
const int MAX = LLONG_MAX;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;

int f[N];
void fmi() {
for(int i = 2 ; i <= 2e5 ; i++) {
if(f[i] == 0) {
f[i] = i;//质数本身;
for(int j = i * i ; j <= 2e5 ; j+=i){
if(f[j] == 0) f[j] = i;
}
}
}
}

//处理每个数去平方因子后//每个p一定是一个质因子；因此这个写法也可以用于快速求x有哪些质因子
int fx(int x) {
int res = 1;
while(x != 1) {
int p = f[x];
int cnt = 0;
while(x%p == 0) {
x/=p;
cnt++;
}
if(cnt%2 == 1) {
res*=p;
}
}
return res;
}


void solve() {
fmi();
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
return 0 ;
}

单调队列

维护某个窗口满足某种单调性或者，这个窗口内的最大最小值

#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define ull unsigned long long #define ld long double const ll MAX = LLONG_MAX; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 2e5 + 10; void solve() { int n , k; cin >> n >> k; vector<int> a(n); for(int i = 0 ; i < n ; i++) cin >> a[i]; deque<int> mx; deque<int> mi; vector<int> ans_mx; vector<int> ans_mi; for(int r = 0 ; r < n ; r++) { while(!mx.empty() && a[mx.back()] <= a[r]) { mx.pop_back(); } while(!mx.empty() && mx.front() < r - k + 1) { mx.pop_front(); } mx.push_back(r); while(!mi.empty() && a[mi.back()] >= a[r]) { mi.pop_back(); } while(!mi.empty() && mi.front() < r - k + 1) { mi.pop_front(); } mi.push_back(r); if(r + 1 >= k) { ans_mx.push_back(mx.front()); ans_mi.push_back(mi.front()); } } // cout << "!!!!" << endl; for(int i = 0 ; i < (int)ans_mi.size() ; i++) { cout << a[ans_mi[i]] << " "; } cout << endl; for(int i = 0 ; i < (int)ans_mx.size() ; i++) { cout << a[ans_mx[i]] << " "; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while(t--) { solve(); } return 0 ; }