登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.6 线段树 › 线段树 / 搜索
JSON MD

2.6 线段树

带懒标记的线段数 Lazy_Segment_Tree_ask_add
66 行
CPP JSON
【带懒标记的线段树——区间加 + 区间求和】 ▪ build(datas, tree, rt, left, right) — 递归建树:叶子存 datas[left],内部节点为左右子树之和 ▪ pushDown(tree, rt, len) — 下传懒标记:将 rt 的 lazy 加到左右子节点(同步更新 data) ▪ updateRange(tree, rt, l, r, ul, ur, val) — 区间更新 [ul,ur] 加 val:若完全覆盖则 data+=val*len 并打 lazy,否则 pushDown 后递归更新左右子树 ▪ query(tree, rt, l, r, ql, qr) — 区间查询 [ql,qr] 的和:类似 update,完全覆盖直接返回 所有操作 O(log N)。适用于区间加法+区间求和的经典问题。
C++ 66 行 CPP
struct node{
    int data,lazy;
};

void build(const vector<int>&datas,vector<node>&tree,int rt,int left,int right){
    if(left == right){
        tree[rt].data=datas[left];
        return;
    }
    int mid = left+(right-left)/2;
    build(datas,tree,2*rt,left,mid);
    build(datas,tree,2*rt+1,mid+1,right);
    tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void pushDown(vector<node>&tree,int rt, int len){
    if(tree[rt].lazy != 0){
        tree[rt*2].data += tree[rt].lazy * (len - len/2);
        tree[rt*2].lazy += tree[rt].lazy;
        tree[rt*2+1].data += tree[rt].lazy * (len/2); 
        tree[rt*2+1].lazy += tree[rt].lazy;
        tree[rt].lazy = 0;  
    }
}

int query(vector<node>&tree,int rt,int left,int right,int ql,int qr){
    if(ql > right || qr < left){
        return MIN;
    }
    if(ql <= left && qr >= right){
        return tree[rt].data;
    }
    int mid = left+(right-left)/2;
    pushDown(tree,rt,right-left+1);
    int leftsum = query(tree,2*rt,left,mid,ql,qr);
    int rightsum = query(tree,2*rt+1,mid+1,right,ql,qr);
    return leftsum+rightsum;
}
void updata(vector<node>&tree,int rt,int left,int right,int idx,int value){
    if(left == right){
        tree[rt].data = value;
        tree[rt].lazy = 0;
        return;
    }
    int mid = left+(right-left)/2;
    pushDown(tree,rt,right-left+1);
    if(idx<=mid){
        updata(tree,2*rt,left,mid,idx,value);
    }else{
        updata(tree,2*rt+1,mid+1,right,idx,value);
    }
    tree[rt].data = tree[2*rt].data+tree[2*rt+1].data;
}
void updataRange(vector<node>&tree,int rt,int left,int right,int ul,int ur,int value){
    if(ul>right||ur<left) return;
    
    if(ul<=left && ur >= right){
        tree[rt].data += value * (right - left + 1);
        tree[rt].lazy += value;
        return;
    }
    int mid = left+(right-left)/2;
    pushDown(tree,rt,right-left+1);
    updataRange(tree,2*rt,left,mid,ul,ur,value);
    updataRange(tree,2*rt+1,mid+1,right,ul,ur,value);
    tree[rt].data=tree[2*rt].data+tree[2*rt+1].data;
}
线段树 LazySegmentTree-full
63 行
CPP JSON
【通用懒标记线段树模板——Info + Tag 双模板参数】 ▪ LazySegmentTree(init) — 构造函数,用 vector<Info> init 建树,内部 lambda build 递归构建 ▪ pull(p) — 上推:info[p] = info[2p] + info[2p+1](需重载 Info 的 + 运算符) ▪ apply(p, v) — 对节点 p 应用标记 v:info[p].apply(v); tag[p].apply(v) ▪ push(p) — 下推:apply(2p, tag[p]); apply(2p+1, tag[p]); 清空 tag[p] ▪ rangeApply(p, l, r, x, y, v) — 区间更新 [x,y] 应用标记 v ▪ rangeQuery(p, l, r, x, y) — 区间查询 [x,y] ▪ Tag 结构 — 懒标记(含 apply 方法),Info 结构 — 节点信息(含 apply 和 + 运算符) 通用模板,仅需定义 Info 和 Tag 即可适配各种线段树变体(求和/最值/异或等),O(log N)。
C++ 63 行 CPP
template<class Info, class Tag> struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree(vector<Info> init) {
        n = init.size();
        info.assign(4 * n, Info());
        tag.assign(4 * n, Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        push(p);
        int m = (l + r) / 2;
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) return Info();
        if (l >= x && r <= y) return info[p];
        push(p);
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
};
struct Tag {
    LL x;
    Tag(LL x = 0) { this->x = x; }
    void apply(const Tag &t) { x += t.x; }
};
struct Info {
    LL x, l, r;
    Info(LL x = 0, LL l = 0, LL r = 0) { this->x = x; this->l = l; this->r = r; }
    void apply(const Tag &t) { if (t.x) x += t.x * (r - l + 1); }
};
Info operator+(const Info &a, const Info &b) { return Info(a.x + b.x, a.l, b.r); }
线段树- mex segment-tree-mex
82 行
CPP JSON
【线段树——区间 MEX 查询】 ▪ built(root, l, r) — 构建线段树,每个叶子对应一个值的出现位置(初始为 0),内部节点维护区间最小值 mins。同时记录 fa[pos] = 叶子在线段树中的节点编号 ▪ modify(num, pos) — 将值 num 的出现位置更新为 pos,从叶子向上 push_up 更新 mins ▪ query(l) — 二分查询:从根向下走,若左子树的 mins ≥ l 则去右子树(左边全出现过),否则去左子树。最终返回第一个出现位置 < l 的值(即 MEX-1) 所有操作 O(log N)。适用于动态维护集合的 MEX 值、博弈论 SG 函数计算。
C++ 82 行 CPP
struct tnode {
    int l, r;
    int mins;
};

struct Segment {
    tnode t[4 * N];
    int fa[4 * N];
    void built(int root, int l, int r) {
        """
        构建线段树
        :param root: 当前节点
        :param l: 左端点
        :param r: 右端点
        """
        t[root].l = l;
        t[root].r = r;
        if (l == r) {
            t[root].mins = 0;
            fa[l] = root;
            return;
        }
        int ch = root << 1;
        int mid = (l + r) >> 1;
        built(ch, l, mid);
        built(ch + 1, mid + 1, r);
        t[root].mins = min(t[ch].mins, t[ch + 1].mins);
    }
    void modify(int num, int pos) {
        """
        修改线段树
        :param num: 要修改的位置
        :param pos: 要修改的值
        """
        int root = fa[num];
        t[root].mins = pos;
        root >>= 1;
        while (root) {
            int ch = root << 1;
            t[root].mins = min(t[ch].mins, t[ch + 1].mins);
            root >>= 1;
        }
    }
    int query(int l) {
        """
        查询线段树
        :param l: 查询的左端点
        :return: 最小的未被覆盖的位置
        """
        int root = 1;
        while (t[root].l != t[root].r) {
            int ch = root << 1;
            if (t[ch].mins >= l) {
                root = ch + 1;
            } else {
                root = ch;
            }
        }
        return t[root].l - 1;
    }
} ST;

// int main() {
//     // 初始化线段树,假设值范围是1到n
//     int n;
//     cin >> n;
//     ST.built(1, 1, n);
//     // 示例:处理m次操作
//     int m;
//     cin >> m;
//     while (m--) {
//         int op, x, y;
//         cin >> op;
//         if (op == 1) {
//             cin >> x >> y;
//             ST.modify(x, y);
//         } else if (op == 2) {
//             cin >> x;
//             cout << ST.query(x) << '\n';
//         }
//     }
// }
ST表求区间最值 RMQ
20 行
CPP JSON
【ST表求区间最值(RMQ)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 关键配置: N=1e5+3,inf=2147483647 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 19 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+3,inf=2147483647;
int i,j,n,k,m,a[N],lg[N],f1[N][18],f2[N][18];
int main(){
    scanf("%d%d",&n,&k);
    for(i=0;i<=17;i++)
        for(j=0;j<=n+1;j++)
            f1[i][j]=-inf,f2[i][j]=inf;
    lg[1]=0;for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;m=lg[n];
    for(i=1;i<=n;f2[i][0]=f1[i][0],i++)scanf("%d",&f1[i][0]);
    for(i=1;i<=m;i++)
        for(j=1;j+(1<<i)-1<=n;j++)
            f1[j][i]=max(f1[j][i-1],f1[j+(1<<i-1)][i-1]),f2[j][i]=min(f2[j][i-1],f2[j+(1<<i-1)][i-1]);
    m=lg[k];
    for(i=1;i+k-1<=n;i++)printf("%d %d\n",max(f1[i][m],f1[i+k-(1<<m)][m]),min(f2[i][m],f2[i+k-(1<<m)][m]));
}
回文串 Manacher+SA+二分+ST表
104 行
CPP JSON
【回文串(Manacher+SA+二分+ST表)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void get_SA(无参数) — 获取值 void get_Height(无参数) — 获取值 void get_ST(无参数) — 获取值 int ask_min(Re l,Re r) — 核心算法函数 void check(Re x,Re len) — 判定/检查函数 void sakura(无参数) — 后缀数组 核心结构体:Suffix_Array 关键配置: N=3e5+5,logN=19 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 103 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+5,logN=19;
int n;char s[N];
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Suffix_Array{
	int m,x[N],y[N],SA[N],cnt[N],rank[N],Height[N];
	inline void get_SA(){
		m=129;
		for(Re i=1;i<=n;++i)++cnt[x[i]=s[i]];
		for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
		for(Re i=n;i>=1;--i)SA[cnt[x[i]]--]=i;
		for(Re len=1;len<=n;len<<=1){
			Re t=0;
			for(Re i=n-len+1;i<=n;++i)y[++t]=i;
			for(Re i=1;i<=n;++i)if(SA[i]>len)y[++t]=SA[i]-len;
			for(Re i=1;i<=m;++i)cnt[i]=0;
			for(Re i=1;i<=n;++i)++cnt[x[i]];
			for(Re i=2;i<=m;++i)cnt[i]+=cnt[i-1];
			for(Re i=n;i>=1;--i)SA[cnt[x[y[i]]]--]=y[i],y[i]=0;
			swap(x,y),x[SA[1]]=m=1;
			for(Re i=2;i<=n;++i)
				x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+len]==y[SA[i-1]+len])?m:++m;
			if(m>=n)break;
		}
	}
	inline void get_Height(){
		for(Re i=1;i<=n;++i)rank[SA[i]]=i;
		for(Re i=1,k=0;i<=n;++i){
			if(rank[i]==1)continue;
			if(k)--k;
			Re j=SA[rank[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
			Height[rank[i]]=k;
		}
//		for(Re i=1;i<=n;++i)printf("%d ",Height[i]);puts("");
	}
	int lg[N],dp[N][20];
	inline void get_ST(){
		lg[0]=-1;
		for(Re i=1;i<=n;++i)dp[i][0]=Height[i],lg[i]=lg[i>>1]+1;
		for(Re j=1;j<=logN;++j)
			for(Re i=1;i+(1<<j)-1<=n;++i)
				dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
	}
	inline int ask_min(Re l,Re r){
		Re m=lg[r-l+1];
		return min(dp[l][m],dp[r-(1<<m)+1][m]);
	}
	int r[N<<1];char a[N<<1];LL ans;
	inline void check(Re x,Re len){
//		printf("x=%d, len=%d\n",x,len);
		x=rank[x];Re L=x,R=x;
		if(Height[x]>=len){
			Re l=2,r=x;
			while(l<r){
				Re mid=l+r>>1;
				if(ask_min(mid,x)>=len)r=mid;
				else l=mid+1;
			}
			L=r-1;
		}
		if(Height[x+1]>=len){
			Re l=x+1,r=n;
			while(l<r){
				Re mid=l+r+1>>1;
				if(ask_min(x+1,mid)>=len)l=mid;
				else r=mid-1;
			}
			R=l;
		}
		ans=max(ans,(LL)len*(R-L+1));
	}
	inline void sakura(){
		get_SA(),get_Height(),get_ST();
		a[m=0]='$',a[++m]='|';
		for(Re i=1;i<=n;++i)a[++m]=s[i],a[++m]='|';
		for(Re i=1,R=0,mid=0;i<=m;++i){
			r[i]=i<=R?min(r[(mid<<1)-i],R-i+1):1;
			while(a[i-r[i]]==a[i+r[i]]){
				++r[i];
				if(i+r[i]-1>R)check((i>>1)-(r[i]>>1)+1,r[i]-!(i+r[i]&1));
			}
			if(i+r[i]-1>R)mid=i,R=i+r[i]-1;
		}
//		for(Re i=1;i<=m;++i)printf("%d ",r[i]);puts("");
		printf("%lld\n",ans);
	}
}SA;
int main(){
//	freopen("123.txt","r",stdin);
//	freopen("my.txt","w",stdout);
	scanf("%s",s+1),n=strlen(s+1),SA.sakura();
}
Escape Through Leaf 超哥线段树+线段树合并
68 行
CPP JSON
【Escape Through Leaf(超哥线段树+线段树合并)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 LL y(Re id,Re x) — 核心算法函数 void change(Re &p,Re L,Re R,Re id) — 核心算法函数 LL ask(Re p,Re L,Re R,Re x) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 67 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,o,cnt,k[N],A[N],B[N],pt[N],head[N];LL b[N],dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int id,lp,rp;}tr[N*18*2*2];
	inline LL y(Re id,Re x){return (LL)k[id]*x+b[id];}
	inline void change(Re &p,Re L,Re R,Re id){
		if(!p){tr[p=++O].id=id;return;}
		if(L==R){if(y(id,L)<y(tr[p].id,L))tr[p].id=id;return;}
		if(k[id]>k[tr[p].id]){
			if(y(id,mid)<y(tr[p].id,mid))change(pr,mid+1,R,tr[p].id),tr[p].id=id;
			else change(pl,L,mid,id);
		}
		else{
			if(y(id,mid)<y(tr[p].id,mid))change(pl,L,mid,tr[p].id),tr[p].id=id;
			else change(pr,mid+1,R,id);
		}
	}
	inline LL ask(Re p,Re L,Re R,Re x){
		if(!p)return 1e18;
		if(L==R)return y(tr[p].id,x);
		LL ans=y(tr[p].id,x);
		if(x<=mid)return min(ans,ask(pl,L,mid,x));
		else return min(ans,ask(pr,mid+1,R,x));
	}
	inline int merge(Re p,Re q,Re L,Re R){
		if(!p||!q)return p+q;
		if(L==R){if(y(tr[p].id,L)>y(tr[q].id,L))tr[p].id=tr[q].id;return p;}
		pl=merge(pl,tr[q].lp,L,mid);
		pr=merge(pr,tr[q].rp,mid+1,R);
		change(p,L,R,tr[q].id);
		return p;
	}
}TR;
inline void dfs(Re x,Re fa){
	Re son=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)son=1,dfs(to,x),pt[x]=TR.merge(pt[x],pt[to],-N,N);
	k[++cnt]=B[x],dp[x]=b[cnt]=son?TR.ask(pt[x],-N,N,A[x]):0;
	TR.change(pt[x],-N,N,cnt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	for(Re i=1;i<=n;++i)in(B[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0);
	for(Re i=1;i<=n;++i)printf("%lld\n",dp[i]);
}
主席树-区间第k小 mid
42 行
CPP JSON
【主席树-区间第k小】 可持久化线段树(主席树)模板,通过动态开点维护历史版本。 核心函数: void in(Re &x) — 核心算法函数 void creat(Re &p,Re q,Re L,Re R,Re w) — 核心算法函数 int ask(Re p,Re q,Re L,Re R,Re k) — 核心算法函数 核心结构体:President_Tree, QAQ 关键配置: N=2e5+3,logN=18 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,logN=18;
int n,m,x,y,z,T,b[N],A[N],pt[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct President_Tree{
    #define pl tr[p].lp
    #define pr tr[p].rp
    #define mid (L+R>>1)
    int O;
    struct QAQ{int S,lp,rp;}tr[N*(logN+1)];
    inline void creat(Re &p,Re q,Re L,Re R,Re w){
        p=++O,tr[p]=tr[q],++tr[p].S;
        if(L==R)return;
        if(w<=mid)creat(pl,tr[q].lp,L,mid,w);
        else creat(pr,tr[q].rp,mid+1,R,w);
    }
    inline int ask(Re p,Re q,Re L,Re R,Re k){
        if(L==R)return L;
        Re tmp=tr[pl].S-tr[tr[q].lp].S;
        if(tmp>=k)return ask(pl,tr[q].lp,L,mid,k);
        else return ask(pr,tr[q].rp,mid+1,R,k-tmp);
    }
}T1;
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
    sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
    for(Re i=1;i<=n;++i)T1.creat(pt[i],pt[i-1],1,m,lower_bound(b+1,b+m+1,A[i])-b);
    while(T--)in(x),in(y),in(z),printf("%d\n",b[T1.ask(pt[y],pt[x-1],1,m,z)]);
}
区修,区查(gcd) (Interval GCD) +
56 行
CPP JSON
【区修,区查(gcd) (Interval GCD)(+)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: template<typename T>inline void in(T &x) — 核心算法函数 LL abs(LL a) — 核心算法函数 LL gcd(LL a,LL b) — 最大公约数 void add(Re x,LL v) — 加法更新 void add(Re L,Re R,LL v) — 加法更新 LL ask(Re x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) 核心结构体:BIT, Segment_Tree 关键配置: N=5e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 55 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T;LL z,A[N];char op;
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL abs(LL a){return a<0?-a:a;}
inline LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
struct BIT{
    LL C[N];
    inline void add(Re x,LL v){while(x<=n)C[x]+=v,x+=x&-x;}
    inline void add(Re L,Re R,LL v){add(L,v),add(R+1,-v);}
    inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR0;
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    LL tr[N<<2];
    inline void pushup(Re p){tr[p]=gcd(tr[pl],tr[pr]);}
    inline void build(Re p,Re L,Re R){
        if(L==R){tr[p]=A[L]-A[L-1];return;}
        build(pl,L,mid),build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re x,LL v){
        if(L==R){tr[p]+=v;return;}
        if(x<=mid)change(pl,L,mid,x,v);
        else change(pr,mid+1,R,x,v);
        pushup(p);
    }
    inline LL ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return abs(tr[p]);
        if(r<=mid)return ask(pl,L,mid,l,r);
        else if(l>mid)return ask(pr,mid+1,R,l,r);
        else return gcd(ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));
    }
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]),TR0.add(i,i,A[i]);
    TR.build(1,1,n);
    while(T--){
        scanf(" %c",&op),in(x),in(y);
        if(op=='Q')printf("%lld\n",gcd(TR0.ask(x),TR.ask(1,1,n,x+1,y)));
        else{
            in(z),TR0.add(x,y,z),TR.change(1,1,n,x,z);if(y<n)TR.change(1,1,n,y+1,-z);
        }
    }
}
区修,区查(Sum) +
52 行
CPP JSON
【区修,区查(Sum)(+)】 带懒标记的线段树模板,支持区间修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p,Re L,Re R,LL v) — 核心算法函数 void pushdown(Re p,Re L,Re R) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 51 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{LL S,add;}tr[N<<2];
    inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
    inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v;}
    inline void pushdown(Re p,Re L,Re R){
        if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
    }
    inline void build(Re p,Re L,Re R){
        if(L==R){tr[p].S=A[L];return;}
        build(pl,L,mid),build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
        if(l<=L&&R<=r){updata(p,L,R,v);return;}
        pushdown(p,L,R);
        if(l<=mid)change(pl,L,mid,l,r,v);
        if(r>mid)change(pr,mid+1,R,l,r,v);
        pushup(p);
    }
    inline LL ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p].S;
        LL ans=0;pushdown(p,L,R);
        if(l<=mid)ans+=ask(pl,L,mid,l,r);
        if(r>mid)ans+=ask(pr,mid+1,R,l,r);
        return ans;
    }
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]);
    TR.build(1,1,n);
    while(T--){
        in(op),in(x),in(y);
        if(op<2)in(z),TR.change(1,1,n,x,y,z);
        else printf("%lld\n",TR.ask(1,1,n,x,y));
    }
}
区修,区查(Sum) +,×
57 行
CPP JSON
【区修,区查(Sum)(+,×)】 带懒标记的线段树模板,支持区间修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata1(Re p,LL v) — 核心算法函数 void updata2(Re p,Re L,Re R,LL v) — 核心算法函数 void pushdown(Re p,Re L,Re R) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re v,Re op) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 56 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,z,T,P,op,A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{LL S,mul,add;}tr[N<<2];
    inline void pushup(Re p){tr[p].S=(tr[pl].S+tr[pr].S)%P;}
    inline void updata1(Re p,LL v){
        tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P,tr[p].add=(LL)tr[p].add*v%P;
    }
    inline void updata2(Re p,Re L,Re R,LL v){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;}
    inline void pushdown(Re p,Re L,Re R){
        if(tr[p].mul!=1)updata1(pl,tr[p].mul),updata1(pr,tr[p].mul),tr[p].mul=1;
        if(tr[p].add)updata2(pl,L,mid,tr[p].add),updata2(pr,mid+1,R,tr[p].add),tr[p].add=0;
    }
    inline void build(Re p,Re L,Re R){
        tr[p].mul=1;
        if(L==R){tr[p].S=A[L]%P;return;}
        build(pl,L,mid),build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re v,Re op){
        if(l<=L&&R<=r){if(op<2)updata1(p,v);else updata2(p,L,R,v);return;}
        pushdown(p,L,R);
        if(l<=mid)change(pl,L,mid,l,r,v,op);
        if(r>mid)change(pr,mid+1,R,l,r,v,op);
        pushup(p);
    }
    inline LL ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p].S;
        LL ans=0;pushdown(p,L,R);
        if(l<=mid)(ans+=ask(pl,L,mid,l,r))%=P;
        if(r>mid)(ans+=ask(pr,mid+1,R,l,r))%=P;
        return ans;
    }
}TR;
int main(){
    in(n),in(T),in(P);
    for(Re i=1;i<=n;++i)in(A[i]);
    TR.build(1,1,n);
    while(T--){
        in(op),in(x),in(y);
        if(op<3)in(z),TR.change(1,1,n,x,y,z,op);
        else printf("%lld\n",TR.ask(1,1,n,x,y));
    }
}
区修,区查(Sum,min) +,/
78 行
CPP JSON
【区修,区查(Sum,min)(+,/)】 带懒标记的线段树模板,支持区间修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p,Re L,Re R,LL v) — 核心算法函数 void pushdown(Re p,Re L,Re R) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 void change_div(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 LL ask_min(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 77 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define div(a,b) floor((double)a/b)
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op,A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{LL S,add,min,max;}tr[N<<2];
    inline void pushup(Re p){
        tr[p].S=tr[pl].S+tr[pr].S;
        tr[p].min=min(tr[pl].min,tr[pr].min);
        tr[p].max=max(tr[pl].max,tr[pr].max);
    }
    inline void updata(Re p,Re L,Re R,LL v){tr[p].S+=v*(R-L+1),tr[p].add+=v,tr[p].min+=v,tr[p].max+=v;}
    inline void pushdown(Re p,Re L,Re R){
        if(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;
    }
    inline void build(Re p,Re L,Re R){
        if(L==R){tr[p].S=tr[p].min=tr[p].max=A[L];return;}
        build(pl,L,mid),build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
        if(l<=L&&R<=r){updata(p,L,R,v);return;}
        pushdown(p,L,R);
        if(l<=mid)change(pl,L,mid,l,r,v);
        if(r>mid)change(pr,mid+1,R,l,r,v);
        pushup(p);
    }
    inline void change_div(Re p,Re L,Re R,Re l,Re r,Re v){
        if(l<=L&&R<=r&&(div(tr[p].max,v)-tr[p].max==div(tr[p].min,v)-tr[p].min)){
            updata(p,L,R,div(tr[p].max,v)-tr[p].max);return;
        }
        pushdown(p,L,R);
        if(l<=mid)change_div(pl,L,mid,l,r,v);
        if(r>mid)change_div(pr,mid+1,R,l,r,v);
        pushup(p);
    }
    inline LL ask_min(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p].min;
        LL ans=1e18;pushdown(p,L,R);
        if(l<=mid)ans=min(ans,ask_min(pl,L,mid,l,r));
        if(r>mid)ans=min(ans,ask_min(pr,mid+1,R,l,r));
        return ans;
    }
    inline LL ask_S(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p].S;
        LL ans=0;pushdown(p,L,R);
        if(l<=mid)ans+=ask_S(pl,L,mid,l,r);
        if(r>mid)ans+=ask_S(pr,mid+1,R,l,r);
        return ans;
    }
}TR;
int main(){
    in(n),in(T);
    for(Re i=1;i<=n;++i)in(A[i]);
    TR.build(1,1,n);
    while(T--){
        in(op),in(x),in(y),++x,++y;
        if(op<2)in(z),TR.change(1,1,n,x,y,z);
        else if(op<3)in(z),TR.change_div(1,1,n,x,y,z);
        else if(op<4)printf("%lld\n",TR.ask_min(1,1,n,x,y));
        else printf("%lld\n",TR.ask_S(1,1,n,x,y));
    }
}
区修,区查(Sum) Sqrt
54 行
CPP JSON
【区修,区查(Sum)(Sqrt)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: template<typename T>inline void in(T &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 53 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,x,y,z,T,op;LL A[N];
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{LL S,max;}tr[N<<2];
    inline void pushup(Re p){
        tr[p].S=tr[pl].S+tr[pr].S;
        tr[p].max=max(tr[pl].max,tr[pr].max);
    }
    inline void build(Re p,Re L,Re R){
        if(L==R){tr[p].S=tr[p].max=A[L];return;}
        build(pl,L,mid),build(pr,mid+1,R);
        pushup(p);
    }
    inline void change(Re p,Re L,Re R,Re l,Re r){
        if(tr[p].max<=1)return;
        if(L==R){tr[p].max=tr[p].S=sqrt(tr[p].S);return;}
        if(l<=mid)change(pl,L,mid,l,r);
        if(r>mid)change(pr,mid+1,R,l,r);
        pushup(p);
    }
    inline LL ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p].S;
        LL ans=0;
        if(l<=mid)ans+=ask(pl,L,mid,l,r);
        if(r>mid)ans+=ask(pr,mid+1,R,l,r);
        return ans;
    }
}TR;
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(A[i]);
    TR.build(1,1,n),in(T);
    while(T--){
        in(op),in(x),in(y);if(x>y)swap(x,y);
        if(op)printf("%lld\n",TR.ask(1,1,n,x,y));
        else TR.change(1,1,n,x,y);
    }
}
单修,区查(最大子段和) +
48 行
CPP JSON
【单修,区查(最大子段和)(+)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void pushup(QAQ &A,const QAQ &L,const QAQ &R) — 上推更新节点信息 void change(Re p,Re L,Re R,Re x,Re v) — 核心算法函数 QAQ ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree, QAQ 关键配置: N=5e4+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 47 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3;
int n,x,y,T,op,A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{LL S,max,lmax,rmax;}tr[N<<2];
    inline void pushup(QAQ &A,const QAQ &L,const QAQ &R){
        A.S=L.S+R.S;
        A.lmax=max(L.lmax,L.S+R.lmax);
        A.rmax=max(R.rmax,R.S+L.rmax);
        A.max=max(max(max(L.max,R.max),max(A.lmax,A.rmax)),L.rmax+R.lmax);
    }
    inline void change(Re p,Re L,Re R,Re x,Re v){
        if(L==R){tr[p].S=tr[p].max=tr[p].lmax=tr[p].rmax=v;return;}
        if(x<=mid)change(pl,L,mid,x,v);
        else change(pr,mid+1,R,x,v);
        pushup(tr[p],tr[pl],tr[pr]);
    }
    inline QAQ ask(Re p,Re L,Re R,Re l,Re r){
        if(l<=L&&R<=r)return tr[p];
        if(r<=mid)return ask(pl,L,mid,l,r);
        else if(l>mid)return ask(pr,mid+1,R,l,r);
        else{QAQ ans;pushup(ans,ask(pl,L,mid,l,r),ask(pr,mid+1,R,l,r));return ans;}
    }
}TR;
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(A[i]),TR.change(1,1,n,i,A[i]);
    in(T);
    while(T--){
        in(op),in(x),in(y);
        if(op)printf("%lld\n",TR.ask(1,1,n,x,y).max);
        else TR.change(1,1,n,x,y);
    }
}
整体DP (Treeland Tour) 树上最长上升子序列
87 行
CPP JSON
【整体DP (Treeland Tour)(树上最长上升子序列)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void change1(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 void change2(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int ask1(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 int ask2(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=6003 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 86 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6003;
int n,m,x,y,t,o,Ans,b[N],A[N],pt[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (tr[p].lp)
	#define pr (tr[p].rp)
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int lp,rp,up,down;}tr[N*13*2];
	inline void pushup(Re p){
		tr[p].up=max(tr[pl].up,tr[pr].up);
		tr[p].down=max(tr[pl].down,tr[pr].down);
	}
	inline void change1(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].up=max(tr[p].up,v);return;}
		if(x<=mid)change1(pl,L,mid,x,v);
		else change1(pr,mid+1,R,x,v);
		pushup(p);
	}
	inline void change2(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].down=max(tr[p].down,v);return;}
		if(x<=mid)change2(pl,L,mid,x,v);
		else change2(pr,mid+1,R,x,v);
		pushup(p);
	}
	inline int ask1(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].up;
		Re ans=0;
		if(l<=mid)ans=max(ans,ask1(pl,L,mid,l,r));
		if(r>mid)ans=max(ans,ask1(pr,mid+1,R,l,r));
		return ans;
	}
	inline int ask2(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].down;
		Re ans=0;
		if(l<=mid)ans=max(ans,ask2(pl,L,mid,l,r));
		if(r>mid)ans=max(ans,ask2(pr,mid+1,R,l,r));
		return ans;
	}
	inline int merge(Re p,Re q,Re L,Re R){
		if(!p||!q)return p+q;
		if(L==R){tr[p].up=max(tr[p].up,tr[q].up),tr[p].down=max(tr[p].down,tr[q].down);return p;}
		Ans=max(Ans,max(tr[pl].up+tr[tr[q].rp].down,tr[pr].down+tr[tr[q].lp].up));
		pl=merge(pl,tr[q].lp,L,mid);
		pr=merge(pr,tr[q].rp,mid+1,R);
		pushup(p);return p;
	}
}TR;
inline void dfs(Re x,Re fa){
	Re up=0,down=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x);
			Re tmp1=TR.ask1(pt[to],1,t,1,A[x]-1),tmp2=TR.ask2(pt[to],1,t,A[x]+1,t);
			Ans=max(Ans,max(up+tmp2+1,down+tmp1+1));
			up=max(up,tmp1),down=max(down,tmp2);
			pt[x]=TR.merge(pt[x],pt[a[i].to],1,t);
		}
	TR.change1(pt[x],1,t,A[x],up+1),TR.change2(pt[x],1,t,A[x],down+1);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
	sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b;
	for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+t+1,A[i])-b;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0),printf("%d\n",Ans);
}
树套树-单修权值,区间权值和+垃圾回收 Intersection of Permutations
64 行
CPP JSON
【树套树-单修权值,区间权值和+垃圾回收(Intersection of Permutations)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(int &x) — 核心算法函数 int New(无参数) — 核心算法函数 void del(Re &p) — 核心算法函数 void change(Re &p,Re L,Re R,Re w,Re v) — 核心算法函数 int ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 int ask(Re L,Re R,Re l,Re r) — 核心算法函数 void add(Re x,Re w,Re v) — 加法更新 核心结构体:Segment_Tree, QAQ 关键配置: N=2e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 63 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=2e5+3;char opt[N];
int x,y,z,w,n,T,op,A[N],rk[N];
inline void in(int &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid ((L+R)>>1)
	int O;queue<int>Q;
	struct QAQ{int S,lp,rp;}tr[N*200];
	inline int New(){// 新建节点
		if(Q.empty())return ++O;
		Re tmp=Q.front();Q.pop();
		return tmp;
	}
	inline void del(Re &p){pl=pr=0,Q.push(p),p=0;}// 删除节点(注意取地址,初始化为1)
	inline void change(Re &p,Re L,Re R,Re w,Re v){
	    if(!p)p=New();tr[p].S+=v;
	    if(L==R){if(!tr[p].S)del(p);return;}
	    if(w<=mid)change(pl,L,mid,w,v);
	    else change(pr,mid+1,R,w,v);
	    if(!tr[p].S)del(p);
	}
	inline int ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		Re ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
}TR;
inline int ask(Re L,Re R,Re l,Re r){
    Re ans=0;
    for(Re i=R;i;i-=i&-i)ans+=TR.ask(pt[i],1,n,l,r);
    for(Re i=L-1;i;i-=i&-i)ans-=TR.ask(pt[i],1,n,l,r);
    return ans;
}
inline void add(Re x,Re w,Re v){
    for(Re i=x;i<=n;i+=i&-i)TR.change(pt[i],1,n,w,v);
}
int main(){
//	freopen("123.txt","r",stdin);
    in(n),in(T);
	for(Re i=1;i<=n;++i)in(x),rk[x]=i;
	for(Re i=1;i<=n;++i)in(A[i]),A[i]=rk[A[i]],add(i,A[i],1);
    while(T--){
    	in(op),in(x),in(y);
    	if(op>1)add(x,A[x],-1),add(y,A[y],-1),swap(A[x],A[y]),add(x,A[x],1),add(y,A[y],1);
    	else in(z),in(w),printf("%d\n",ask(z,w,x,y));
	}
}
树套树-单修权值,区间第k小 pl
74 行
CPP JSON
【树套树-单修权值,区间第k小】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int ask(Re p,Re L,Re R,Re K) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask(Re L,Re R,Re k) — 核心算法函数 核心结构体:QWQ, President_Tree, QAQ, BIT 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 73 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,T,b[N<<1],A[N];char op[N];
struct QWQ{int x,y,k;}Q[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int t1,t2,pt[N],ptl[20],ptr[20];
struct President_Tree{
    #define pl (tr[p].lp)
    #define pr (tr[p].rp)
    #define mid ((L+R)>>1)
    int O;
    struct QAQ{int S,lp,rp;}tr[(N<<1)*200];
    inline void change(Re &p,Re L,Re R,Re x,Re v){
        if(!p)p=++O;tr[p].S+=v;
        if(L==R)return;
        if(x<=mid)change(pl,L,mid,x,v);
        else change(pr,mid+1,R,x,v);
    }
    inline int ask(Re p,Re L,Re R,Re K){
        if(L==R)return L;
        Re tmp=0;
        for(Re i=1;i<=t1;++i)tmp-=tr[tr[ptl[i]].lp].S;
        for(Re i=1;i<=t2;++i)tmp+=tr[tr[ptr[i]].lp].S;
        if(K<=tmp){
            for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].lp;
            for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].lp;
            return ask(pl,L,mid,K);
        }
        else{
            for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].rp;
            for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].rp;
            return ask(pr,mid+1,R,K-tmp);
        }
    }
}SG;
struct BIT{
    inline void add(Re x,Re v){
        for(Re i=x;i<=n;i+=i&-i)SG.change(pt[i],1,m,A[x],v);
    }
    inline int ask(Re L,Re R,Re k){
        t1=t2=0;
        for(Re i=L-1;i;i-=i&-i)ptl[++t1]=pt[i];
        for(Re i=R;i;i-=i&-i)ptr[++t2]=pt[i];
        return SG.ask(1,1,m,k);
    }
}TR;
int main(){
    in(n),in(T),m=n;
    for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
    for(Re i=1;i<=T;++i){
        scanf(" %c",&op[i]),in(Q[i].x),in(Q[i].y);
        if(op[i]=='Q')in(Q[i].k);
        else b[++m]=Q[i].y;
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
    for(Re i=1;i<=T;++i)if(op[i]=='C')Q[i].y=lower_bound(b+1,b+m+1,Q[i].y)-b;
    for(Re i=1;i<=n;++i)TR.add(i,1);
    for(Re i=1;i<=T;++i){
        if(op[i]=='Q')printf("%d\n",b[TR.ask(Q[i].x,Q[i].y,Q[i].k)]);
        else TR.add(Q[i].x,-1),A[Q[i].x]=Q[i].y,TR.add(Q[i].x,1);
    }
}
线段树分治 (LCT维护MST) (城市建设) 时间分治
135 行
CPP JSON
【线段树分治 (LCT维护MST) (城市建设)(时间分治)】 带懒标记的线段树模板,支持区间修改与区间查询。 核心函数: void in(int &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:QWQ, Link_Cut_Tree, QAQ, QAQ, Segment_Tree 关键配置: N=2e4+3,M=5e4+3 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 134 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e4+3,M=5e4+3;
int n,m,x,y,z,T,op,X[N+M],Y[N+M],last[M];LL v[N+M],Ans[M];
inline void in(int &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct QWQ{int id,op;QWQ(Re ID=0,Re OP=0){id=ID,op=OP;}};
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int size,Q[N+M];QWQ QQ[M*32];LL MST;
	struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
	inline void pushup(Re p){
		tr[p].mx=p;
		if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
		if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p); 
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re x){access(x),splay(x),updata(x);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
	inline void cut(Re x,Re y){makeroot(x),access(y),splay(y),tr[x].fa=tr[y].ps[0]=0,pushup(y);}
	inline void cut_(Re id){
		makeroot(Y[id]),access(X[id]),splay(X[id]),tr[X[id]].ps[0]=tr[Y[id]].fa=tr[id].ps[0]=tr[id].fa=0,pushup(X[id]);
	}
	inline void link_(Re id){
		makeroot(X[id]),makeroot(Y[id]),tr[X[id]].fa=tr[Y[id]].fa=id;
	}
	inline void MST_link(Re id){
		Re x=X[id],y=Y[id];makeroot(x);
		if(findroot(y)!=x)link(x,id),link(id,y),QQ[++size]=QWQ(id,0),MST+=v[id];
		else{
			Re mx=tr[y].mx;
			if(v[id]<v[mx]){
//				cut(X[mx],mx),cut(mx,Y[mx]),QQ[++size]=QWQ(mx,1);
				cut_(mx),QQ[++size]=QWQ(mx,1);
				link(x,id),link(id,y),QQ[++size]=QWQ(id,0);
//				link_(id),QQ[++size]=QWQ(id,0);
				MST+=v[id]-v[mx];
			}
		}
	}
	inline void back(Re to){
		while(size>to){
			QWQ a=QQ[size--];Re id=a.id;
			if(a.op)link(id,Y[id]),link(X[id],id),MST+=v[id];
//			else cut(id,Y[id]),cut(X[id],id),MST-=v[id];
//			if(a.op)link_(id),MST+=v[id];
			else cut_(id),MST-=v[id];
		}
	}
	#undef pl
	#undef pr
}LCT;
int o,head[M<<2];
struct QAQ{int id,next;LL v;}a[M*32];
inline void add(Re x,Re id,LL v){a[++o].id=id,a[o].v=v,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	inline void change(Re p,Re L,Re R,Re l,Re r,Re id,LL v){
		if(l>r)return;
		if(l<=L&&R<=r){add(p,id,v);return;}
		if(l<=mid)change(pl,L,mid,l,r,id,v);
		if(r>mid)change(pr,mid+1,R,l,r,id,v);
	}
	inline void dfs(Re p,Re L,Re R){
		Re tmp=LCT.size;
		for(Re i=head[p];i;i=a[i].next)v[a[i].id]=a[i].v,LCT.MST_link(a[i].id);
		if(L==R)Ans[L]=LCT.MST;
		else dfs(pl,L,mid),dfs(pr,mid+1,R);
		LCT.back(tmp);
	}
}T1;
int main(){
// 	freopen("123.txt","r",stdin);
// 	freopen("my.txt","w",stdout);
	in(n),in(m),in(T);
	for(Re i=1;i<=m;++i)in(X[i+n]),in(Y[i+n]),in(x),v[i+n]=x,last[i]=1;
	for(Re i=1;i<=T;++i){
		in(x),in(y);
		T1.change(1,1,T,last[x],i-1,x+n,v[x+n]);
		last[x]=i,v[x+n]=y;
	}
	for(Re i=1;i<=m;++i)T1.change(1,1,T,last[i],T,i+n,v[i+n]);
	T1.dfs(1,1,T);
	for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
线段树分治 (冰茶姬 判断二分图) 时间分治
71 行
CPP JSON
【线段树分治 (冰茶姬 判断二分图)(时间分治)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void merge(Re x,Re y) — 合并操作 void back(Re to) — 获取队尾元素 void add(Re x,Re y1,Re y2) — 加法更新 void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y) — 核心算法函数 void dfs(Re p,Re L,Re R) — 深度优先搜索遍历 核心结构体:Union, BK, QAQ, Segment_Tree 关键配置: N=1e5+3,M=2e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 70 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=1e5+3,M=2e5+3;
int x,y,l,r,n,m,T,Ans[N];char ch[20];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
	struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
	int fa[N<<1],size[N<<1];stack<BK>Q;
	inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
	inline void merge(Re x,Re y){// 启发式合并
		x=find(x),y=find(y);
		if(x==y)return;
		if(size[x]>size[y])swap(x,y);
		Q.push(BK(x,size[x],y,size[y]));
		fa[x]=y,size[y]+=size[x];
	}
	inline void back(Re to){// 撤销操作
		while(int(Q.size())>to){
			BK a=Q.top();Q.pop();
			fa[a.x]=a.x,size[a.x]=a.sizex;
			fa[a.y]=a.y,size[a.y]=a.sizey;
		}
	}
}TF;
int o,head[N<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
		if(l>r)return;
		if(l<=L&&R<=r){add(p,x,y);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,y);
		if(r>mid)change(pr,mid+1,R,l,r,x,y);
	}
	inline void dfs(Re p,Re L,Re R){
		Re tmp=TF.Q.size();
		for(Re i=head[p];i;i=a[i].next){
			if(TF.find(a[i].x)==TF.find(a[i].y)){
				for(Re j=L;j<=R;++j)Ans[j]=1;
				TF.back(tmp);return;
			}
			TF.merge(a[i].x,a[i].y+n),TF.merge(a[i].x+n,a[i].y);
		}
		if(L<R)dfs(pl,L,mid),dfs(pr,mid+1,R);
		TF.back(tmp);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(T);
	for(Re i=1;i<=(n<<1);++i)TF.fa[i]=i,TF.size[i]=1;
	for(Re i=1;i<=m;++i)in(x),in(y),in(l),in(r),T1.change(1,1,T,l+1,r+1-1,x,y);
	T1.dfs(1,1,T);
	for(Re i=1;i<=T;++i)puts(Ans[i]?"No":"Yes");
}
线段树分治 (冰茶姬 查询图的连通性) (洞穴勘测) 时间分治
73 行
CPP JSON
【线段树分治 (冰茶姬 查询图的连通性) (洞穴勘测)(时间分治)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void merge(Re x,Re y) — 合并操作 void back(Re to) — 获取队尾元素 void add(Re x,Re y1,Re y2) — 加法更新 void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y) — 核心算法函数 void dfs(Re p,Re L,Re R) — 深度优先搜索遍历 核心结构体:Query, Union, BK, QAQ, Segment_Tree 关键配置: N=1e4+3,M=2e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1e4+3,M=2e5+3;
int x,y,n,T,Ans[M];char ch[20];
map<pair<int,int>,int>last;
struct Query{int x,y,op;}Q[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
	struct BK{int x,y,sizex,sizey;BK(Re X=0,Re S1=0,Re Y=0,Re S2=0){x=X,y=Y,sizex=S1,sizey=S2;}};
	int fa[N],size[N];stack<BK>Q;
	inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
	inline void merge(Re x,Re y){// 启发式合并
		x=find(x),y=find(y);
		if(size[x]>size[y])swap(x,y);
		Q.push(BK(x,size[x],y,size[y]));
		fa[x]=y,size[y]+=size[x];
	}
	inline void back(Re to){// 撤销操作
		while(Q.size()>to){
			BK a=Q.top();Q.pop();
			fa[a.x]=a.x,size[a.x]=a.sizex;
			fa[a.y]=a.y,size[a.y]=a.sizey;
		}
	}
}TF;
int o,head[M<<2];
struct QAQ{int x,y,next;}a[M*20];
inline void add(Re x,Re y1,Re y2){a[++o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid (L+R>>1)
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y){
		if(l<=L&&R<=r){add(p,x,y);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,y);
		if(r>mid)change(pr,mid+1,R,l,r,x,y);
	}
	inline void dfs(Re p,Re L,Re R){
		Re tmp=TF.Q.size();
		for(Re i=head[p];i;i=a[i].next)TF.merge(a[i].x,a[i].y);
		if(L==R){if(Q[L].op)Ans[L]=(TF.find(Q[L].x)==TF.find(Q[L].y));}
		else dfs(pl,L,mid),dfs(pr,mid+1,R);
		TF.back(tmp);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
	for(Re i=1;i<=T;++i){
		scanf("%s",ch),in(x),in(y);if(x>y)swap(x,y);
		if(ch[0]=='Q')Q[i].op=1,Q[i].x=x,Q[i].y=y;
		else if(ch[0]=='C')last[mp(x,y)]=i;
		else T1.change(1,1,T,last[mp(x,y)],i,x,y),last.erase(mp(x,y));
	}
	for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
		T1.change(1,1,T,it->second,T,it->first.first,it->first.second);
	T1.dfs(1,1,T);
	for(Re i=1;i<=T;++i)if(Q[i].op)puts(Ans[i]?"Yes":"No");
}
线段树分治 (线性基) (八纵八横) 时间分治
91 行
CPP JSON
【线段树分治 (线性基) (八纵八横)(时间分治)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y,Int z) — 加法更新 int find(Re x) — 查找(并查集寻根/二分查找) int getlen(Int &x) — 获取值 void print(Int &x) — 核心算法函数 void in(Int &x) — 核心算法函数 void in(Re &x) — 核心算法函数 void insert(Int x) — 插入元素 Int ask(无参数) — 核心算法函数 核心结构体:QAQ, Line_JI, Segment_Tree, QAQ 关键配置: N=550+5,M=1000+5 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 90 行 CPP
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<stack>
#define LL long long
#define Re register int
#define Int bitset<M>
using namespace std;
const int N=550+5,M=1000+5;
int n,m,x,y,o,O,T,logN,X[N],Y[N],fa[N],last[N],head[N];Int z,Z[N],dis[N],Ans[M];char op[20];
struct QAQ{int to,next;Int w;}a[N<<1];
inline void add(Re x,Re y,Int z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline int getlen(Int &x){Re n=1000;while(n>=1&&!x[n])--n;return n;}
inline void print(Int &x){for(Re i=getlen(x);i>=0;--i)putchar(x[i]+'0');puts("");}
inline void in(Int &x){cin>>x,logN=max(logN,getlen(x));}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Line_JI{
	Int p[M];bool pp[M];stack<int>Q;
	inline void insert(Int x){
		for(Re i=logN;i>=0;--i)
			if(x[i]){
				if(!pp[i]){Q.push(i),p[i]=x,pp[i]=1;break;}
				x^=p[i];
			}
	}
	inline Int ask(){
		Int ans;ans.reset();
		for(Re i=logN;i>=0;--i)if(pp[i]&&(!ans[i]))ans^=p[i];
		return ans;
	}
	inline void back(Re to){
		while(Q.size()>to)x=Q.top(),Q.pop(),p[x].reset(),pp[x]=0;
	}
}JI;
struct Segment_Tree{
	int o,head[M<<2];
	struct QAQ{int x,y,next;Int w;}a[(N+M)*10];
	inline void add(Re t,Re x,Re y,Int &z){a[++o].x=x,a[o].y=y,a[o].w=z,a[o].next=head[t],head[t]=o;}
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Int &z){
		if(l<=L&&R<=r){add(p,x,y,z);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,y,z);
		if(r>mid)change(pr,mid+1,R,l,r,x,y,z);
	}
	inline void dfs(Re p,Re L,Re R){
		Re tmp=JI.Q.size();
		for(Re i=head[p];i;i=a[i].next)JI.insert(dis[a[i].x]^dis[a[i].y]^a[i].w);
		if(L==R)Ans[L]=JI.ask();// 这里还没做back撤销操作,不能return!!!
		else dfs(pl,L,mid),dfs(pr,mid+1,R);
		JI.back(tmp);
	}
}TR;
inline void dfs(Re x,Re fa,Re w){
	dis[x]=dis[fa]^a[w].w;
	for(Re i=head[x];i;i=a[i].next)
		if(a[i].to!=fa)dfs(a[i].to,x,i);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(T),++T;
	for(Re i=1;i<=n;++i)fa[i]=i;
	while(m--){
		in(x),in(y),in(z);
		if(find(x)!=find(y))add(x,y,z),add(y,x,z),fa[find(x)]=find(y);
		else TR.change(1,1,T,1,T,x,y,z);
	}
	for(Re i=2;i<=T;++i){
		scanf("%s",op);
		if(op[0]=='A')last[++O]=i,in(X[O]),in(Y[O]),in(Z[O]);
		else if(op[1]=='h'){
			in(x),in(z);
			TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]);
			last[x]=i,Z[x]=z;
		}
		else in(x),TR.change(1,1,T,last[x],i-1,X[x],Y[x],Z[x]),last[x]=0;
	}
	for(Re i=1;i<=O;++i)if(last[i])TR.change(1,1,T,last[i],T,X[i],Y[i],Z[i]);
	dfs(1,0,0),TR.dfs(1,1,T);
	for(Re i=1;i<=T;++i)print(Ans[i]);
}
线段树分裂-分裂区间前后k个 区间排序 P2824
106 行
CPP JSON
【线段树分裂-分裂区间前后k个(区间排序 P2824)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void change(Re &p,Re L,Re R,Re x) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 void split1(Re &p,Re q,Re L,Re R,Re k) — 分裂操作 void split2(Re &p,Re q,Re L,Re R,Re k) — 分裂操作 void dfs(Re p,Re L,Re R) — 深度优先搜索遍历 IT split(Re w) — 分裂操作 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 105 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+3;
int n,m,l,r,T,op,A[N],tmp[N],cnt[N],Ans[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct QAQ{
	int l,r;mutable int pt,op; 
	QAQ(Re L=0,Re R=0,Re OP=0,Re PT=0){l=L,r=R,op=OP,pt=PT;};
	inline bool operator<(const QAQ &O)const{return l<O.l;}
};
set<QAQ>s;
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int S,lp,rp;}tr[N*60];
	inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
	inline void change(Re &p,Re L,Re R,Re x){
		p=++O;
		if(L==R){tr[p].S=1;return;}
		if(x<=mid)change(pl,L,mid,x);
		else change(pr,mid+1,R,x);
		pushup(p);
	}
	inline int merge(Re p,Re q,Re L,Re R){
		if(!p||!q)return p+q;
		if(L==R){tr[p].S+=tr[q].S;return p;}
		pl=merge(pl,tr[q].lp,L,mid);
		pr=merge(pr,tr[q].rp,mid+1,R);
		pushup(p);return p;
	}
	inline void split1(Re &p,Re q,Re L,Re R,Re k){// 取q中的前k个,分到新节点p
		tr[p=++O].S=tr[q].S-k,tr[q].S=k;
		if(L==R)return;
		Re tmp=tr[tr[q].lp].S;
		if(k>tmp)split1(pr,tr[q].rp,mid+1,R,k-tmp);// q左子树全部分给p,只剩右子树
		else pr=tr[q].rp,tr[q].rp=0;// 右子树全部分给p
		if(k<tmp)split1(pl,tr[q].lp,L,mid,k);// q的右子树全部分给p,只剩左子树
	}
	inline void split2(Re &p,Re q,Re L,Re R,Re k){// 取q中的后k个,分到新节点p
		tr[p=++O].S=tr[q].S-k,tr[q].S=k;
		if(L==R)return;
		Re tmp=tr[tr[q].rp].S;
		if(k>tmp)split2(pl,tr[q].lp,L,mid,k-tmp);// q的右子树全部分给p,只剩左子树
		else pl=tr[q].lp,tr[q].lp=0;// 左子树全部分给p
		if(k<tmp)split2(pr,tr[q].rp,mid+1,R,k);// q左子树全部分给p,只剩右子树
	}
	inline void dfs(Re p,Re L,Re R){
		if(!p)return;
		if(L==R){cnt[tmp[++tmp[0]]=L]=tr[p].S;return;}
		dfs(pl,L,mid),dfs(pr,mid+1,R);
	}
}T1;
inline IT split(Re w){
	IT it=s.lower_bound(QAQ(w));
	if(it!=s.end()&&it->l==w)return it;
	--it;
	Re L=it->l,R=it->r,op=it->op,pt=it->pt,ptt=0;
	s.erase(it);
	if(op)T1.split1(ptt,pt,1,m,w-1-L+1);
	else T1.split2(ptt,pt,1,m,w-1-L+1);
	s.insert(QAQ(L,w-1,op,pt));
	return s.insert(QAQ(w,R,op,ptt)).first;
}
inline void assign(Re l,Re r,Re op){
	if(l==r)return;
	IT itr=split(r+1),itl=split(l),it=itl;
	Re pt=0;
	while(it!=itr)pt=T1.merge(pt,it->pt,1,m),it->pt=0,++it;
	s.erase(itl,itr),s.insert(QAQ(l,r,op,pt));
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n;
	for(Re i=1;i<=n;++i)in(A[i]);
	s.insert(QAQ(n+1,n+1));
	for(Re i=1;i<=n;++i){
		QAQ tmp(i,i,0,0);T1.change(tmp.pt,1,m,A[i]),s.insert(tmp);
	}
	while(T--)in(op),in(l),in(r),op^=1,assign(l,r,op);
	IT itl=s.lower_bound(QAQ(1)),itr=s.lower_bound(QAQ(n+1));
	while(itl!=itr){
		tmp[0]=0,T1.dfs(itl->pt,1,m);
		if(itl->op)for(Re i=1;i<=tmp[0];++i)
			for(Re j=1;j<=cnt[tmp[i]];++j)
				Ans[++Ans[0]]=tmp[i];
		else for(Re i=tmp[0];i>=1;--i)
			for(Re j=1;j<=cnt[tmp[i]];++j)
				Ans[++Ans[0]]=tmp[i];
		++itl;
	}
	in(op),printf("%d\n",Ans[op]);
}
线段树分裂-分裂指定区间 mid
80 行
CPP JSON
【线段树分裂-分裂指定区间】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void build(Re &p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 int ask(Re p,Re L,Re R,LL k) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 void split(Re &p,Re &q,Re L,Re R,Re l,Re r) — 分裂操作 核心结构体:Segment_Tree, QAQ 关键配置: N=2e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 79 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3;
int n,m,x,y,p,T,op,A[N],pt[N];LL K;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int lp,rp;LL S;}tr[N*20];
	inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
	inline void build(Re &p,Re L,Re R){
		p=++O;
		if(L==R){tr[p].S=A[L];return;}
		build(pl,L,mid),build(pr,mid+1,R);
		pushup(p);
	}
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].S+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		pushup(p);
	}
	inline LL ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		LL ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
	inline int ask(Re p,Re L,Re R,LL k){
		if(!p||k>tr[p].S)return -1;
		if(L==R)return L;
		LL tmp=tr[pl].S;
		if(tmp>=k)return ask(pl,L,mid,k);
		else return ask(pr,mid+1,R,k-tmp);
	}
	inline int merge(Re p,Re q,Re L,Re R){
		if(!p||!q)return p+q;
		if(L==R){tr[p].S+=tr[q].S;return p;}
		pl=merge(pl,tr[q].lp,L,mid);
		pr=merge(pr,tr[q].rp,mid+1,R);
		pushup(p);return p;
	}
	inline void split(Re &p,Re &q,Re L,Re R,Re l,Re r){
		if(!q)return;
		if(l<=L&&R<=r){p=q,q=0;return;}
		p=++O;
		if(l<=mid)split(pl,tr[q].lp,L,mid,l,r);
		if(r>mid)split(pr,tr[q].rp,mid+1,R,l,r);
		pushup(p),pushup(q);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(m),in(T);
	for(Re i=1;i<=m;++i)in(A[i]);
	T1.build(pt[n=1],1,m);
	while(T--){
		in(op),in(p);
		if(op<1)in(x),in(y),T1.split(pt[++n],pt[p],1,m,x,y);
		else if(op<2)in(x),pt[p]=T1.merge(pt[p],pt[x],1,m),pt[x]=0;
		else if(op<3)in(x),in(y),T1.change(pt[p],1,m,y,x);
		else if(op<4)in(x),in(y),printf("%lld\n",T1.ask(pt[p],1,m,x,y));
		else scanf("%lld",&K),printf("%d\n",T1.ask(pt[p],1,m,K));
	}
}
线段树合并 晋升者计数
61 行
CPP JSON
【线段树合并(晋升者计数)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void change(Re &p,Re L,Re R,Re x) — 核心算法函数 int merge(Re p,Re q,Re L,Re R) — 合并操作 int ask(Re &p,Re L,Re R,Re l,Re r) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3,logN=17 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 60 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,o,T,op,b[N],A[N],Ans[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int pt[N];
struct Segment_Tree{
    #define pl (tr[p].lp)
    #define pr (tr[p].rp)
    #define mid ((L+R)>>1)
    int O;
    struct QAQ{int lp,rp,S;}tr[N*(logN+1)];
    inline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}
    inline void change(Re &p,Re L,Re R,Re x){
        p=++O,++tr[p].S;
        if(L==R)return;
        if(x<=mid)change(pl,L,mid,x);
        else change(pr,mid+1,R,x);
    }
    inline int merge(Re p,Re q,Re L,Re R){
        if(!p||!q)return p+q;
        if(L==R){tr[p].S+=tr[q].S;return p;}
        pl=merge(pl,tr[q].lp,L,mid);
        pr=merge(pr,tr[q].rp,mid+1,R);
        pushup(p);return p;
    }
    inline int ask(Re &p,Re L,Re R,Re l,Re r){
        if(!p)return 0;
        if(l<=L&&R<=r)return tr[p].S;
        Re ans=0;
        if(l<=mid)ans+=ask(pl,L,mid,l,r);
        if(r>mid)ans+=ask(pr,mid+1,R,l,r);
        return ans;
    }
}TR;
inline void dfs(Re x,Re fa){
    TR.change(pt[x],1,m,A[x]);
    for(Re i=head[x],to;i;i=a[i].next)
        dfs(to=a[i].to,x),pt[x]=TR.merge(pt[x],pt[to],1,m);
    if(A[x]<m)Ans[x]=TR.ask(pt[x],1,m,A[x]+1,m);
}
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
    sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
    for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
    for(Re i=2;i<=n;++i)in(x),add(x,i);
    dfs(1,0);
    for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
