线段树区间加法 区间求和#includebits/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区间加法和乘法 区间求和注意懒标记维护形式;#includebits/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(mlogn)的复杂度。特点在于左右子数不在是简单的2*n以及2*n1,我们的树只有当必须用到他的时候才去建立也就是只有不得不访问左右子树的时候才去创建他们因为这个区间没改变所以他的值可以直接用公式计算。#includebits/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区间修改区间求和维护俩个数组bit1bit2。一个为差分数组用于修改。一个为前缀和数组用于求和。#includebits/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单点修改区间求和#includebits/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区间修改单点查询#includebits/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个字符串里多少前缀为目标字符串。#includebits/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的反符#includebits/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; vectorint 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_queueint maxHeap; // 大根堆存小的一半 priority_queueint, vectorint, greaterint minHeap; // 小根堆存大的一半 unordered_mapint, 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内所有数的所有因子因为存所有因子开销太多只需存最小因子后续访问时再处理#includebits/stdc.husing namespace std;#define int long long#define endl \n#define ull unsigned long long#define ld long doubleconst 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 ; ji){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 ;}单调队列维护某个窗口满足某种单调性或者这个窗口内的最大最小值#includebits/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; vectorint a(n); for(int i 0 ; i n ; i) cin a[i]; dequeint mx; dequeint mi; vectorint ans_mx; vectorint 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 ; }
线段树区间加法 区间求和#includebits/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区间加法和乘法 区间求和注意懒标记维护形式;#includebits/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(mlogn)的复杂度。特点在于左右子数不在是简单的2*n以及2*n1,我们的树只有当必须用到他的时候才去建立也就是只有不得不访问左右子树的时候才去创建他们因为这个区间没改变所以他的值可以直接用公式计算。#includebits/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区间修改区间求和维护俩个数组bit1bit2。一个为差分数组用于修改。一个为前缀和数组用于求和。#includebits/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单点修改区间求和#includebits/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区间修改单点查询#includebits/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个字符串里多少前缀为目标字符串。#includebits/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的反符#includebits/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; vectorint 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_queueint maxHeap; // 大根堆存小的一半 priority_queueint, vectorint, greaterint minHeap; // 小根堆存大的一半 unordered_mapint, 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内所有数的所有因子因为存所有因子开销太多只需存最小因子后续访问时再处理#includebits/stdc.husing namespace std;#define int long long#define endl \n#define ull unsigned long long#define ld long doubleconst 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 ; ji){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 ;}单调队列维护某个窗口满足某种单调性或者这个窗口内的最大最小值#includebits/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; vectorint a(n); for(int i 0 ; i n ; i) cin a[i]; dequeint mx; dequeint mi; vectorint ans_mx; vectorint 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 ; }
)
