数据结构
（如果有的话） 读者请先看底部说明
1.并查集
并查集是一种能够判断两个元素是否属于同一个集合的数据结构，主要有操作有：将两个集合合并；查询一个元素所在的集合。
查询：
int fid(int x){
if(fa[x]==x) return x;
return fa[x]=fid(fa[x]);
}
合并
void merge(int x,int y){
x=fa[x],y=fa[y];
if(x==y) return;
fa[x]=y;
}
2.线段树
(1).基础
略
(2).扫描线
_1.求面积
首先将点离散化。将每一根线段用线段树上的一个点表示，线段树上的每一个点代表的线段都是右端点减去左端点
，注意叶子节点不能产生贡献。最后按线段的高度排序，并加上
标签。
_2.特殊意义的扫描线
可以处理除去~
对
~
的贡献的问题。
同样将每根线段的左右端点单独列出来，并打上标签，类似于高度按照某个量排序。
_3.李超线段树
李超线段树用于解决：在平面直角坐标系中插入线段，问一个在哪一条线段上取到最大的
。
原理：两条线段最多只有一个交点，根据这点，对一个区间，李超线段树只维护在该区间内在大多数时候最大(表现为该线段在当前区间
处的
比其它线段都大)的线段，而反常的时候怎么办呢？由于两条线段最多只有一个交点，反常的位置只能在左或右的一段，那么向下递归更新反常的那一段即可，直到确定每一段区间的大多数时候
最大的线段。查询时，由于是单点查询，可以
直接递归到底。由于和其它线段树不同，该线段树只维护大多数时候正确的那个答案，所以一定要递归到底，且要在每一层都取
。
代码：
#include<bits/stdc++.h>
using namespace std;
int m,ans,tot;
const int inf=1e9+7;
const double eps=1e-10;
struct o{
int xma,xmi;
double k,b;
double operator ()(int x){
if(x<=xma&&x>=xmi) return 1.0*(k*x+b);
return -inf;
}
}a[5000100];
struct oo{
int tree[5000100];
pair<double,int> ma(pair<double,int>a,pair<double,int>b ){
if(a.first-b.first>eps) return a;
if(b.first-a.first>eps) return b;
return a.second<b.second?a:b;
}
int ls(int k){return k<<1;}
int rs(int k){return k<<1|1;}
void change(int k,int l,int r,int x,int y,int v){
if(x<=l&&y>=r){
if(!tree[k]){
tree[k]=v;
return;
}
int mid=(l+r)>>1;
if(a[v](mid)-a[tree[k]](mid)>eps) swap(v,tree[k]);
if(a[v](l)-a[tree[k]](l)>eps||(fabs(a[v](l)-a[tree[k]](l))<=eps&&v<tree[k])) change(ls(k),l,mid,x,y,v);
if(a[v](r)-a[tree[k]](r)>eps||(fabs(a[v](r)-a[tree[k]](r))<=eps&&v<tree[k])) change(rs(k),mid+1,r,x,y,v);
return;
}
int mid=(l+r)>>1;
if(x<=mid) change(ls(k),l,mid,x,y,v);
if(y>mid) change(rs(k),mid+1,r,x,y,v);
return;
}
pair<double,int> ask(int k,int l,int r,int x){
pair<double,int>res;
if(tree[k]) res=make_pair(a[tree[k]](x),tree[k]);
if(l==r){
return res;
}
int mid=(l+r)>>1;
if(x<=mid) res=ma(ask(ls(k),l,mid,x),res);
else res=ma(ask(rs(k),mid+1,r,x),res);
return res;
}
}t;
int read(){
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
m=read();
while(m--){
int op=read();
if(op){
int x0=read(),y0=read();
int x1=read(),y1=read();
x0=(x0+ans-1)%39989+1;
y0=(y0+ans-1)%(1000000000)+1;
x1=(x1+ans-1)%39989+1;
y1=(y1+ans-1)%(1000000000)+1;
if(x1==x0){
++tot;
a[tot].xma=a[tot].xmi=x1;
a[tot].b=max(y1,y0);
a[tot].k=0;
}else{
a[++tot].xma=max(x1,x0);
a[tot].xmi=min(x1,x0);
a[tot].k=1.0*(y0-y1)/(x0-x1);
a[tot].b=1.0*(1.0*y1-1.0*a[tot].k*x1);
}
t.change(1,1,39990,min(x1,x0),max(x1,x0),tot);
}else{
int x=read();x=(x+ans-1)%39989+1;
ans=t.ask(1,1,39990,x).second;
printf("%d\n",ans);
}
}
return 0;
}
当然李超线段树也可以维护区间最值：
代码：
#include<bits/stdc++.h>
using namespace std;
long long dis[1000100],atid[1000100],e,head[1000100],dep[1000100],siz[1000100],fa[1000100],son[1000100];
long long top[1000100],id[1000100],dfn,n,m,tot;
const long long inf=123456789123456789;
struct o{
long long ne,to,w;
}a[1000100];
struct oo{
long long xma,xmi,k,b;
long long operator ()(long long x){
return k*x+b;
}
}g[1000100];
struct ooo{
long long tree[1000100],mi[1000100];
void init(){
for(long long i=0;i<=1000000;i++){
mi[i]=inf;
}
}
long long ls(long long k){return k<<1;}
long long rs(long long k){return k<<1|1;}
void change(long long k,long long l,long long r,long long x,long long y,long long v){
if(x<=l&&y>=r){
mi[k]=min(mi[k],min(g[v](dis[atid[l]]),g[v](dis[atid[r]])));//维护答案
long long mid=(l+r)>>1;
if(g[v](dis[atid[mid]])<g[tree[k]](dis[atid[mid]])){
swap(v,tree[k]);//维护大多数时候最优的 注意答案不能用mid更新
}
if(l==r) return;
if(g[v](dis[atid[l]])<g[tree[k]](dis[atid[l]])) change(ls(k),l,mid,x,y,v);
if(g[v](dis[atid[r]])<g[tree[k]](dis[atid[r]])) change(rs(k),mid+1,r,x,y,v);
mi[k]=min(mi[k]/*不要忘了和自己比较*/,min(mi[ls(k)],mi[rs(k)]));//
return;
}
long long mid=(l+r)>>1;
if(x<=mid) change(ls(k),l,mid,x,y,v);
if(y>mid) change(rs(k),mid+1,r,x,y,v);
mi[k]=min(mi[k],min(mi[ls(k)],mi[rs(k)]));//
}
long long ask(long long k,long long l,long long r,long long x,long long y){
if(x<=l&&y>=r){
return mi[k];
}
long long mid=(l+r)>>1,res=min(g[tree[k]](dis[atid[max(l,x)]]),g[tree[k]](dis[atid[min(r,y)]]));//
if(x<=mid) res=min(res,ask(ls(k),l,mid,x,y));
if(y>mid) res=min(res,ask(rs(k),mid+1,r,x,y));
return res;
}
}t;
void dd(long long u,long long v,long long w){
a[++e].ne=head[u];
a[e].to=v;
a[e].w=w;
head[u]=e;
}
void dfs1(long long x,long long f){
dep[x]=dep[f]+1;
siz[x]=1;
fa[x]=f;
for(long long i=head[x];i;i=a[i].ne){
long long v=a[i].to;
if(v==f) continue;
dis[v]=dis[x]+a[i].w;
dfs1(v,x);
siz[x]+=siz[v];
if(!son[x]||siz[son[x]]<siz[v]) son[x]=v;
}
}
void dfs2(long long x,long long tp){
top[x]=tp;
id[x]=++dfn;
atid[dfn]=x;
if(!son[x]) return;
dfs2(son[x],tp);
for(long long i=head[x];i;i=a[i].ne){
long long v=a[i].to;
if(v==fa[x]||v==son[x]) continue;
dfs2(v,v);
}
}
long long lca(long long x,long long y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
long long getdis(long long x,long long y){
return dis[x]+dis[y]-(dis[lca(x,y)]<<1);
}
void change(long long x,long long y,long long v){
while(top[x]!=top[y]){
t.change(1,1,n,id[top[x]],id[x],v);
x=fa[top[x]];
}
t.change(1,1,n,id[y],id[x],v);
}
long long ask(long long x,long long y){
long long res=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=min(res,t.ask(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=min(res,t.ask(1,1,n,id[x],id[y]));
return res;
}
long long read(){
char ch=getchar();long long x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
n=read();m=read();
for(long long i=1;i<n;i++){
long long u=read(),v=read(),w=read();
dd(u,v,w);dd(v,u,w);
}
t.init();
dfs1(1,0);dfs2(1,1);
g[0].b=inf; //
while(m--){
long long op=read(),x=read(),y=read();
if(op==1){
long long k=read(),b=read();
long long anc=lca(x,y);
g[++tot].k=-k;
g[tot].b=k*dis[x]+b;
g[tot].xma=dis[x];
g[tot].xmi=dis[anc];
change(x,anc,tot);
g[++tot].k=k;
g[tot].b=b+k*dis[x]-2*k*dis[anc];
g[tot].xma=dis[y];
g[tot].xmi=dis[anc];
change(y,anc,tot);
}else{
printf("%lld\n",ask(x,y));
}
}
return 0;
}
可以和斜率优化结合：
转移显然有：
暴力，考虑优化。
先把平方展开：。
因为我们肯定是从推到
，所以把
当成已知量处理，整理得到：
因为是从
到
枚举的，所以
是变化的。显然对于每一个
,把
看成自变量，都有一个关于
的函数
。这样就是李超线段树的模板题了。
代码：
#include<bits/stdc++.h>
using namespace std;
long long h[1000100],w[1000100],sum[1000100],tot;
struct oo{
long long k,b;
long long operator ()(long long x){
return k*x+b;
}
}a[1000100];
struct o{
long long tree[8000100];
long long ls(long long k){return k<<1;}
long long rs(long long k){return k<<1|1;}
void change(long long k,long long l,long long r,long long x,long long y,long long v){
if(x<=l&&y>=r){
long long mid=(l+r)>>1;
if(a[v](mid)<a[tree[k]](mid)) swap(v,tree[k]);
if(l==r) return;
if(a[v](l)<a[tree[k]](l)) change(ls(k),l,mid,x,y,v);
if(a[v](r)<a[tree[k]](r)) change(rs(k),mid+1,r,x,y,v);
return;
}
long long mid=(l+r)>>1;
if(x<=mid) change(ls(k),l,mid,x,y,v);
if(y>mid) change(rs(k),mid+1,r,x,y,v);
}
long long ask(long long k,long long l,long long r,long long x){
if(l==r){
return a[tree[k]](l);
}
long long mid=(l+r)>>1;
long long res=a[tree[k]](x);
if(x<=mid) res=min(res,ask(ls(k),l,mid,x));
else res=min(res,ask(rs(k),mid+1,r,x));
return res;
}
}t;
long long read(){
char ch=getchar();long long x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
long long pf(long long x){return x*x;}
int main(){
int n=read();
for(int i=1;i<=n;i++) h[i]=read();
for(int i=1;i<=n;i++){
long long x=read();sum[i]=sum[i-1]+x;
}
a[0].b=1e18+7;
a[++tot].k=-2*h[1];
a[tot].b=pf(h[1])-sum[1];
t.change(1,0,1000000,0,1000000,tot);
for(int i=2;i<n;i++){
long long x=t.ask(1,0,1000000,h[i])+pf(h[i])+sum[i-1];
a[++tot].k=-2*h[i];
a[tot].b=pf(h[i])-sum[i]+x;
t.change(1,0,1000000,0,1000000,tot);
}
printf("%lld\n",t.ask(1,0,1000000,h[n])+pf(h[n])+sum[n-1]);
return 0;
}
_4.可持久化线段树
@1基础
先看最简单的场景：对一个序列，每次更新只修改一个数，并把新序列当作一个新的版本。要查询某个版本序列的区间和。如果只保留最后版本的话很容易想到用线段树维护。但现在要维护多个版本，最简单的线段树已经不能达到目标了。思考一下，每次只改一个数，那么序列每次的变化其实是很小的，如果用线段树维护的话，不需要对整个序列重新建立一棵完整的线段树，只维护变化的节点就行了。根据这个思路，我们就可以创造出可持久化线段树了。
具体是这样操作的：每次修改，沿途新建，其余复制。在经典线段树上，每次修改都会有一个树上路径，由于新版本的线段树和旧版本的不一样，但又不能覆盖旧版本，所以沿途的每个节点都要新建。根据之前的思路，新节点的大部分信息与旧节点相同，所以可以先复制旧节点信息，只修改不同的部分。具体见代码：
int change(int pre,int l,int r,int x,int v){
int k=++tot;
tree[k]=tree[pre];
if(l==r){
tree[k].sum=v;
return;
}
int mid=(l+r)>>1;
if(x<=mid) tree[k].ls=change(tree[pre].ls,l,mid,x,v);
else tree[k].rs=change(tree[pre].rs,mid+1,r,x,v);
tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;
return k;
}
不难发现一次修改最多修改个节点，时间复杂度、空间复杂度均为
。
那么区间修改、新建版本呢？其实也是可以的。由于懒标记的存在，我们可以积蓄修改操作，直到需要的时候再下传。主要操作依旧是沿途修改，其余复制，有些不同的是，在下传操作时也需要新建节点(因为下传之后信息发生变化，而旧节点可能仍在某个版本中需要被复用，所以需要新节点维护)，但如果是在修改操作时下传，在下传之后立马就要修改，那么刚刚新建的节点可能就直接被浪费了。但其实这不要紧，即使有浪费的情况，一次修改消耗的空间依然是级别的，总空间复杂度为
，浪费只会加常数，不影响算法的正确性。
模板题：
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,q,a[1000100],tot,rt[1000100];
struct o{
long long ls,rs,sum,lan;
}tree[10000100];
long long clone(long long v){
long long k=++tot;
tree[k]=tree[v];
return k;
}
void pup(long long k){
tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;
}
void build(long long &k,long long l,long long r){
if(!k) k=++tot;
if(l==r){
tree[k].sum=a[l];
return;
}
long long mid=(l+r)>>1;
build(tree[k].ls,l,mid);
build(tree[k].rs,mid+1,r);
pup(k);
}
void add(long long k,long long l,long long r,long long v){
tree[k].sum+=(r-l+1)*v;
tree[k].lan+=v;
}
void pud(long long k,long long l,long long r,long long mid){
if(tree[k].lan){
tree[k].ls=clone(tree[k].ls);
tree[k].rs=clone(tree[k].rs);
add(tree[k].ls,l,mid,tree[k].lan);
add(tree[k].rs,mid+1,r,tree[k].lan);
tree[k].lan=0;
}
}
long long change(long long pre,long long l,long long r,long long x,long long y,long long v){
long long k=clone(pre);
if(x<=l&&y>=r){
add(k,l,r,v);
return k;
}
long long mid=(l+r)>>1;
pud(k,l,r,mid);
if(x<=mid) tree[k].ls=change(tree[k].ls,l,mid,x,y,v);
if(y>mid) tree[k].rs=change(tree[k].rs,mid+1,r,x,y,v);
pup(k);
return k;
}
long long ask(long long k,long long l,long long r,long long x,long long y){
if(x<=l&&y>=r){
return tree[k].sum;
}
long long mid=(l+r)>>1,res=0;
pud(k,l,r,mid);
if(x<=mid) res=ask(tree[k].ls,l,mid,x,y);
if(y>mid) res+=ask(tree[k].rs,mid+1,r,x,y);
return res;
}
long long read(){
char ch=getchar();long long x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
n=read();q=read();
for(long long i=1;i<=n;i++) a[i]=read();
build(rt[0],1,n);
long long t=0;
while(q--){
char op;cin>>op;
long long x=read();
if(op=='C'){
long long y=read(),z=read();
rt[t+1]=change(rt[t],1,n,x,y,z);
++t;
}else if(op=='Q'){
long long y=read();
printf("%lld\n",ask(rt[t],1,n,x,y));
}else if(op=='H'){
long long y=read(),z=read();
printf("%lld\n",ask(rt[z],1,n,x,y));
}else{
t=x;
}
}
return 0;
}
@2经典应用
最基本的就是版本问题，即：修改但不抛弃，即我不仅会用到修改后的，修改前的我也会用到。
另一种就是可以把可持久化值域线段树当成前缀和处理。
即：除了版本问题，还有就是特殊的区间问题了，通常与“一个数在某个区间出现了多少次”有关(比如区间第小是谁)。这时就可以建立可持久化值域线段树了。每插入一个值都当作是对原序列修改产生的一个新的版本，这样就可以用类似前缀和的方式去处理线段树上节点了。本质是：在
版本上
的出现次数
版本上
的出现次数就是区间
上
的出现次数。值域线段树上每个节点可以维护区间内所有数的出现次数之和，这样就很好处理了。
3.树状数组
略
4.分块
易错点
一定要考虑左右端点在同一个块内的情况，要特殊处理！！！
正文
分块就是将暴力做法放到一个块里面处理。询问时，两边的散块可以暴力处理，中间的整块可以非常快速地得到答案，从而将时间复杂度降到。
经验而言，块内对问题的答案是一定要维护的。
经典套路：
(1).带单点修改；找一段区间有多少数大于
新创建一个数组，用来存储一个块内的升序顺序。
询问：对散块直接暴力处理，整块用在块内
数组快速查询，时间复杂度
修改：单点直接单个元素冒泡排序。如果是区间修改，尽量不要使用，很慢，可以观察一些性质来处理。
总复杂度。
(2).求区间众数(具体到是哪一个数)(不带修改)
维护为块
的众数，
为前
个块中
的出现次数。那么对一个询问，答案只可能为：散块里面出现过的数，中间整块的众数，数量是
级别的，直接暴力枚举可能的答案，时间复杂度
。
5.莫队
根据排序对暴力进行优化的离线算法。
(1).经典莫队
按左端点所在块排序，相同则升序排序。左端点移动复杂度
，右端点时间复杂度
，总时间复杂度
。
(2).带修莫队
带修改时，多出一个变量：修改的时间。变成的三维问题。将块长调整为
，按依次按左端点所在块、右端点所在块、时间升序排序。左右端点移动很好处理，时间流动时要能同时做到实现修改和消除修改的影响(通常要用到
)。总时间复杂度
。
(3).回滚莫队
当增加操作很好处理，但删除操作异常困难的时候，就可以上回滚莫队。
因为右端点单调递增，所以只有增加操作，要删除的只有左端点。那么可以考虑让左端点也只有增加操作，那就是从左端点所在块的右端点开始向左回滚，这样就只有增加操作了，且左端点回滚的时间复杂度仍为
。总时间复杂度
。
声明（一定要看）
虽然我的文章应该没人看但还是要说明：这篇文章的初衷是自用的，主要写给自己看以总结提高、方便复习的，对内容的正确性不做任何保证（当然大部分应该是对的），有错误可以指出
原始链接：a
查看13道真题和解析