超哥线段树 Blue Mary开公司
51 行
CPP JSON
【超哥线段树(Blue Mary开公司)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 LD y(Re id,Re x) — 核心算法函数 void change(Re p,Re L,Re R,Re id) — 核心算法函数 LD ask(Re p,Re L,Re R,Re x) — 核心算法函数 核心结构体:Segment_Tree 关键配置: N=1e5+3,M=5e4 复杂度:建树 O(N),单次操作 O(log N) 说明:if(L==R){if(y(id,L)>y(tr[p],L))tr[p]=id;return;};freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 50 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=5e4;
int n,x,T;LD b[N],k[N];char s[20];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LD y(Re id,Re x){return k[id]*x+b[id];}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	int tr[N<<2];
	inline void change(Re p,Re L,Re R,Re id){
		if(y(id,L)>y(tr[p],L)&&y(id,R)>y(tr[p],R)){tr[p]=id;return;}
		if(y(id,L)<=y(tr[p],L)&&y(id,R)<=y(tr[p],R))return;
//		if(L==R){if(y(id,L)>y(tr[p],L))tr[p]=id;return;}
		if(k[tr[p]]<k[id]){
			if(y(id,mid+1)>y(tr[p],mid+1))change(pl,L,mid,tr[p]),tr[p]=id;
			else change(pr,mid+1,R,id);
		}
		else{
			if(y(id,mid)>y(tr[p],mid))change(pr,mid+1,R,tr[p]),tr[p]=id;
			else change(pl,L,mid,id);
		}
	}
	inline LD ask(Re p,Re L,Re R,Re x){
		if(L==R)return y(tr[p],x);
		LD ans=y(tr[p],x);
		if(x<=mid)return max(ans,ask(pl,L,mid,x));
		else return max(ans,ask(pr,mid+1,R,x));
	}
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		scanf("%s",s);
        if(s[0]=='P')++n,scanf("%lf%lf",&b[n],&k[n]),TR.change(1,1,M,n);
        else in(x),printf("%d\n",(int)(TR.ask(1,1,M,x-1)/100));
	}
}
二逼平衡树 树套树(有注释
101 行
CPP JSON
【二逼平衡树(树套树(有注释)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re L,Re R,Re k) — 核心算法函数 int ask_kth_pre(Re L,Re R,Re k) — 预处理函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 void add_pre(Re x,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 int ask_level_pre(Re L,Re R,Re w) — 预处理函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ, O_O, T_T 关键配置: N=1e5+3,inf=2147483647 复杂度:建树 O(N),单次操作 O(log N) 说明:printf("%lf\n",(sizeof(tree))/1024.0/1024.0);;�������λ����ԭ����������һ�����������ֺ��ٰ�������һ�����ʹﵽ���滻��Ŀ�� 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 100 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20]; 
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
    if(L==R)return b[R];
    Re tmp=0;
    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
    if(tmp>=k){
    	F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
    	return ask_kth(L,mid,k);
    }
    else{
    	F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
    	return ask_kth(mid+1,R,k-tmp);
    }
}
inline int ask_kth_pre(Re L,Re R,Re k){
    tl=tr=0;
    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
    return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
    Re w=lo(a[x]);
    for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(L==R)return tree[p].g; 
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
	Re ans=0;
    for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
    for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
    return ans;
}
int main(){
//	printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
//	printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
	in(n),in(T),m=n;
    F(i,1,n)in(a[i]),b[i]=a[i];
    F(i,1,T){
    	in(opt[i]);
    	if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
    	else{
    		in(Q[i].l),in(Q[i].r),in(Q[i].k);
    		if(opt[i]!=2)b[++m]=Q[i].k;
		}
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    F(i,1,n)add_pre(i,1);
    F(i,1,T){
    	if(opt[i]==1)
    		Q[i].k=lo(Q[i].k),
			printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);

    	if(opt[i]==2)
    		printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));

		if(opt[i]==3)
			add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);

		if(opt[i]==4){
		}

		if(opt[i]==5){
		}
    }
}
二逼平衡树 (无注释) 树套树
96 行
CPP JSON
【二逼平衡树 (无注释)(树套树)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re L,Re R,Re k) — 核心算法函数 int ask_kth_pre(Re L,Re R,Re k) — 预处理函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 void add_pre(Re x,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 int ask_level_pre(Re L,Re R,Re w) — 预处理函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ, O_O, T_T 关键配置: N=1e5+3,inf=2147483647 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 95 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20]; 
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
    if(L==R)return b[R];
    Re tmp=0;
    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
    if(tmp>=k){
    	F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
    	return ask_kth(L,mid,k);
    }
    else{
    	F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
    	return ask_kth(mid+1,R,k-tmp);
    }
}
inline int ask_kth_pre(Re L,Re R,Re k){
    tl=tr=0;
    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
    return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
    Re w=lo(a[x]); 
    for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(L==R)return tree[p].g; 
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
	Re ans=0;
    for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
    for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
    return ans;
}
int main(){
	in(n),in(T),m=n;
    F(i,1,n)in(a[i]),b[i]=a[i];
    F(i,1,T){
    	in(opt[i]);
    	if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
    	else{
    		in(Q[i].l),in(Q[i].r),in(Q[i].k);
    		if(opt[i]!=2)b[++m]=Q[i].k;
		}
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,n)add_pre(i,1);
    F(i,1,T){
    	if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
    	if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
		if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
		if(opt[i]==4){
			Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
			if(!level)printf("%d\n",-inf);
			else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
		}
		if(opt[i]==5){
			Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
			if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
			else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
		}
    }
}
整体DP Minimax
101 行
CPP JSON
【整体DP(Minimax)】 带懒标记的线段树模板,支持区间修改与区间查询。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void pushup(Re p) — 上推更新节点信息 void updata(Re p,Re v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int merge(Re p,Re q,Re pv,Re qv,Re v) — 合并操作 核心结构体:Segment_Tree, QAQ 关键配置: N=3e5+3,P=998244353 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 100 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+3,P=998244353;
int n,m,x,ans,inv1e4,f[N],b[N],p[N],A[N],fa[N],ch[N][3];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int pt[N];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int S,lp,rp,mul;}tr[N*19];
	inline void pushup(Re p){
		tr[p].S=(tr[pl].S+tr[pr].S)%P;
	}
	inline void updata(Re p,Re v){
		tr[p].S=(LL)tr[p].S*v%P,tr[p].mul=(LL)tr[p].mul*v%P;
	}
	inline void pushdown(Re p){
		if(tr[p].mul!=1)updata(pl,tr[p].mul),updata(pr,tr[p].mul),tr[p].mul=1;
	}
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;tr[p].mul=1;
		if(L==R){tr[p].S=v;return;}
		pushdown(p);
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		pushup(p);
	}
	inline int merge(Re p,Re q,Re pv,Re qv,Re v){
//		printf("pv=%d, qv=%d, v=%d\n",pv,qv,v);
		if(!p&&!q)return 0;
		if(!p){updata(q,qv);return q;}
		if(!q){updata(p,pv);return p;}
		pushdown(p),pushdown(q);
		Re plS=tr[pl].S,prS=tr[pr].S,qlS=tr[tr[q].lp].S,qrS=tr[tr[q].rp].S;
//		printf("p:%d,%d q:%d,%d\n",tr[pl].S,tr[pr].S,tr[tr[q].lp].S,tr[tr[q].rp].S);
		pl=merge(pl,tr[q].lp,(pv+(1-v+P)%P*1ll*qrS%P)%P,(qv+(1-v+P)%P*1ll*prS%P)%P,v);
		pr=merge(pr,tr[q].rp,(pv+(LL)v*qlS%P)%P,(qv+(LL)v*plS%P)%P,v);
		pushup(p);
		return p;
	}
	inline void dfs_(Re p,Re L,Re R){
		if(!p)return;
		if(L==R){f[L]=tr[p].S;return;}
		pushdown(p),dfs_(pl,L,mid),dfs_(pr,mid+1,R);
	}
	inline int ask(Re p,Re L,Re R,Re x){
		if(!p)return 0;
		if(L==R)return tr[p].S;
		pushdown(p);
		if(x<=mid)return ask(pl,L,mid,x);
		else return ask(pr,mid+1,R,x);
	}
}T1;
inline void dfs(Re x){
	if(!ch[x][0])T1.change(pt[x],1,m,A[x],1);
	else{
//		printf("x=%d:\n",x);
//		for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
		dfs(ch[x][1]);
		if(ch[x][0]<2)pt[x]=pt[ch[x][1]];
		else dfs(ch[x][2]),pt[x]=T1.merge(pt[ch[x][1]],pt[ch[x][2]],0,0,p[x]);
//		printf("x=%d:\n",x);
//		for(Re i=1;i<=m;++i)printf("%d ",T1.ask(pt[x],1,m,i));puts("");
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),inv1e4=inv(10000);
	for(Re i=1;i<=n;++i)in(fa[i]),ch[fa[i]][++ch[fa[i]][0]]=i;
	for(Re i=1;i<=n;++i)
		if(ch[i][0])in(p[i]),p[i]=(LL)p[i]*inv1e4%P;
		else in(x),b[++m]=A[i]=x;
	sort(b+1,b+m+1);
	for(Re i=1;i<=n;++i)if(!ch[i][0])A[i]=lower_bound(b+1,b+m+1,A[i])-b;
//	for(Re i=1;i<=n;++i)if(!ch[i][0])printf("%d: %d\n",i,A[i]);
	dfs(1),T1.dfs_(1,1,m);
//	for(Re i=1;i<=m;++i)printf("%d ",f[i]);puts("");
	for(Re i=1;i<=m;++i)(ans+=(LL)i*b[i]%P*f[i]%P*f[i]%P)%=P;
	printf("%d\n",ans);
}
普通平衡树 线段树
62 行
CPP JSON
【普通平衡树(线段树)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re p,Re L,Re R,Re k) — 核心算法函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 F(i,1,T) — 核心算法函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e5+3,inf=2147483647 复杂度:建树 O(N),单次操作 O(log N) 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 61 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N]; 
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
	if(L==R)return b[R];
    Re tmp=tree[pl].g;
    if(tmp>=k)return ask_kth(pl,L,mid,k);
    else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(!x)return 0;
	if(L==R)return tree[p].g;
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
	in(T); 
    F(i,1,T){
    	in(opt[i]),in(Q[i]);
    	if(opt[i]!=4)b[++m]=Q[i];
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,T){
    	if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
    	if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
		if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
		if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
		if(opt[i]==5){
			Re level=ask_level(root,1,m,lo(Q[i])-1);
			printf("%d\n",ask_kth(root,1,m,level));
		}
		if(opt[i]==6){
			Re level=ask_level(root,1,m,lo(Q[i]));
			printf("%d\n",ask_kth(root,1,m,level+1));
		}
    }
}
线段树分治 (冰茶姬+线性基 查询两点最短异或和路径) (Shortest Path Queries) 时间分治
95 行
CPP JSON
【线段树分治 (冰茶姬+线性基 查询两点最短异或和路径) (Shortest Path Queries)(时间分治)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) int Dis(Re x) — 核心算法函数 void merge(Re x,Re y,Re w) — 合并操作 void back(Re to) — 获取队尾元素 void insert(Re x) — 插入元素 int ask(Re x) — 核心算法函数 void back(Re to) — 获取队尾元素 核心结构体:Union, BK, Line_JI, QAQ, Segment_Tree 关键配置: N=2e5+3,logN=30 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 94 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=2e5+3,logN=30;
int x,y,n,m,T,op,X[N],Y[N],OP[N];LL Ans[N];map<pair<int,int>,int>last,z;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Union{// 冰茶姬(并查集)
	struct BK{int x,y,dx,dy,sx,sy;BK(Re X=0,Re d1=0,Re S1=0,Re Y=0,Re d2=0,Re S2=0){x=X,y=Y,sx=S1,sy=S2,dx=d1,dy=d2;}};
	int fa[N],dis[N],size[N];stack<BK>Q;
	inline int find(Re x){return fa[x]==x?x:find(fa[x]);}
	inline int Dis(Re x){return fa[x]==x?0:dis[x]^Dis(fa[x]);}
	inline void merge(Re x,Re y,Re w){// 启发式合并
		if(size[x]>size[y])swap(x,y);
		Q.push(BK(x,dis[x],size[x],y,dis[y],size[y]));
		fa[x]=y,dis[x]=w,size[y]+=size[x];
	}
	inline void back(Re to){// 撤销操作
		while(int(Q.size())>to){
			BK a=Q.top();Re x=a.x,y=a.y;Q.pop();
			fa[x]=x,dis[x]=a.dx,size[x]=a.sx;
			fa[y]=y,dis[y]=a.dy,size[y]=a.sy;
		}
	}
}TF;
struct Line_JI{
	int p[31];stack<int>Q;
	inline void insert(Re x){
		for(Re i=logN;i>=0;--i)
			if((x>>i)&1){
				if(!p[i]){p[i]=x,Q.push(i);break;}
				x^=p[i];
			}
	}
	inline int ask(Re x){for(Re i=logN;i>=0;--i)if(p[i])x=min(x,x^p[i]);return x;}
	inline void back(Re to){
		while(int(Q.size())>to)p[Q.top()]=0,Q.pop();
	}
}JI;
int o,head[N<<2];
struct QAQ{int x,y,w,next;}a[N*50];
inline void add(Re x,Re y1,Re y2,Re w){a[++o].w=w,a[o].x=y1,a[o].y=y2,a[o].next=head[x],head[x]=o;}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re y,Re v){
		if(l>r)return;
		if(l<=L&&R<=r){add(p,x,y,v);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,y,v);
		if(r>mid)change(pr,mid+1,R,l,r,x,y,v);
	}
	inline void dfs(Re p,Re L,Re R){
		Re tmp1=TF.Q.size(),tmp2=JI.Q.size();
		for(Re i=head[p];i;i=a[i].next){
			Re x=TF.find(a[i].x),y=TF.find(a[i].y),w=TF.Dis(a[i].x)^TF.Dis(a[i].y)^a[i].w;
			if(x!=y)TF.merge(x,y,w);
			else JI.insert(w);
		}
		if(L==R){if(OP[L])Ans[L]=JI.ask(TF.Dis(X[L])^TF.Dis(Y[L]));}
		else dfs(pl,L,mid),dfs(pr,mid+1,R);
		TF.back(tmp1),JI.back(tmp2);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)TF.fa[i]=i,TF.size[i]=1;
	for(Re i=1;i<=m;++i){
		in(x),in(y);if(x>y)swap(x,y);
		in(z[mp(x,y)]),last[mp(x,y)]=1;
	}
	in(T);
	for(Re i=1;i<=T;++i){
		in(op),in(x),in(y);if(x>y)swap(x,y);
		if(op<2)in(z[mp(x,y)]),last[mp(x,y)]=i;
		else if(op<3)T1.change(1,1,T,last[mp(x,y)],i-1,x,y,z[mp(x,y)]),last.erase(last.find(mp(x,y)));
		else OP[i]=1,X[i]=x,Y[i]=y;
	}
	for(map<pair<int,int>,int>::iterator it=last.begin();it!=last.end();++it)
		T1.change(1,1,T,it->second,T,it->first.first,it->first.second,z[it->first]);
	T1.dfs(1,1,T);
	for(Re i=1;i<=T;++i)if(OP[i])printf("%lld\n",Ans[i]);
}
线段树分治 (可持久化Trie+CDQ) (火星商店问题) 时间分治
90 行
CPP JSON
【线段树分治 (可持久化Trie+CDQ) (火星商店问题)(时间分治)】 可持久化线段树(主席树)模板,通过动态开点维护历史版本。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re p,Re q,Re o,Re x) — 插入元素 int ask(Re p,Re q,Re o,Re x) — 核心算法函数 void change(Re p,Re L,Re R,Re l,Re r,Query &v) — 核心算法函数 int find1(Re l,Re r,Re id) — 查找(并查集寻根/二分查找) int find2(Re l,Re r,Re id) — 查找(并查集寻根/二分查找) void CDQ(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Change, Query, Trie, Segment_Tree 关键配置: N=1e5+3,logN=18 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 89 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18;
int n,x,y,z,w,op,m1,m2,T,A[N],t1[N],t2[N],Ans[N];
struct Change{int i,v,t;inline bool operator<(const Change &O)const{return i<O.i;}}C[N],tmp[N];
struct Query{int x,l,r,id;}Q[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int pt[N];
struct Trie{
	int O,cnt[N*(logN+2)],tr[N*(logN+2)][2];
	inline void insert(Re p,Re q,Re o,Re x){
		if(o<0)return;Re i=(x>>o)&1;
		tr[p][i]=++O,tr[p][i^1]=tr[q][i^1];
		cnt[tr[p][i]]=cnt[tr[q][i]]+1;
		insert(tr[p][i],tr[q][i],o-1,x);
	}
	inline int ask(Re p,Re q,Re o,Re x){
		if(o<0)return 0;Re i=(x>>o)&1;
		if(cnt[tr[q][i^1]]>cnt[tr[p][i^1]])return (1<<o)+ask(tr[p][i^1],tr[q][i^1],o-1,x);
		else return ask(tr[p][i],tr[q][i],o-1,x);
	}
}T1;
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	vector<Query>tr[N<<2];
	inline void change(Re p,Re L,Re R,Re l,Re r,Query &v){
		if(l>r)return;
		if(l<=L&&R<=r){tr[p].push_back(v);return;}
		if(l<=mid)change(pl,L,mid,l,r,v);
		if(r>mid)change(pr,mid+1,R,l,r,v);
	}
	inline int find1(Re l,Re r,Re id){
		if(C[r].i<id)return r+1;
		while(l<r){
			Re Mid=l+r>>1;
			if(C[Mid].i>=id)r=Mid;
			else l=Mid+1;
		}
		return r;
	}
	inline int find2(Re l,Re r,Re id){
		if(C[r].i<=id)return r+1;
		while(l<r){
			Re Mid=l+r>>1;
			if(C[Mid].i>id)r=Mid;
			else l=Mid+1;
		}
		return r;
	}
	inline void CDQ(Re p,Re L,Re R,Re l,Re r){
		if(l>r)return;
		T1.O=pt[l-1]=0;
		for(Re i=l;i<=r;++i)T1.insert(pt[i]=++T1.O,pt[i-1],logN,C[i].v);
		for(vector<Query>::iterator it=tr[p].begin();it!=tr[p].end();++it){
			Re ll=find1(l,r,it->l)-1,rr=find2(l,r,it->r)-1;
			if(ll<rr)Ans[it->id]=max(Ans[it->id],T1.ask(pt[ll],pt[rr],logN,it->x));
		}
		if(L==R)return;
		Re p1=l-1;for(Re i=l;i<=r;++i)if(C[i].t<=mid)tmp[++p1]=C[i];
		Re p2=p1;for(Re i=l;i<=r;++i)if(C[i].t>mid)tmp[++p2]=C[i];
		for(Re i=l;i<=r;++i)C[i]=tmp[i];
		CDQ(pl,L,mid,l,p1),CDQ(pr,mid+1,R,p1+1,r);
	}
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(A[i]),T1.insert(pt[i]=++T1.O,pt[i-1],logN,A[i]);
	for(Re i=1;i<=T;++i){
		in(op),in(x),in(y);
		if(!op)++m1,C[m1]=(Change){x,y,m1};
		else in(z),in(w),++m2,Q[m2]=(Query){z,x,y,m2},t1[m2]=max(1,m1-w+1),t2[m2]=m1;
	}
	for(Re i=1;i<=m2;++i)Ans[i]=T1.ask(pt[Q[i].l-1],pt[Q[i].r],logN,Q[i].x),TR.change(1,1,m1,t1[i],t2[i],Q[i]);
	sort(C+1,C+m1+1),TR.CDQ(1,1,m1,1,m1);
	for(Re i=1;i<=m2;++i)printf("%d\n",Ans[i]);
}
已复制