爱飞鱼的blog

以一道区间和查询来说明板子如何使用 1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息 2.find的时候更新维护是子节点到根的距离 3.需要加一个查询函数，因为距离数组是开在结构体内部的。 题目描述 对于一个长度为 NNN 的整数数列 A1,A2,⋯ANA_{1}, A_{2}, \cdots A_{N}A1​,A2​,⋯AN​，小蓝想知道下标 lll 到 rrr 的部分和 ∑i=lrAi=Al+Al+1+⋯+Ar\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}i=l∑r​Ai​=Al​+Al+1​+⋯+Ar​ 是多少? 然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 MMM 个部分和的值。其中第 iii 个部分和是下标 lil_{i}li​ 到 rir_{i}ri​ 的部分和...

从单调栈到笛卡尔树 功能1：单调栈可以在线性时间内为每个数找到序列中下一个比它的大的数，以及上一个比它大的数 https://vjudge.net/problem/POJ-2796单调栈基本功能代表作 poj的c++98首先对size函数不是O（1）的，然后还卡关了同步流的cin，关键数据范围才1e5,逆天毒瘤，耽误我40min，以后poj的题目先测试一下是不是卡常数。然后我不熟悉printf的输出longlong，应该用%lld 题意：给定一个数组，找到一个区间，使得 最大化 区间里的数的和×\times×区间最小值 Sol：直接单调栈维护每个数作为最小值能到的左右边界，然后O（n)枚举更新答案即可，前缀和优化一下。 123456789101112131415161718192021222324252627282930313233343536373839404142int a[N];ll s[N];stack<int>pre;stack<int>nxt;//找到两侧第一个比它小的下标int l[N];int r[N];void...

利用优先队列维护序列前k大的和 https://codeforces.com/contest/1969/problem/D https://sua.ac/wiki/2023-icpc-nanjing/g/ https://qoj.ac/submission/408738 注意排序的技巧 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h> using namespace std;#define sz(a) int((a).size())using li = long long;int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector<int> a(n), b(n); for (auto& x : a) cin >> x; ...

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。 1234567891011121314151617181920212223242526272829303132333435363738394041int n, m;int a[N];int tr[N];vector<int>lan;int lowbit(int x){ return x&(-x);}void discrete(){ sort(lan.begin(), lan.end()); //排序 lan.erase(unique(lan.begin(), lan.end()), lan.end()); //去重}//查询int find(int x){ return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1; //返回所查询的数据的下标}void add(int x,int c){ for(int...

动态维护第k大 1234567891011121314priority_queue<int> a; //大根堆priority_queue<int,vector<int>,greater<int> > b;for(int i=1; i<=n; i++){ int x; scanf("%d",&x); if(b.empty()||x>=b.top()) b.push(x); //插入 else a.push(x); int k=max(1,i*w/100); //第k大 while(b.size()>k) a.push(b.top()), b.pop(); //调整 while(b.size()<k) b.push(a.top()), a.pop(); printf("%d ", b.top()); //取值}

对于种类并查集主要是考虑清楚到根节点距离分为几类，每一类的意义 有的题目相出d数组的含义才能想到用带权并查集 1234567891011//find函数需要变化int find(int x){ if (p[x] != x) { int root = find(p[x]); d[x] += d[p[x]]; p[x] = root; } return p[x];} 在查询过程中遇到两个不连通的点，需要合并操作，我们需要注意维护距离 123456789if(find(l)!=find(r)){//1.a[f[l]]=a[l]-d[l]2.a[f[r]]=a[r]-d[r]//现在要维护的是d[f[l]];//最终应该满足3.x=d[f[l]]=a[f[l]]-a[f[r]];//4.a[j]-a[r]=x;//将124代入3解得d[f[l]];d[f[l]]=x-d[l]+d[r];f[f[l]]=f[r];//不能颠倒顺序，先维护距离再移动根}

维护集合最值和集合全体加 你有一个可重集合初始有n个数，有4种操作，5e5次操作5e5次操作5e5次操作 向集合中加入一个数 删除集合中一个数 集合中所有数加x 查询集合最大值 进一步考虑另一个可以使用这个模型的问题。一个vector，动态在尾部增加数，删除数，边操作边求后缀和最小值 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include <bits/stdc++.h>#ifdef LOCAL#include "debug.h"#else#define deb(...)#endifusing namespace std;#define ll long long// #define int long...

线段树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125template <class Info, class Tag>struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) {...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475const int N = 1e5 + 10;int n, m;int a[N];struct Tree{ int l,r; ll sum,add; }tr[4*N];void build(int u,int l,int r){ // l=tr[u].l;r=tr[u].r; //注释掉的部分是典型的错误，对于build过程中我们是初始化编号对应区间节点，上面赋值逻辑反了 tr[u]={l,r}; if(l==r)tr[u].sum=a[l]; else{ int...

链接：https://ac.nowcoder.com/acm/contest/69510/G 来源：牛客网 你在一个星球上，外星人amiloac想让你管理一条河流，该河流有xxx段，每两段之间有一个挡板隔开，每一段都有各自的颜色aaa。你需要管理qqq天，每一天你需要做以下的一种操作。 1 l r1\ l\ r1 l r将第lll至rrr段河流的所有未打开的挡板打开。 2 x2\ x2 x询问你第xxx段河流的颜色是什么。 对于任意相邻的两段，它们之间的隔板被打开后的瞬间，河流的颜色会混合变成颜色最深的河流的颜色，aaa越大，颜色越深。 注：隔板打开后，河流的段数不会变。请注意不同寻常的空间限制！ 第一行为两个整数n,q(1≤n≤5⋅105),(1≤q≤5⋅105)n,q(1\le n \le 5 \cdot 10^5),(1\le q\le 5 \cdot 10^5)n,q(1≤n≤5⋅105),(1≤q≤5⋅105)，分别表示河流的段数和管理的天数。 第二行为nnn个整数ai(1≤i≤n),(1≤ai≤109)a_i(1\le i\le n),(1\le a_i\le...