• 描述: 一种用来管理元素分组情况的数据结构。并查集可以高效的进行如下操作: 查询元素a和元素b是否属于同一个数组。 合并元素a和元素b所在的组。 代码: // 并查集 int par[Max_n]; //父亲 int ...
    • 并查集
    • KMP算法
    • 树状数组
    • 线段树
    • 莫队算法

    1、并查集

    描述: 一种用来管理元素分组情况的数据结构。并查集可以高效的进行如下操作:

    • 查询元素a和元素b是否属于同一个数组。
    • 合并元素a和元素b所在的组。

    代码:

    // 并查集
    int par[Max_n];  //父亲
    int rank[Max_n]; //树的高度
    
    void init(int n){ //初始化n个元素
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }
    
    int find(int x){ //查询树的根(路径压缩)
        if(par[x]==x)return x;
        return par[x]=find(par[x]);
    }
    
    int find(int x){ //非递归写法
        int p,t;
        p=x;
        while(x!=par[x])x=par[x];
        while(p!=x){
            t=par[p];
            par[p]=x;
            p=t;
        }
        return x;
    }
    
    void unite(int x,int y){ //合并x和y所属的集合(按秩归并)
        x=find(x);
        y=find(y);
        if(x==y)return;
        if(rank[x]<rank[y])par[x]=y;
        else par[y]=x;
        if(rank[x]==rank[y])rank[x]++;
    }
    

    **复杂度:**加入优化后效率非常高,对n个元素的元素进行一次操作的复杂度是O(α(n)),比O(logn)还要快。

    2、KMP算法

    描述: KMP算法是一种改进的字符串匹配算法,是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的,时间复杂度O(m+n)。
    SouthEast

    • pmt数组记录的是字符串前缀集合和后缀集合的最长匹配。为了编程的方便,不直接使用pmt数组,而pmt数组向后偏移一位得到next数组。即next数组 记录的是主串字符与模式串字符失配时,主串应与模式串的第next[j]个字符再进行比较。

    代码:

    next是C++中的保留字,使用next数组,会CE!

    char s[Max_n],t[Max_n];
    int next[Max_n];
    int slen,tlen;
    
    void getNext(){ //next数组
        int i=0,j=-1;
        next[0]=-1;
        while(i<tlen){
            if(j==-1||t[i]==t[j]){
                i++;j++;
                next[i]=j;
            }
            else j=next[j];
        }
    }
    
    void getNext2(){ //优化的next数组
        int i=0,j=-1;
        next[0]=-1;
        while(i<tlen){
            if(j==-1||t[i]==t[j]){
                i++;j++;
                if(t[i]==t[j])next[i]=next[j];
                else next[i]=j;
            }
            else j=next[j];
        }
    }
    
    int kmp_index(){ //返回模式串T在主串S中首次出现的位置
        int i=0,j=0;
        getNext();
        while(i<slen&&j<tlen){
            if(j==-1||s[i]==t[j]){
                i++;j++;
            }
            else j=next[j];
        }
        if(j==tlen)return i-j;
        else return -1;
    }
    
    int kmp_count(){ //返回模式串在主串S中出现的次数
        int i=0,j=0,k=0;
        getNext();
        while(i<slen){
            if(j==-1||s[i]==t[j]){
                i++;j++;
            }
            else j=next[j];
            if(j==tlen){
                k++;
                j=next[j];
            }
        }
        return k;
    }
    
    // KMP求最小循环节、循环周期
    
    定理:假设S的长度为len,则S存在最小循环节,循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。
    (1)如果len可以被len - next[len]整除,则表明字符串S可以完全由循环节循环组成,循环周期T=len/L。
    (2)如果不能,说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L。
     
    简单理解:
    对于字符串abcd abcd abcd,由长度为4的字符串abcd重复3次得到,那么必然有原字符串的前八位等于后八位。
    也就是说,对于某个字符串S,由长度为L的字符串s重复R次得到,当R≥2时必有S[0..len-L-1]=S[L..len-1](下标从0开始)
    那么对于KMP算法来说,就有next[len]=len-L。此时L肯定已经是最小的。
    (因为next的值是前缀和后缀相等的最大长度,即len-L是最大的,那么在len已经确定的情况下,L是最小的)。
    
    

    next数组和优化后的next2数组:
    在这里插入图片描述

    3、树状数组

    描述: 树状数组用来维护数组的前缀和,从而可以快速求得某一个区间的和,并支持对元素的值进行修改。但是树状数组并非只有这一种功能,变形后它还能衍生出两个功能,本文我们就来分别讨论下树状数组这三大功能。

    永远要记住,基本的树状数组维护的是数组的前缀和,所有的区间求值都可以转化成用 sum[m]-sum[n-1] 来解,这点无论是在改点还是接下来要说的改段中都非常重要!

    1.改点求段(单点修改 区间查询)

    这也是树状数组的基本应用。我们可以来看一下这道题 敌兵布阵
    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max_n=1e5+10;
    
    int t,n,k=0;
    int c[Max_n];
    
    int lowbit(int k){
        return k&-k;
    }
    
    void update(int k,int val){
        while(k<=n){
            c[k]+=val;
            k+=lowbit(k);
        }
    }
    
    int sum(int k){
        int ans=0;
        while(k>0){
            ans+=c[k];
            k-=lowbit(k);
        }
        return ans;
    }
    
    int main()
    {
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            int a,b;
            char s[10];
            memset(c,0,sizeof(c));
            for(int i=1;i<=n;i++){
                scanf("%d",&a);
                update(i,a);
            }
            printf("Case %d:\n",++k);
            while(~scanf("%s",s)&&s[0]!='E'){
                if(s[0]=='Q'){
                    scanf("%d%d",&a,&b);
                    printf("%d\n",sum(b)-sum(a-1));
                }
                else if(s[0]=='A'){
                    scanf("%d%d",&a,&b);
                    update(a,b);
                }
                else {
                    scanf("%d%d",&a,&b);
                    update(a,-b);
                }
            }
        }
        return 0;
    }
    

    2.改段求点(区间修改 单点查询)

    改段求点和改点求段恰好相反,比如有一个数组 a = [x, 0, 0, 0, 0, 0, 0, 0, 0, 0],每次的修改都是一段,比如让 a[1]~a[5] 中每个元素都加上10,让 a[6]~a[9] 中每个元素都减去2,求任意的元素的值。

    看例题: Color the ball

    跟改点求段不同,这里要转变一个思想。在改点求段中,c[i]表示Ci节点所管辖的子节点的元素和,而在改段求点中,c[i]表示Ci所管辖子节点的批量统一增量。

    还是看这个经典的图:
    这里写图片描述
    比方说,C8管辖A1A8这8个节点,如果A1A8每个都染色一次,因为前面说了c[i]表示i所管辖子节点的统一增量,那么也就是 c[8]+=1,A5~A7都染色两次,也就是 c[6] +=2, c[7] +=2 。如果要求A1被染色的次数,C8是能管辖到A1的,也就是说c[8]的值和A1被染色的次数有关,仔细想想,也就是把能管辖到A1的父节点的c值累积起来即可。两个过程正好和改点求段相反。

    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max_n=1e5+10;
    
    int n;
    int c[Max_n];
    
    int lowbit(int k){
        return k&-k;
    }
    
    void update(int k,int val){
        while(k>0){
            c[k]+=val;
            k-=lowbit(k);
        }
    }
    
    int query(int k){
        int ans=0;
        while(k<=n){
            ans+=c[k];
            k+=lowbit(k);
        }
        return ans;
    }
    
    int main()
    {
        while(~scanf("%d",&n)&n){
            memset(c,0,sizeof(c));
            int a,b;
            for(int i=0;i<n;i++){
                scanf("%d%d",&a,&b);
                update(a-1,-1);update(b,1);
            }
            printf("%d",query(1));
            for(int i=2;i<=n;i++)
                printf(" %d",query(i));
            putchar('\n');
        }
    
        return 0;
    }
    
    

    3.改段求段(区间修改 区间查询)

    改段求段也有道经典的模板题:A Simple Problem with Integers

    我们还是从简单的例子入手,比如有数组a[10]={1,2,3…9}。

    假设我们将 a[1]~a[4] 这段增加5,对于我们要求的区间和来说,要么是 [1,2] 这种属于所改段的子区间,要么是 [1,8] 这种属于所改段的父区间(前面说了,所有的区间求值都可以用sum[m]-sum[n-1]来解,所以我们只考虑前缀和),我们分别讨论。

    1)如果所求是类似 [1,8] 这种,我们可以很开心地发现,我们将区间增量(4*5)全部加在 a[4] 这个元素上,对结果并没有什么影响!于是变成了一般的改点求段

    2)如果所求是类似 [1,2] 这种,我们可以用类似改段求点中染色的思想进行处理。譬如 [1,4] 成段加5,如果我们要计算 [1,2] 的和。我们将 [1,3] 进行“染色”(节点4加上了4*5的权重),因为 [1,3] 在树状数组的划分中可以分为两个区间,[1,2] 和 [3,3],所以我们用类似改段求点对这两块区域进行“染色”,染上的次数为5。我们要求的是 [1,2] 的区间和,我们只需找 2 被染色的次数,因为 [1,n] 进行染色。如果m(1<=m<=n)被染色,那么m的左边肯定都被染色了。求出被染色的次数,然后乘上区间宽度,就是整段的和了。

    这样我们分别对两种情况进行了处理,更重要的是,这两种情况互不影响!于是我们简单地把两个结果相加就ok了,而这两个过程,分别正是改点求段和改段求点!

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max_n=1e5+10;
    
    int N,Q;
    ll b[Max_n],c[Max_n];
    
    int lowbit(int k){
        return k&-k;
    }
    
    void update_backward(int k,int val){ 
        while(k<=N){
            b[k]+=val;
            k+=lowbit(k);
        }
    }
    
    void update_forward(int k,int val){ 
        while(k>0){
            c[k]+=val;
            k-=lowbit(k);
        }
    }
    
    void update(int k,int val){
        update_backward(k,k*val);
        update_forward(k-1,val);
    }
    
    ll query_forward(int k){
        ll ans=0;
        while(k>0){
            ans+=b[k];
            k-=lowbit(k);
        }
        return ans;
    }
    
    ll query_backward(int k){
        ll ans=0;
        while(k<=N){
            ans+=c[k];
            k+=lowbit(k);
        }
        return ans;
    }
    
    ll query(int k){
        return query_forward(k)+k*query_backward(k);
    }
    
    int main()
    {
        scanf("%d%d",&N,&Q);
        int x,y,z;
        char s[10];
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        N+=1;  //下标2~n+1
        for(int i=2;i<=N;i++){
            scanf("%d",&x);
            update_backward(i,x);
        }
        for(int i=0;i<Q;i++){
            scanf("%s",s);
            if(s[0]=='Q'){
                scanf("%d%d",&x,&y);
                x++;y++;
                printf("%lld\n",query(y)-query(x-1));
            }
            else {
                scanf("%d%d%d",&x,&y,&z);
                x++;y++;
                update(y,z);
                update(x-1,-z);
            }
        }
        return 0;
    }
    

    注意: 一般的用数组来解的题,都是不用a[0]的,也就是元素是从a[1]~a[n]。而本题中的改段求段中的元素是从 a[2]~a[n+1],因为 update()更新区间[1,x](x为任意值)时,左端点为0向后更新update_backward会造成死循环!

    // 支持本小节树状数组原创作者:韩子迟,十分感谢~~

    4、线段树

    描述: 是一种树状结构来存储一个连续区间的信息的数据结构。线段树是平衡二叉树,所有操作都是logn级别,每个节点对应一个区间。关键的一点:需要维护哪些区间的附件信息,怎样维护这个信息。

    代码风格:

    1. 数组要开节点数Max_n的4倍,详见证明,lson和rson分别代表当前节点的左右儿子。
    2. 函数传参时,同时传递当前儿子的节点rt和对应的区间[l,r]。
    3. pushUP(int rt) 把当前结点的信息更新给父结点。
      pushDown(int rt) 把当前结点的信息更新给儿子结点。
    4. 线段树维护的区间范围是[1,x],根节点从1开始(1,2,3…)!!!

    hdu-1166 敌兵布阵

    • 简单的单点修改,区间查询
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    const int Max_n=5e4+10;
    
    int tree[Max_n<<2];
    
    void pushUp(int rt){
    	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    }
    
    void build(int l,int r,int rt){
    	if(l==r){
    		scanf("%d",&tree[rt]);
    		return;
    	}
    	int m=(l+r)>>1;
    	build(lson);build(rson);
    	pushUp(rt);
    }
    
    void update(int k,int value,int l,int r,int rt){ //单点更新 
    	if(l==r){
    		tree[rt]+=value;
    		return;
    	} 
    	int m=(l+r)>>1;
    	if(k<=m)update(k,value,lson);
    	else update(k,value,rson);
    	pushUp(rt);
    } 
    
    int query(int L,int R,int l,int r,int rt){
    	if(r<=R&&l>=L)return tree[rt];
    	int ans=0;
    	int m=(l+r)>>1;
    	if(L<=m)ans+=query(L,R,lson);
    	if(R>=m+1)ans+=query(L,R,rson);
    	return ans; 
    }
    
    int main()
    {
    	int T,n;
    	scanf("%d",&T);
    	for(int i=1;i<=T;i++){
    		printf("Case %d:\n",i);
    		scanf("%d",&n); 
    		build(1,n,1);
    		char s[110];
    		int x,y;
    		while(~scanf("%s",s)&&s[0]!='E'){
    			scanf("%d%d",&x,&y);
    			if(s[0]=='A')update(x,y,1,n,1);
    			else if(s[0]=='S')update(x,-y,1,n,1);
    			else printf("%d\n",query(x,y,1,n,1));
    		}
    	}
    	return 0;
    }
    

    poj 3468 A Simple Problem with Integers

    • 区间修改,区间查询(lazy标记)
    • lazy标记思想:更新到某个区间的时候,先给这个区间打上lazy标记,不去更新子区间。当下一次更新子区间的时候再把该区间的lazy标记更新到子区间。从而避免浪费更新那些不必要的结点的时间。
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    using namespace std; 
    typedef long long ll;
    const int Max_n=1e5+10;
    
    int s[Max_n];
    ll sum[Max_n<<2];
    int lazy[Max_n<<2];
    
    void pushUp(int rt){
    	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    
    void pushDown(int rt,int len){
    	if(lazy[rt]){
    		lazy[rt<<1]+=lazy[rt];
    		lazy[rt<<1|1]+=lazy[rt];
    		sum[rt<<1]+=(len-(len>>1))*lazy[rt];
    		sum[rt<<1|1]+=(len>>1)*lazy[rt];
    		lazy[rt]=0;
    	}
    }
    
    void build(int l,int r,int rt){
    	lazy[rt]=0;
    	if(l==r){
    		sum[rt]=s[l];
    		return;
    	}
    	int m=(l+r)>>1;
    	build(lson);build(rson);
    	pushUp(rt);
    }
    
    void update(int L,int R,int c,int l,int r,int rt){
    	if(l>=L&&r<=R){
    		lazy[rt]+=c;
    		sum[rt]+=(ll)c*(r-l+1);
    		return;
    	}
    	int m=(l+r)>>1;
    	pushDown(rt,r-l+1);
    	if(L<=m)update(L,R,c,lson);
    	if(R>=m+1)update(L,R,c,rson);
    	pushUp(rt);
    }
    
    ll query(int L,int R,int l,int r,int rt){
    	if(l>=L&&r<=R)return sum[rt];
    	pushDown(rt,r-l+1);
    	int m=(l+r)>>1;
    	ll ans=0;
    	if(L<=m)ans+=query(L,R,lson);
    	if(R>=m+1)ans+=query(L,R,rson);
    	return ans;
    }
    
    int main()
    {
    	int n,t;
    	scanf("%d%d",&n,&t);
    	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    	build(1,n,1);
    	char ch;
    	int x,y,z;
    	while(t--){
    		cout<<t<<'&'<<endl;
    		scanf("%c",&ch);
    		if(ch=='Q'){
    			scanf("%d%d",&x,&y);
    			printf("%lld\n",query(x,y,1,n,1));
    		} 
    		else {
    			scanf("%d%d%d",&x,&y,&z);
    			update(x,y,z,1,n,1);
    		}
    	}
    	
    	return 0;
    }
    

    5、莫队算法

    描述: 一种优雅的暴力,离线处理一类区间不修改查询类问题的算法。通过预先知道所有的询问,合理的组织每个询问的顺序以此来降低复杂度。
    复杂度: O(n*√n)

















































    66666666666666666666666666

    展开全文
  • STL中数据结构通用操作 1.1二分查找 1.2排列生成 栈 2.1单调栈 队列 3.1优先队列 3.2单调队列 向量 链表 5.1链式前向星 堆 6.1映射二叉堆 集合 映射 ST表 并查集 *10.1带权并查集 *10.2种类并查集...

    目录

    1. STL中数据结构通用操作
      1.1二分查找
      1.2排列生成

    2. 2.1单调栈
    3. 队列
      3.1优先队列
      3.2单调队列
    4. 向量
    5. 链表
      5.1链式前向星
      5.2舞蹈链(dancing links)

    6. 6.1映射二叉堆
    7. 集合
    8. 映射
    9. ST表
    10. 并查集
      *10.1带权并查集
      *10.2种类并查集
      *10.3可持久化并查集
    11. 树状数组
    12. 线段树
      12.1 ZKW线段树
      *12.2 权值线段树
      12.3 可持久化线段树(主席树)
    13. 平衡树
      13.1 Splay伸展树
      13.2 Treap树堆
      13.3 替罪羊树(重量平衡树)
    14. 珂朵莉树(ODT)
    15. KD树(kd-tree)
    16. Trie字典树
      16.1自动机
    17. LCT(动态森林)
    18. 序列
      18.1 dfs序
      18.2 欧拉序
    19. 树链剖分
    20. 根号算法
      20.1分块算法
      20.2莫队算法
    21. CDQ分治
      21.1三维偏序
      21.2四维偏序

    注:由于数据结构过于繁杂,部分*内容后续会慢慢补齐,持续更新中…


    一.STL中数据结构常见操作

    1. a.assign(b.begin(), b.begin()+3); //b为向量,将b的0~2个元素构成的向量赋给a
    2. a.assign(4,2); //是a只含4个元素,且每个元素为2
    3. a.back(); //返回a的最后一个元素
    4. a.front(); //返回a的第一个元素
    5. a[i]; //返回a的第i个元素,当且仅当a[i]存在2013-12-07
    6.  a.clear(); //清空a中的元素
    7.  a.empty(); //判断a是否为空,空则返回ture,不空则返回false
    8. a.pop_back(); //删除a向量的最后一个元素
    9. a.erase(a.begin()+1,a.begin()+3); //删除a中第1个(从第0个算起)到第2个元素,也就是说删除的元素从a.begin()+1算起(包括它)一直到a.begin()+         3(不包括它)
    10.  a.push_back(5); //在a的最后一个向量后插入一个元素,其值为5
    11.  a.insert(a.begin()+1,5); //在a的第1个元素(从第0个算起)的位置插入数值5,如a为1,2,3,4,插入元素后为1,5,2,3,4
    12.  a.insert(a.begin()+1,3,5); //在a的第1个元素(从第0个算起)的位置插入3个数,其值都为5
    13.  a.insert(a.begin()+1,b+3,b+6); //b为数组,在a的第1个元素(从第0个算起)的位置插入b的第3个元素到第5个元素(不包括b+6),如b为1,2,3,4,5,9,8         ,插入元素后为1,4,5,9,2,3,4,5,9,8
    14.  a.size(); //返回a中元素的个数;
    15.  a.capacity(); //返回a在内存中总共可以容纳的元素个数
    16.  a.resize(10); //将a的现有元素个数调至10个,多则删,少则补,其值随机
    17.  a.resize(10,2); //将a的现有元素个数调至10个,多则删,少则补,其值为2
    18. a.reserve(100); //将a的容量(capacity)扩充至100,也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义,因为这将避免内存多次容量扩充操作(当a的容量不足时电脑会自动扩容,当然这必然降低性能)
    19. a.swap(b); //b为向量,将a中的元素和b中的元素进行整体性交换
    20. a==b; //b为向量,向量的比较操作还有!=,>=,<=,>,<
    21. sort(a.begin(),a.end()); //对a中的从a.begin()(包括它)到a.end()(不包括它)的元素进行从小到大排列
    22. reverse(a.begin(),a.end()); //对a中的从a.begin()(包括它)到a.end()(不包括它)的元素倒置,但不排列,如a中元素为1,3,2,4,倒置后为4,2,3,1
    23. copy(a.begin(),a.end(),b.begin()+1); //把a中的从a.begin()(包括它)到a.end()(不包括它)的元素复制到b中,从b.begin()+1的位置(包括它)开 始复制,覆盖掉原有元素
    24. find(a.begin(),a.end(),10); //在a中的从a.begin()(包括它)到a.end()(不包括它)的元素中查找10,若存在返回其在向量中的位置
    

    1.二分查找:

    只能对有序数列使用,内部通过二分查找实现

    lower_bound(a,a+n,m):返回数组a中,0~n里第一个大于等于m的指针
    int pos=lower_bound(a,a+n,m)-a:返回数组a中,0~n里第一个大于等于m的位置
    
    upper_bound(a,a+n,m):返回数组a中,0~n里第一个大于m的指针
    int pos=upper_bound(a,a+n,m)-a:返回数组a中,0~n里第一个大于m的位置
    
    lower_bound(seq2, seq2+6, 7, greater<int>()):加greater<int>()后,lower变小于等于,upper变小于

    2.排列:

    头文件:#include< algorithm>
    next_permutation(a,a+3) //求数组a中前3个元素的下一个排列
    prev_permutation(a,a+3) //求数组a中前3个元素的前一个排列
    a可为普通数组,string,vector……

    求1-10的第10个排列
    a[10]={1,2,3,4,5,6,7,8,9,10};
    for(int i=1;i< k;i++)
    next_permutation(a,a+10);
    for(int i=0;i<10;i++)
    cout<< a[i]< < ” “;


    二.栈

    建立:stack< T >S;
    入栈:S.push(a);
    取栈顶元素:S.top();
    删除栈顶元素:S.pop();

    1.单调栈

    https://blog.csdn.net/wubaizhe/article/details/70136174
    利用单调栈,可以找到从左/右遍历第一个比它小/大的元素的位置.由此也可知道该区间上数的个数O(n)
    可统计出a[i]~a[n],以i为起点的单调序列长度,从后向前建立单调栈,常做预处理用
    一个元素向左遍历的第一个比它小的数的位置就是将它插入单调栈时栈顶元素的值,若栈为空,则说明不存在这么一个数。然后将此元素的下标存入栈,就能类似迭代般地求解后面的元素

    #include <iostream>
    #include <stack>
    using namespace std;
    
    stack<int>s;
    int n;
    int ans[N];          //ans[i],表示第i个元素,向左遍历,第一个比它小的元素的位置
    void getans(int a[])
    {
        for(int i=1;i<=n;i++)
        {
            while(s.size() && a[s.top()]>=a[i]) s.pop();
            if(s.empty()) ans[i]=0;
            else ans[i]=s.top();
            s.push(i);
        }
    }

    三.队列

    建立:queue< T>Q;
    入队:Q.push(a);
    出队:Q.front();
    删除:Q.pop();

    1.优先队列

    头文件:#include< queue>
    默认从大到小排列
    声明:
    普通优先队列:priority_queue< int>Q;
    从小到大优先队列:priority_queue< int,vector< int>,greater< int> >Q;
    对结构体应用优先队列:

    struct Node
    {
        int x,y,val;
        friend bool operator < (node n1,node n2)
        {
                if(n1.val==n2.val)
                    return n1.x>n2.x;
            return n1.val<n2.val;    //和正常不同,"<"为从大到小,">"为从小到大
        }
    };
    priority_queue<node>Q

    2.单调队列

    整理归纳单调队列的定义:
    1、维护区间最值;
    2、去除冗杂状态;
    3、保持队列单调(最大值是单调递减序列,最小值是单调递增序列);
    4、最优选择在队首。
    在维护好一个 区间正确、严格递减 的单调递减队列后,队列头就是当前区间的最大值了

    整理归纳单调队列的使用方法:
    1、维护队首(对于上题就是如果你已经是当前的m个之前那你就可以被删了) ;
    2、在队尾插入(每插入一个就要从队尾开始往前去除冗杂状态) ;
    3、取出需要的最优解(队列头的值即是);
    4、借助最优解,得到目前所求的最优解(通常此处插入DP方程)。

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[200000];
    struct node
    {
        int x,p;
        node(){}
        node(int xx,int pp){x=xx;p=pp;}
    }list[200000];
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int head=1,tail=1;
        list[1]=node(a[1],1);
        for(int i=2;i<=n;i++)
        {
            while(head<=tail&&list[tail].x<=a[i]) tail--;//删尾
            list[++tail]=node(a[i],i);//得到最优解并插入
            while(i-list[head].p>=m) head++;//去头
            if(i>=m) printf("%d\n",list[head]);
        }
        return 0;
    }

    四.向量

    可作为数组的替代,但效率不如数组

    建立:vector< T >V;
    加入:V.push_back(a);
    删除:V.earse()


    五.链表

    stl中默认实现双向链表

    建立:list< T>L;
    L.assign(a) 给list赋值
    L.back() 返回最后一个元素
    L.erase() 删除一个元素
    L.front() 返回第一个元素
    L.insert() 插入一个元素到list中
    L.pop_back() 删除最后一个元素
    L.pop_front() 删除第一个元素
    L.push_back() 在list的末尾添加一个元素
    L.push_front() 在list的头部添加一个元素
    L.remove() 从list删除元素
    L.remove_if() 按指定条件删除元素

    1.链式前向星

    即用数组模拟链表

    #include <iostream>
    #include <string.h>
    using namespace std;
    int const MAX_M=100000;     //一定要开很大,否则会TLE
    int const MAX_N=100000;
    struct Edge
    {
        int to,cost,next;
    }e[MAX_M];
    int eid,p[MAX_N];
    void init()
    {
        eid=0;
        memset(p,-1,sizeof(p));
    }
    void insert(int u,int v,int c)
    {
        e[eid].to=v;
        e[eid].cost=c;
        e[eid].next=p[u];
        p[u]=eid++;
    }
    void addedge(int u,int v,int c)
    {
        insert(u,v,c);
        insert(v,u,0);
    }
    int main()
    {
        init()    //初始化,每次必须要有!
        addedge(a,b,c);         //读入边
        for(int i=p[u];i!=-1;i=e[i].next)   //遍历u连向的所有边
        {
            cout<<u<<"->"<<e[i].to<<e[i].next<<e[i].cost;
        }
    }

    适用范围:解决精确覆盖问题,例如数独,n皇后问题;以及重复覆盖问题。
    精确覆盖:在一个全集X中若干子集的集合为S,精确覆盖(Exactcover)是指,S的子集S*,满足X中的每一个元素在S*中恰好出现一次
    矩阵表示法:
      包含关系可以用一个关系矩阵表示。.矩阵每行表示S的一个子集,每列表示X中的一个元素。矩阵行列交点元素为1表示对应的元素在对应的集合中,不在则为0。
      通过这种矩阵表示法,求一个精确覆盖转化为求矩阵的若干个行的集合,使每列有且仅有一个1。同时,该问题也是精确覆盖的典型例题之一。
    图论表示法:
      可将精确覆盖问题转化为一个二分图,左侧为集合,右侧为元素,左侧集合若与右侧元素有包含关系则连边,通过将左侧节点与其所有边保留与否求解一个右侧的每一个节点恰好有一条边的匹配。
    重复覆盖问题:
    即选取一个01矩阵中的几行,使这几行组成的新矩阵的每一列至少有一个1。 该问题在精确覆盖问题上减少了一个约束条件。

    struct DLX//dancing links
    {
        int U[maxnode],D[maxnode],L[maxnode],R[maxnode],col[maxnode],row[maxnode];//元素上下左右对应列对应行的指针
        int S[maxn],H[maxn],V[maxn];//S为每列元素个数,H指向每行末尾的元素,V是dep()函数的标记数组。
        int n,m,size,all;//all为解的行数的最大值
        void init(int _n,int _m,int _all)
        {
            n=_n;
            m=_m;
            all=_all;
            for(int i=0;i<=m;i++)
            {
                L[i]=i-1;
                R[i]=i+1;
                U[i]=i;
                D[i]=i;
                row[i]=0;
                col[i]=i;
            }
            clr(S);
            clrlow(H);
            L[0]=m;
            R[m]=0;
            size=m;
            return ;
        }
        //初始化
        void push(int r,int c)
        {
            D[++size]=D[c];
            col[size]=U[size]=c;
            U[D[c]]=size;
            D[c]=size;
            row[size]=r;
            S[c]++;
            if(H[r]<0)
            {
                H[r]=L[size]=R[size]=size;
            }
            else
            {
                L[size]=H[r];
                R[size]=R[H[r]];
                L[R[H[r]]]=size;    
                R[H[r]]=size;
            }    
            return ;
        }
        //加入元素
        void del(int c)
        {
            S[col[c]]--;
            for(int i=D[c];i!=c;i=D[i])
                {
                    R[L[i]]=R[i];
                    L[R[i]]=L[i];
                    S[col[i]]--;
                }
            return ;
        }
         //删除一列
         void reback(int c)
         {
             for(int i=U[c];i!=c;i=U[i])
             {
                 S[col[R[L[i]]=L[R[i]]=i]]++;
             }
             S[col[c]]++;
             return ;
         }
         //恢复一列
         int  dep( )
         {
             clr(V);
             int deep=0;
             for(int i=R[0];i!=0;i=R[i])
             if(!V[i])
             {
                 deep++;
                 for(int j=D[i];j!=i;j=D[j])
                     for(int k=R[j];k!=j;k=R[k])
                             V[col[k]]=1;
             }
             return deep;
         }
         //之后到达的最大深度
         //d为当前深度
         bool dancing(int d)
         {
             if(d+dep()>all) return false;
             int c=R[0];
             if(c==0)
             {
                 return d<=all;
            }
            for(int i=R[0];i!=0;i=R[i])
                if(S[i]<S[c])
                    c=i;
             for(int i=D[c];i!=c;i=D[i])
             {
                 del(i);
                 for(int j=R[i];j!=i;j=R[j])
                     del(j);
                 if(dancing(d+1)) return true;
                 for(int j=L[i];j!=i;j=L[j])
                     reback(j);
                 reback(i);
             }
             return false;
         }
         //dancing
    }dlx;

    六.堆

    STL中的建立的队默认是最大堆,要想用最小堆的话,必须要在push_heap,pop_heap,make_heap等每一个函数后面加第三个参数greater< int>(),括号不能省略

    make_heap(_First, _Last, _Comp); //默认是建立最大堆的。对int类型,可以在第三个参数传入greater()得到最小堆。
    push_heap (_First, _Last); //在堆中添加数据,要先在容器中加入数据,再调用push_heap ()
    pop_heap(_First, _Last); //在堆中删除数据,要先调用pop_heap()再在容器中删除数据
    sort_heap(_First, _Last); //堆排序,排序之后就不再是一个合法的heap了

    1.映射二叉堆:

    利用set实现,可以在log(n)的时间进行增,删,改,查操作,利用优先级进行排序,再映射到相应内容

    #define PII pair<int, int>
    set<PII, greater<PII>> gheap;    // 定义了一个大根堆
    set<PII, less<PII>> lheap;    // 定义了一个小根堆
    
    //pair的first储存关键字(优先级),second储存索引或内容
    int keys[MAX_INDEX];  // 存储每个索引对应的内容,如果索引的范围很大,可以用 map<int, int> 来储存
    //堆的插入
    gheap.insert(make_pair(value, id));
    //取堆顶元素
    set<PII, greater<PII>>::iterator iter = gheap.begin();
    cout << iter->first << " " << iter->second << endl;  // 第一个数是堆顶元素的关键字,第二个数是堆顶元素的索引
    //取堆尾元素
    set<PII, greater<PII>>::reverse_iterator riter = gheap.rbegin();
    cout<< riter->first<<" "<<riter->second<<endl;
    //删除指定元素
    gheap.erase(make_pair(keys[idx], idx));
    //删除堆顶元素
    gheap.erase(*(gheap.begin()));
    //删除堆尾元素
    riter=gheap.rbegin();
    int a=riter->first;
    int b=riter->second;
    gheap.erase(make_pair(a,b));

    七.集合

    内部通过红黑树实现,各种操作均为O(logn),集合中没有重复元素,且默认按从小到大排序

      头文件:#include<set>
      声明:set<T>s;
      迭代器:set<T>::iterator;
      插入:A.insert("Tom");
      删除:A.erase("Tom");    只支持正向迭代器
      查找:A.count("Tom");
      遍历:set<string>::iterator it;
                for(it=A.begin();it!=A.end();it++)
                    cout<<(*it);
      正向: 
                A.begin(); 返回集合中第一个元素的迭代器
                A.end(); 返回集合中最后一个元素下一位置的迭代器
      反向:
                set<T>:: reverse_iterator;
                A.rbegin(); 返回集合中最后一个元素的反向迭代器
                A.rend(); 返回集合中第一个元素前一位置的反向迭代器
      清空:A.clear();
      取并:set_union(A.begin(),A.end(),B.begin(),B.end(),inserter( C , C.begin() ) );  将A集合与B集合取并后存入C集合,要去A,B必须有序
      取交:set_intersection(A.begin(),A.end(),B.begin(),B.end(),inserter( C , C.begin() ));   取交集,同上

    八.映射

    基本与set相同,常用于将字符串映射成数字等操作

      头文件:#include<map>
      声明:map<T1,T2>m;
      插入:A.insert(pari<string,int>("Tom",1));
                A["Tom"]=1;
      访问:cout<<A["Tom"];
      查找:A.count("Tom")
                若存在返回1,否则返回0
      遍历:map<string,int>::iterator it;
                for(it=A.begin();it!=A.end();it++)
                    cout<<it->first<<it->second;
      清空:A.clear();
      删除:A.erase(it);

    九.ST表

    常用于RMQ问题,即区间最值查询,不支持修改,预处理O(nlogn),每次查询仅为O(1)

    void REQ_init(vector<int> A) {
        int n = A.size();
        for (int i = 0; i < n; ++i) f[i][0] = A[i];
        for (int j = 1; (1 << j) <= n; ++j) // 枚举长度 2^j
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
    }
    int RMQ(int L, int R) {
        int k = 0;
        while ((1 << (k + 1)) <= R - L + 1) ++k;
        return max(f[L][k], f[R - (1 << k) + 1][k]);
    }

    十.并查集

    用于维护各个点之间的关系,可快速判断某点是否属于某一类集合

    int fa[N],rank[N];
    void init(int n)    //初始化
    {
          for(int i=0;i<n;i++)
           {
               fa[i]=i;
                rank[i]=0;
           }
    }
    int find(int x)
    {
           if(fa[x]==x)
              return x;
            else
              return fa[x]=find(fa[x]);           //路径压缩
    }
    void unite(int x,int y)
    {
           x=find(x);
            y=find(y);
            if(x==y) return ;
            if(rank[x]<rank[y])
              fa[x]=y;
            else
            {
              fa[y]=x;
              if(rank[x]==rank[y])
                 rank[x]++;
            }
    }
    bool same(int x,int y)
    {
              return find(x)==find(y);
    }

    十一.树状数组

    利用二进制性质,可在O(logn)对区间前缀进行查询和修改操作

    #include <iostream>
    #include <string.h>
    using namespace std;
    const int N=100050;
    int c[N],ans[N];      //c[n]表示a[1~n]的和,a数组省略
    int lowbit(int x)       //求2^k
    { 
        return x & -x;
    }
    int getsum(int n)   //区间查询,求a[1~n]的和
    {
        int res = 0;
        while(n>0)
        {
            res+=c[n];
            n=n-lowbit(n);
        }
        return res;
    }
    int change(int x)  //单点更新,将a[x]的值加1
    {
         while(x<=N)
         {
             c[x]++;
             x+=lowbit(x);
         }
    }
    int main()
    {
        int n;
        cin>>n;
        memset(c,0,sizeof(c));
        memset(ans,0,sizeof(ans));
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            x++;
            ans[getsum(x)]++;
            change(x);
        }
        for(int i=0;i<n;i++)
            cout<<ans[i]<<endl;
        return 0;
    }

    十二.线段树

    比树状数组更为灵活,功能更加强大,对于区间操作,支持单点修改,区间修改,区间查询等

    单点操作,区间查询:

    #include<cstdio>  
    #include<iostream>  
    #include<algorithm>  
    #include<queue>  
    #include<cstring>  
    #include<cmath>  
    using namespace std;  
    #define INF 10000000  
    #define lson l,mid,rt<<1      //左儿子  
    #define rson mid+1,r,rt<<1|1  //右儿子  
    const int maxn = 222222;  
    struct Node{  
        int Max,Min;  //区间的最大值和最小值  
        int sum;      //区间的和  
    }stree[maxn<<2];  
    void up(int rt){  //更新该区间的最值与和  
        stree[rt].Max=max(stree[rt<<1].Max,stree[rt<<1|1].Max);  
        stree[rt].Min=min(stree[rt<<1].Min,stree[rt<<1|1].Min);  
        stree[rt].sum=stree[rt<<1].sum+stree[rt<<1|1].sum;  
    }  
    void build(int l,int r,int rt){  //在结点i上建立区间为[l,r]  
        if(l==r){                    //叶子结点  
            int num;  
            scanf("%d",&num);  
            stree[rt].Max=stree[rt].Min=stree[rt].sum=num;  
            return ;  
        }  
        int mid=(l+r)>>1;  
        build(lson); //建立左儿子  
        build(rson); //建立右儿子  
        up(rt);      //更新  
    }  
    int querymax(int a,int b,int l,int r,int rt){  //求区间[a,b]的最大值  
        if(a<=l&&r<=b){  //如果全包含,直接取区间最大值  
            return stree[rt].Max;  
        }  
        int mid = (r+l)>>1;  
        int ret = -INF;  
        if(a<=mid) ret=max(ret,querymax(a,b,lson));//如果左端点在中点的左边,找出左区间的最大值  
        if(mid<b) ret=max(ret,querymax(a,b,rson));//如果右端点在中点的右边,找出右区间(以及左区间)的最大值  
        return ret;  
    }  
    int querymin(int a,int b,int l,int r,int rt){  //求区间[a,b]的最小值  
        if(a<=l&&r<=b){  //如果全包含,直接取区间最小值  
            return stree[rt].Min;  
        }  
        int mid = (r+l)>>1;  
        int ret = INF;  
        if(a<=mid) ret=min(ret,querymin(a,b,lson));//如果左端点在中点的左边,找出左区间的最小值  
        if(mid<b) ret=min(ret,querymin(a,b,rson)); //如果右端点在中点的右边,找出右区间(以及左区间)的最小值  
        return ret;  
    }  
    int querysum(int a,int b,int l,int r,int rt){  //求区间[a,b]的和(a,b的值相同时为求单点的值)  
        if(a<=l&&r<=b){ //如果全包含,直接取区间的和  
            return stree[rt].sum;  
        }  
        int mid = (r+l)>>1;  
        int ret=0;  
        if(a<=mid) ret+=querysum(a,b,lson);  
        if(mid<b) ret+=querysum(a,b,rson);  
        return ret;  
    }  
    void uppoint(int a,int b,int l,int r,int rt){  //单点替换,把第a个数换成b  
        if(l==r){  
            stree[rt].Max=stree[rt].Min=stree[rt].sum=b;  
            return ;  
        }  
        int mid =(r+l)>>1;  
        if(a<=mid)uppoint(a,b,lson);  
        else uppoint(a,b,rson);  
        up(rt);  
    }  
    void upadd(int a,int b,int l,int r,int rt){  //单点增减,把第a个数增减b  
        if(l==r){  
            stree[rt].sum=stree[rt].sum+b;  
            stree[rt].Max=stree[rt].Max+b;  
            stree[rt].Min=stree[rt].Min+b;  
            return ;  
        }  
        int mid=(l+r)>>1;  
        if(a<=mid) upadd(a,b,lson);  
        else upadd(a,b,rson);  
        up(rt);  
    }  
    int main()  
    {  
        //freopen("F:\\11.txt","r",stdin);  
        int n,q;  
        while(~scanf("%d%d",&n,&q)){  
            build(1,n,1);//build(l,r,rt);  
            while(q--){  
                char op[10];  
                int a,b;  
                scanf("%s%d%d",op,&a,&b);  
                if(op[0]=='X'){//求区间[a,b]的最大值  
                    printf("%d\n",querymax(a,b,1,n,1));//querymax(int a,int b,int l,int r,int rt);  
                }  
                else if(op[0]=='N'){//求区间[a,b]的最小值  
                    printf("%d\n",querymin(a,b,1,n,1));//querymin(int a,int b,int l,int r,int rt);  
                }  
                else if(op[0]=='U'){//单点替换,把第a个数换成b  
                    uppoint(a,b,1,n,1);//uppoint(int a,int b,int l,int r,int rt);  
                }  
                else if(op[0]=='S'){//求区间[a,b]的和(a,b的值相同时为求单点的值)  
                    printf("%d\n",querysum(a,b,1,n,1));//querysum(int a,int b,int l,int r,int rt);  
                }  
                else if(op[0]=='A'){//单点增加,把第a个数增加b  
                    upadd(a,b,1,n,1);  
                }  
                else if(op[0]=='E'){//单点减少,把第a个数减少b  
                    upadd(a,-b,1,n,1);  
                }  
            }  
        }  
        return 0;  
    }  

    区间替换,区间查询:

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #define max(a,b) (a>b)?a:b
    #define min(a,b) (a>b)?b:a
    #define lson l , m , rt << 1
    #define rson m + 1 , r , rt << 1 | 1
    const int maxn = 100100;
    const int INF=0x7fffffff;
    using namespace std;
    int lazy[maxn<<2];
    int MAX[maxn<<2];
    int MIN[maxn<<2];
    int SUM[maxn<<2];
    void PushUp(int rt) { //由左孩子、右孩子向上更新父节点
        SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
        MAX[rt] = max(MAX[rt<<1],MAX[rt<<1|1]);
        MIN[rt] = min(MIN[rt<<1],MIN[rt<<1|1]);
    }
    void PushDown(int rt,int m) { //向下更新
        if (lazy[rt]) { //懒惰标记
            lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
            SUM[rt<<1] = (m - (m >> 1)) * lazy[rt];
            SUM[rt<<1|1] = ((m >> 1)) * lazy[rt];
            MAX[rt<<1]=MAX[rt<<1|1]=lazy[rt];
            MIN[rt<<1]=MIN[rt<<1|1]=lazy[rt];
            lazy[rt] = 0;
        }
    }
    //所有的l,r,rt  带入1,n,1
    void build(int l,int r,int rt) { //初始化建树
        lazy[rt] = 0;
        if (l== r) {
            SUM[rt]=MAX[rt]=MIN[rt]=0;  //初始化为0的建树
            /*scanf("%d",&SUM[rt]);  //边读入边建树的方法
              MAX[rt]=MIN[rt]=SUM[rt];
            */
            return ;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        PushUp(rt);
    }
    void update(int L,int R,int v,int l,int r,int rt) { //将L~R区间的值置为v
        //if(L>l||R>r) return;
        if (L <= l && r <= R) {
            lazy[rt] = v;
            SUM[rt] = v * (r - l + 1);
            MIN[rt] = v;
            MAX[rt] = v;
            //printf("%d %d %d %d %d\n", rt, sum[rt], c, l, r);
            return ;
        }
        PushDown(rt , r - l + 1);
        int m = (l + r) >> 1;
        if (L <= m) update(L , R , v , lson);
        if (R > m) update(L , R , v , rson);
        PushUp(rt);
    }
    int querySUM(int L,int R,int l,int r,int rt) {  //求区间L~R的和
        if (L <= l && r <= R) {
            //printf("%d\n", sum[rt]);
            return SUM[rt];
        }
        PushDown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = 0;
        if (L <= m) ret += querySUM(L , R , lson);
        if (m < R) ret += querySUM(L , R , rson);
        return ret;
    }
    int queryMIN(int L,int R,int l,int r,int rt) {  //求区间L~R的最小值
        if (L <= l && r <= R) {
            //printf("%d\n", sum[rt]);
            return MIN[rt];
        }
        PushDown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = INF;
        if (L <= m) ret = min(ret, queryMIN(L , R , lson));
        if (m < R) ret = min(ret,queryMIN(L , R , rson));
        return ret;
    }
    int queryMAX(int L,int R,int l,int r,int rt) {  //求区间L~R的最大值
        if (L <= l && r <= R) {
            //printf("%d\n", sum[rt]);
            return MAX[rt];
        }
        PushDown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = -INF;
        if (L <= m) ret = max(ret, queryMAX(L , R , lson));
        if (m < R) ret = max(ret,queryMAX(L , R , rson));
        return ret;
    }
    int main() {
        int  n , m;
        char str[5];
        while(scanf("%d%d",&n,&m)) {
            build(1 , n , 1);
            while (m--) {
                scanf("%s",str);
                int a , b , c;
                if(str[0]=='T') {
                    scanf("%d%d%d",&a,&b,&c);
                    update(a , b , c , 1 , n , 1);
                } else if(str[0]=='Q') {
                    scanf("%d%d",&a,&b);
                    cout<<querySUM(a,b,1,n,1)<<endl;
                } else if(str[0]=='A') {
                    scanf("%d%d",&a,&b);
                    cout<<queryMAX(a,b,1,n,1)<<endl;
                } else if(str[0]=='I') {
                    scanf("%d%d",&a,&b);
                    cout<<queryMIN(a,b,1,n,1)<<endl;
                }
            }
        }
        return 0;
    }

    区间增加,区间查询:

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #define max(a,b) (a>b)?a:b
    #define min(a,b) (a>b)?b:a
    #define lson l , m , rt << 1
    #define rson m + 1 , r , rt << 1 | 1
    const int maxn = 100100;
    const int INF=0x7fffffff;
    using namespace std;
    int lazy[maxn<<2];
    int SUM[maxn<<2],MAX[maxn<<2],MIN[maxn<<2];
    void putup(int rt) {
        SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
        MAX[rt] =max(MAX[rt<<1],MAX[rt<<1|1]) ;
        MIN[rt] =min(MIN[rt<<1],MIN[rt<<1|1]);
    }
    void putdown(int rt,int m) {
        if (lazy[rt]) {
            lazy[rt<<1] += lazy[rt];
            lazy[rt<<1|1] += lazy[rt];
            SUM[rt<<1] += lazy[rt] * (m - (m >> 1));
            SUM[rt<<1|1] += lazy[rt] * (m >> 1);
            MAX[rt<<1]+=lazy[rt];
            MAX[rt<<1|1] +=lazy[rt];
            MIN[rt<<1]+=lazy[rt];
            MIN[rt<<1|1]+=lazy[rt];
            lazy[rt] = 0;
        }
    }
    //以下的 l,r,rt 都带入 1,n,1
    void build(int l,int r,int rt) {  //初始化建树
        lazy[rt] = 0;
        if (l == r) {
            //初始化树为0的写法
            SUM[rt]=MAX[rt]=MIN[rt]=0;
            /*  //边读入边建树的写法
            scanf("%d",&SUM[rt]);
            MAX[rt]=MIN[rt]=SUM[rt];
            */
            return ;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        putup(rt);
    }
    void update(int L,int R,int v,int l,int r,int rt) {  //将区间L~R的值增加v
        if (L <= l && r <= R) {
            lazy[rt] += v;
            SUM[rt] += v * (r - l + 1);
            MAX[rt]+=v;
            MIN[rt]+=v;
            return ;
        }
        putdown(rt , r - l + 1);
        int m = (l + r) >> 1;
        if (L <= m) update(L , R , v , lson);
        if (m < R) update(L , R , v , rson);
        putup(rt);
    }
    int querySUM(int L,int R,int l,int r,int rt) {  //求区间L~R的和
        if (L <= l && r <= R) {
            return SUM[rt];
        }
        putdown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = 0;
        if (L <= m) ret += querySUM(L , R , lson);
        if (m < R) ret += querySUM(L , R , rson);
        return ret;
    }
    int queryMAX(int L,int R,int l,int r,int rt) {  //求区间L~R的最大值
        if (L <= l && r <= R) {
            return MAX[rt];
        }
        putdown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = -INF;
        if (L <= m) ret =max(ret,queryMAX(L , R , lson)) ;
        if (m < R) ret =max(ret,queryMAX(L , R , rson)) ;
        return ret;
    }
    int queryMIN(int L,int R,int l,int r,int rt) {  //求区间L~R的最小值
        if (L <= l && r <= R) {
            return MIN[rt];
        }
        putdown(rt , r - l + 1);
        int m = (l + r) >> 1;
        int ret = INF;
        if (L <= m) ret = min(ret,queryMIN(L , R , lson));
        if (m < R) ret = min(ret,queryMIN(L , R , rson));
        return ret;
    }
    int main() {
        int n , m;
        int a , b , c;
        char str[5];
        scanf("%d%d",&n,&m);
        build(1 , n , 1);
        while (m--) {
            scanf("%s",str);
            if (str[0] == 'S') {
                scanf("%d%d",&a,&b);
                printf("%d\n",querySUM(a , b , 1 , n , 1));
            } else if(str[0]=='C') {
                scanf("%d%d%d",&a,&b,&c);
                update(a , b , c , 1 , n , 1);
            } else if(str[0]=='A') {
                scanf("%d%d",&a,&b);
                printf("%d\n",queryMAX(a , b , 1 , n , 1));
            } else if(str[0]=='I') {
                scanf("%d%d",&a,&b);
                printf("%d\n",queryMIN(a , b , 1 , n , 1));
            }
        }
        return 0;
    }
    
    
    

    1.zkw线段树:

    代码简单,效率高,区间修改较难,建议用普通线段树

    单点操作,区间查询:

    #include <iostream>
    #include <stdio.h>
    #include <string>
    using namespace std;
    const int N=50005;
    int n,M,q;
    int d[N*4];
    void build(int n)
    {
        for(M=1;M<n;M<<=1);
        for(int i=M+1;i<=M+n;i++)
            scanf("%d",&d[i]);
        for(int i=M-1;i;i--)
            d[i]=d[i<<1]+d[i<<1|1];
            //d[i]=max(d[i<<1],d[i<<1|1]);   求最值
    }
    void update_add(int x,int y)
    {
        d[x+=M]+=y;
        x>>=1;
        for(;x;x>>=1)
            d[x]=d[x<<1]+d[x<<1|1];
    }
    void update_sub(int x,int y)
    {
        d[x+=M]-=y;
        x>>=1;
        for(;x;x>>=1)
            d[x]=d[x<<1]+d[x<<1|1];
    }
    void update_change(int x,int y)
    {
        d[x+=M]=y;
        for(x>>=1;x;x>>=1)
            d[x]=max(d[x<<1],d[x<<1|1]);
    }
    int query_max(int s,int t)
    {
        int ans=-1;
        for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1)
        {
            if(~s&1)
                ans=max(ans,d[s^1]);
            if(t&1)
                ans=max(ans,d[t^1]);
        }
        return ans;
    }
    int query_sum(int s,int t)
    {
        int ans=0;
        for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1)
        {
            if(~s&1)
                ans+=d[s^1];
            if(t&1)
                ans+=d[t^1];
        }
        return ans;
    }
    int main()
    {
        int a,b;
        string str;
        cin>>n;
        build(n);
        while(cin>>str)
        {
            if(str=="End")
                break;
            if(str=="Query")
            {
                cin>>a>>b;
                cout<<query(a,b)<<endl;
            }
            if(str=="Add")
            {
                cin>>a>>b;
                update_add(a,b);
            }
            if(str=="Sub")
            {
                cin>>a>>b;
                update_sub(a,b);
            }
        }
        return 0;
    }

    3.主席树

    每个结点都是一棵线段树,维护[1~i]的前缀信息,各操作均为O(logn)
    特点:查询区间第K大;将当前版本返回之前某版本;在之前某版本上区间查询
    https://blog.csdn.net/creatorx/article/details/75446472
    https://blog.csdn.net/CillyB/article/details/75912440

    用主席树求区间第K大问题,包含离散化:

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn = 1e5 + 10;
    int n, m;
    int cnt;
    struct node{
        int L, R;//分别指向左右子树
        int sum;//该节点所管辖区间范围内数的个数
        node(){
            sum = 0;
        }
    }Tree[maxn * 20];
    struct value{
        int x;//值的大小
        int id;//离散之前在原数组中的位置
    }Value[maxn];
    bool cmp(value v1, value v2)
    {
        return v1.x < v2.x;
    }
    int root[maxn];//多颗线段树的根节点
    int rank[maxn];//原数组离散之后的数组
    void init()
    {
        cnt = 1;
        root[0] = 0;
        Tree[0].L = Tree[0].R = Tree[0].sum = 0;
    }
    void update(int num, int &rt, int l, int r)
    {
        Tree[cnt++] = Tree[rt];
        rt = cnt - 1;
        Tree[rt].sum++;
        if(l == r) return;
        int mid = (l + r)>>1;
        if(num <= mid) update(num, Tree[rt].L, l, mid);
        else update(num, Tree[rt].R, mid + 1, r);
    }
    int query(int i, int j, int k, int l, int r)    //查询第K小的数
    {
        int d = Tree[Tree[j].L].sum - Tree[Tree[i].L].sum;
        if(l == r) return l;
        int mid = (l + r)>>1;
        if(k <= d) return query(Tree[i].L, Tree[j].L, k, l, mid);
        else return query(Tree[i].R, Tree[j].R, k - d, mid + 1, r);
    }
    
    int query_lessKNum(int i,int j,int k,int l,int r)    //查询小于等于k的数有几个
    {
        if(l==r) return Tree[j].sum - Tree[i].sum;
        int mid=(l+r)>>1;
        int res=0;
        if(k<=mid) res+=query_lessKNum(Tree[i].L,Tree[j].L,k,l,mid);
        else
        {
            res+=Tree[Tree[j].L].sum-Tree[Tree[i].L].sum;
            res+=query_lessKNum(Tree[i].R,Tree[j].R,k,mid+1,r);
        }
        return res;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &Value[i].x);
            Value[i].id = i;
        }
        //进行离散化
        sort(Value + 1, Value + n + 1, cmp);
        for(int i = 1; i <= n; i++)
        {
            rank[Value[i].id] = i;
        }
        init();
        for(int i = 1; i <= n; i++)
        {
            root[i] = root[i - 1];
            update(rank[i], root[i], 1, n);
        }
        int left, right, k;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &left, &right, &k);
            printf("%d\n", Value[query(root[left - 1], root[right], k, 1, n)].x);
        }
        return 0;
    }

    十三.平衡树:

    用于动态维护数据,可求特定值的排名,特定排名的值,某值的前驱,某值的后继

    1.Splay树

    常用方法
    splay主要可以用来解决区间的维护问题
      假设我们需要维护一个数列,支持
      1.在数列第i位后插入一个长为l的数列
      2.在数列第i为后删除一个长为l的数列 
      3.将数列的l r区间翻转(1 2 3 2 3 翻转后为 3 2 3 2 1)
      4.将数列的l r区间同时加上一个值
      5.将数列的l r区间同时改为一个值
      6.求数列的l r区间的和(最大值)
      其实线段树上的大部分操作这里都支持,比如区间最大子区间和

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    #define MAXN 1000000
    int ch[MAXN][2],f[MAXN],size[MAXN],cnt[MAXN],key[MAXN];
    int sz,root;
    inline void clear(int x){            //初始化
        ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;
    }
    inline bool get(int x){             // 判断当前点是它父结点的左儿子还是右儿子
        return ch[f[x]][1]==x;
    }
    inline void update(int x){         // 更新当前点的size值(用于发生修改之后)
        if (x){
            size[x]=cnt[x];
            if (ch[x][0]) size[x]+=size[ch[x][0]];
            if (ch[x][1]) size[x]+=size[ch[x][1]];
        }
    }
    inline void rotate(int x){                   //旋转,保持平衡
        int old=f[x],oldf=f[old],whichx=get(x);
        ch[old][whichx]=ch[x][whichx^1]; f[ch[old][whichx]]=old;
        ch[x][whichx^1]=old; f[old]=x;
        f[x]=oldf;
        if (oldf)
            ch[oldf][ch[oldf][1]==old]=x;
        update(old); update(x);
    }
    inline void splay(int x){                   //伸展,保持平衡
        for (int fa;fa=f[x];rotate(x))
          if (f[fa])
            rotate((get(x)==get(fa))?fa:x);
        root=x;
    }
    inline void insert(int x){           //插入
        if (root==0){sz++; ch[sz][0]=ch[sz][1]=f[sz]=0; root=sz; size[sz]=cnt[sz]=1; key[sz]=x; return;}
        int now=root,fa=0;
        while(1){
            if (x==key[now]){
                cnt[now]++; update(now); update(fa); splay(now); break;
            }
            fa=now;
            now=ch[now][key[now]<x];
            if (now==0){
                sz++;
                ch[sz][0]=ch[sz][1]=0;
                f[sz]=fa;
                size[sz]=cnt[sz]=1;
                ch[fa][key[fa]<x]=sz;
                key[sz]=x;
                update(fa);
                splay(sz);
                break;
            }
        }
    }
    inline int find(int x){               //查询x点的排名
        int now=root,ans=0;
        while(1){
            if (x<key[now])
              now=ch[now][0];
            else{
                ans+=(ch[now][0]?size[ch[now][0]]:0);
                if (x==key[now]){
                    splay(now); return ans+1;
                }
                ans+=cnt[now];
                now=ch[now][1];
            }
        }
    }
    inline int findx(int x){              //查询排名为x的结点
        int now=root;
        while(1){
            if (ch[now][0]&&x<=size[ch[now][0]])
              now=ch[now][0];
            else{
                int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];
                if (x<=temp) return key[now];
                x-=temp; now=ch[now][1];
            }
        }
    }
    inline int pre(){                //求前驱
        int now=ch[root][0];
        while (ch[now][1]) now=ch[now][1];
        return now;
    }
    inline int next(){                //求后继
        int now=ch[root][1];
        while (ch[now][0]) now=ch[now][0];
        return now;
    }
    inline void del(int x){           //删除
        int whatever=find(x);
        if (cnt[root]>1){cnt[root]--; update(root); return;}
        if (!ch[root][0]&&!ch[root][1]) {clear(root); root=0; return;}
        if (!ch[root][0]){
            int oldroot=root; root=ch[root][1]; f[root]=0; clear(oldroot); return;
        }
        else if (!ch[root][1]){
            int oldroot=root; root=ch[root][0]; f[root]=0; clear(oldroot); return;
        }
        int leftbig=pre(),oldroot=root;
        splay(leftbig);
        ch[root][1]=ch[oldroot][1];
        f[ch[oldroot][1]]=root;
        clear(oldroot);
        update(root);
    }
    int main(){
        int n,opt,x;
        scanf("%d",&n);
        for (int i=1;i<=n;++i){
            scanf("%d%d",&opt,&x);
            switch(opt){
                case 1: insert(x); break;
                case 2: del(x); break;
                case 3: printf("%d\n",find(x)); break;
                case 4: printf("%d\n",findx(x)); break;
                case 5: insert(x); printf("%d\n",key[pre()]); del(x); break;
                case 6: insert(x); printf("%d\n",key[next()]); del(x); break;
            }
        }
    }

    2.Treap树堆

    较常用的平衡树,综合性能优秀

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    struct TREAP{
        int l,r,val,sz,recy,rd;
        //sz表示树的节点数,recy记录自己被重复了几次
        //rd表示该节点的优先级
    }t[1000000];
    int m,size,root,ans;
    void update(int k){
        t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].recy;
        //更新维护
    }
    void left_rotate(int &k){
        int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
        t[y].sz=t[k].sz;update(k);k=y;
        //左旋,至于这里的k=y,由于下面的递归调用,
        //它会一直迭代,所以无需担心会有什么错误
    }
    void right_rotate(int &k){
        int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
        t[y].sz=t[k].sz;update(k);k=y;
        //右旋
    }
    //以下函数的调用中(int k)表示在根为k的子树中
    void insert(int &k,int x){//插入操作
        if (k==0){//无节点时特判,
                  //或是递归的边界,即插入叶节点
            ++size;k=size;t[k].sz=t[k].recy=1;
            t[k].val=x;t[k].rd=rand();return ;
              //rand()生成随机的优先级,保证了期望复杂度
        }
        ++t[k].sz;//每次向下找同时增加该节点1个节点数
        if (t[k].val==x) ++t[k].recy;
                  //如果是相同数字,只需++recy即可
        else if (x>t[k].val){
            insert(t[k].r,x);
            if (t[t[k].r].rd<t[k].rd) left_rotate(k);
                  //插入后如果违反堆性质,就进行上浮
        }else{
            insert(t[k].l,x);
            if (t[t[k].l].rd<t[k].rd) right_rotate(k);
        }
    }
    void del(int &k,int x){
        if (k==0) return ;//无节点就跳出
        if (t[k].val==x){
            if (t[k].recy>1){
                --t[k].recy;--t[k].sz;return ;
                //如果重复了,只需--recy即可
            }
            if (t[k].l*t[k].r==0) k=t[k].l+t[k].r;
                            //如果左右儿子有为空的情况
                //或将其变为其儿子节点,或将其删除
            else if (t[t[k].l].rd<t[t[k].r].rd)
                        right_rotate(k),del(k,x);
                            //如果其左右儿子都有,选择优先级较大的,
                //保持以后的堆性质,同时将k节点下沉
                   else left_rotate(k),del(k,x);
        }
        else if (x>t[k].val)
                    --t[k].sz,del(t[k].r,x);
                //如果关键值不同,继续向下找
               else --t[k].sz,del(t[k].l,x);
    }
    int atrank(int k,int x){//寻找值为x的数的排名
        if (k==0) return 0;
        if (t[k].val==x) return t[t[k].l].sz+1;
            //如果找的关键字,根据BST的性质,
            //则其排名为左子树的大小+1
        else if (x>t[k].val)
                return t[t[k].l].sz+t[k].recy+atrank(t[k].r,x);
            //加上前面所有比它小的数,在右子树中找
           else return atrank(t[k].l,x);
            //如果在左子树中找的话就不用加了
    }
    int rerank(int k,int x){//寻找排名为x的数值
        if (k==0) return 0;
        if (x<=t[t[k].l].sz) return rerank(t[k].l,x);
            //如果x小于了左子树的大小,那解一定在左子树中
        else if (x>t[t[k].l].sz+t[k].recy)
                return rerank(t[k].r,x-t[k].recy-t[t[k].l].sz);
            //如果x大于的左子树的大小+k的重复次数,
            //那就在右子树中找
           else return t[k].val;
            //否则就是找到解了(包含了重复数字中)
    }
    void pred(int k,int x){//找前缀
        if (k==0) return ;
        if (t[k].val<x){
            ans=k;pred(t[k].r,x);
            //找到了更优的解,就替换之
            //而且在其右子树中不可能再有更优的了
            //故向其左子树中找
        }else pred(t[k].l,x);
            //否则就往右子树中找
    }
    void succ(int k,int x){//找后缀
        if (k==0) return ;
        if (t[k].val>x){
            ans=k;succ(t[k].l,x);
        }else succ(t[k].r,x);
    }
    int main(){
        int f,x;
        scanf("%d",&m);
        for (int i=1;i<=m;++i){
            scanf("%d%d",&f,&x);ans=0;
            if (f==1) insert(root,x);
            if (f==2) del(root,x);
            if (f==3) printf("%d\n",atrank(root,x));
            if (f==4) printf("%d\n",rerank(root,x));
            if (f==5) {pred(root,x);printf("%d\n",t[ans].val);}
            if (f==6) {succ(root,x);printf("%d\n",t[ans].val);}
        }
        return 0;
    }

    3.替罪羊树(重量平衡树)

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #define inf (1<<30)
    #define maxn (2100000)
    #define db double
    #define il inline
    #define RG register
    using namespace std;
    il int gi(){
      RG int x=0,q=1; RG char ch=getchar();
      while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
      if( ch=='-' ) q=-1,ch=getchar();
      while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
      return q*x;
    }
    const db al=0.75;
    struct node{ int son[2],fa,size,num; }t[maxn];
    int n,cnt,root;
    il bool balance(RG int id){  //平衡限制,这里的 alpha 取0.75
      return (db)t[id].size*al>=(db)t[ t[id].son[0] ].size
        && (db) t[id].size*al>=(db)t[t[ id].son[1] ].size;
    }
    int cur[maxn],sum;
    il void recycle(RG int id){   //压扁成一个序列,按大小顺序回收节点
      if(t[id].son[0]) recycle(t[id].son[0]);
      cur[++sum]=id;
      if(t[id].son[1]) recycle(t[id].son[1]);
    }
    il int build(RG int l,RG int r){  //递归建树
      if(l>r) return 0;
      RG int mid=(l+r)>>1,id=cur[mid];
      t[ t[id].son[0]=build(l,mid-1) ].fa=id;
      t[ t[id].son[1]=build(mid+1,r) ].fa=id;
      t[id].size=t[ t[id].son[0] ].size+t[ t[id].son[1] ].size+1;
      return id;
    }
    il void rebuild(RG int id){  //重构
      sum=0; recycle(id);
      RG int fa=t[id].fa,Son=( t[ t[id].fa ].son[1]==id );
      RG int cur=build(1,sum);
      t[ t[fa].son[Son]=cur ].fa=fa;
      if(id==root) root=cur;
    }
    il void insert(RG int x){
      RG int now=root,cur=++cnt;
      t[cur].size=1,t[cur].num=x;
      while(1){  //插入维护序列,左小右大
        t[now].size++;
        RG bool Son=(x>=t[now].num);
        if( t[now].son[Son] ) now=t[now].son[Son];
        else{
          t[ t[now].son[Son]=cur ].fa=now;
          break;
        }
      }
      RG int flag=0;
      for(RG int i=cur;i;i=t[i].fa) if(!balance(i)) flag=i;
      if(flag) rebuild(flag); //插入往往会导致不平衡,这时只需要重建不平衡的子树即可
    }
    il int get_num(RG int x){  //查询 x 在树中的节点编号
      RG int now=root;
      while(1){
        if(t[now].num==x) return now;
        else now=t[now].son[ t[now].num<x ];
      }
    }
    il void erase(RG int id){  //删除
      if(t[id].son[0] && t[id].son[1]){
        RG int cur=t[id].son[0];
        while(t[cur].son[1]) cur=t[cur].son[1];
        t[id].num=t[cur].num; id=cur;
      }  //删除操作需要找到左子树的最后一个节点或右子树的第一个节点来顶替,优先找左子树
      RG int Son=(t[id].son[0]) ? t[id].son[0]:t[id].son[1];
      RG int k=( t[ t[id].fa ].son[1]==id );
      t[ t[ t[id].fa ].son[k]=Son ].fa=t[id].fa;
      for(RG int i=t[id].fa;i;i=t[i].fa) t[i].size--;
      if(id==root) root=Son;
    }
    il int get_rank(RG int x){  //查 x 的排名
      RG int now=root,ans=0;
      while(now){
        if(t[now].num<x) ans+=t[ t[now].son[0] ].size+1,now=t[now].son[1];
        else now=t[now].son[0];
      }
      return ans;
    }
    il int get_kth(RG int x){  //查树中的第 k 个数
      RG int now=root;
      while(1){
        if(t[ t[now].son[0] ].size==x-1) return now;
        else if(t[ t[now].son[0] ].size>=x) now=t[now].son[0];
        else x-=t[ t[now].son[0] ].size+1,now=t[now].son[1];
      }
      return now;
    }
    il int get_front(RG int x){  //找前驱,即左子树最后一个点
      int now=root,ans=-inf;
      while(now){
        if(t[now].num<x) ans=max(ans,t[now].num),now=t[now].son[1];
        else now=t[now].son[0];
      }
      return ans;
    }
    il int get_behind(RG int x){  //找后继,即右子树第一个点
    h RG int now=root,ans=inf;
      while(now){
        if(t[now].num>x) ans=min(ans,t[now].num),now=t[now].son[0];
        else now=t[now].son[1];
      }
      return ans;
    }
    il void init(){
      cnt=2,root=1;
      t[1].num=-inf,t[1].size=2,t[1].son[1]=2;
      t[2].num=inf,t[2].size=1,t[2].fa=1;
    }
    il void work(){
      n=gi(); RG int type,x;
      for(RG int i=1;i<=n;i++){
        type=gi(),x=gi();
        if(type==1) insert(x);
        if(type==2) erase( get_num(x) );
        if(type==3) printf("%d\n",get_rank(x));
        if(type==4) printf("%d\n",t[ get_kth(x+1) ].num);
        if(type==5) printf("%d\n",get_front(x));
        if(type==6) printf("%d\n",get_behind(x));
      }
    }
    int main(){ init(); work(); return 0; }

    十四.珂朵莉树(ODT)

    维护一种数据结构,支持:
    区间加,区间覆盖,区间求第k大,区间求x次方和(x≤1e9)(x≤1e9)。
    保证数据随机。

    #include<bits/stdc++.h>
    #define IT set<node>::iterator
    using namespace std;
    typedef long long LL;
    const int MOD7 = 1e9 + 7;
    const int MOD9 = 1e9 + 9;
    const int imax_n = 1e5 + 7;
    struct node
    {
        int l,r; //范围
        mutable LL v; //数值
        node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
        bool operator<(const node& o) const     //重载运算符
        {
            return l < o.l;
        }
    };
    
    IT split(int pos)
    {
        IT it = s.lower_bound(node(pos));   //找到首个不小于pos的set
        if (it != s.end() && it->l == pos)   //无需,直接返回
            return it;
        --it;  //否则一定在前一个区间中
        int L = it->l, R = it->r;  //【l,r】就是要分裂的区间
        LL V = it->v;  //取出值
        s.erase(it);   //删除原集合
        s.insert(node(L, pos-1, V));  //构建前半段的新结合
        return s.insert(node(pos, R, V)).first;  //构建后半段的新集合并且返回地址
    }
    void assign_val(int l, int r, LL val)
    {
        IT itl = split(l),itr = split(r+1);  //求出要被摊平区间的收尾地址
        s.erase(itl, itr);  //删除原集合
        s.insert(node(l, r, val));  //添加新集合
    }
    void add(int l, int r, LL val)            //区间加
    {
        IT itl = split(l),itr = split(r+1);
        for (; itl != itr; ++itl)
            itl->v += val;
    }
    LL rank(int l, int r, int k)                //区间第k小
    {
        vector<pair<LL, int> > vp;
        IT itl = split(l),itr = split(r+1);
        vp.clear();
        for (; itl != itr; ++itl)
            vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
        sort(vp.begin(), vp.end());
        for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
        {
            k -= it->second;
            if (k <= 0)
                return it->first;
        }
    }
    LL pown(LL a, LL b, LL mod)       //求区间幂次和
    {
        LL res = 1;
        LL ans = a % mod;
        while (b)
        {
            if (b&1)
                res = res * ans % mod;
            ans = ans * ans % mod;
            b>>=1;
        }
        return res;
    }
    
    LL sum(int l, int r, int ex, int mod)
    {
        IT itl = split(l),itr = split(r+1);
        LL res = 0;
        for (; itl != itr; ++itl)
            res = (res + (LL)(itl->r - itl->l + 1) * pown(itl->v, LL(ex), LL(mod))) % mod;
        return res;
    }
    int n, m;
    LL seed, vmax;
    LL rd()
    {
        LL ret = seed;
        seed = (seed * 7 + 13) % MOD7;
        return ret;
    }
    LL a[imax_n];
    int main()
    {
        cin>>n>>m>>seed>>vmax;
        for (int i=1; i<=n; ++i)
        {
            a[i] = (rd() % vmax) + 1;
            s.insert(node(i,i,a[i]));
        }
        s.insert(node(n+1, n+1, 0));
        int lines = 0;
        for (int i =1; i <= m; ++i)
        {
            int op = int(rd() % 4) + 1;
            int l = int(rd() % n) + 1;
            int r = int(rd() % n) + 1;
            if (l > r)
                swap(l,r);
            int x, y;
            if (op == 3)
                x = int(rd() % (r-l+1)) + 1;
            else
                x = int(rd() % vmax) +1;
            if (op == 4)
                y = int(rd() % vmax) + 1;
            if (op == 1)
                add(l, r, LL(x));
            else if (op == 2)
                assign_val(l, r, LL(x));
            else if (op == 3)
                cout<<rank(l,r,x)<<endl;
            else
                cout<<sum(l,r,x,y)<<endl;
        }
        return 0;
    }

    十五.KD-tree:

    O(sqrt(n))
    求二维空间最近点对

    inline int cmp(arr a,arr b){return a.d[D]<b.d[D]||a.d[D]==b.d[D]&&a.d[D^1]<b.d[D^1];}
    inline void up(int k,int s)
    {
      a[k].min[0]=min(a[k].min[0],a[s].min[0]);
      a[k].max[0]=max(a[k].max[0],a[s].max[0]);
      a[k].min[1]=min(a[k].min[1],a[s].min[1]);
      a[k].max[1]=max(a[k].max[1],a[s].max[1]);
    }
    int build(int l,int r,int dd)
    {
      D=dd;int mid=(l+r)>>1;
      nth_element(a+l+1,a+mid+1,a+r+1,cmp);
      a[mid].min[0]=a[mid].max[0]=a[mid].d[0];
      a[mid].min[1]=a[mid].max[1]=a[mid].d[1];
      if (l!=mid) a[mid].l=build(l,mid-1,dd^1);
      if (mid!=r) a[mid].r=build(mid+1,r,dd^1);
      if (a[mid].l) up(mid,a[mid].l);
      if (a[mid].r) up(mid,a[mid].r);
      return mid;
    }
    void insert(int k)
    {
      int p=root;D=0;
      while (1)
      {
        up(p,k);
        if (a[k].d[D]<=a[p].d[D]){if (!a[p].l) {a[p].l=k;return;} p=a[p].l;}
        else {if (!a[p].r) {a[p].r=k;return;} p=a[p].r;}
        D^=1;
      }
    }
    
    int getdis(int k)
    {
      int res=0;
      if (x<a[k].min[0]) res+=a[k].min[0]-x;
      if (x>a[k].max[0]) res+=x-a[k].max[0];
      if (y<a[k].min[1]) res+=a[k].min[1]-y;
      if (y>a[k].max[1]) res+=y-a[k].max[1];
      return res;
    }
    void ask(int k)  //查询与(x,y)最近的点(曼哈顿距离)与其的距离
    {
      int d0=abs(a[k].d[0]-x)+abs(a[k].d[1]-y);
      if (d0<ans) ans=d0;
      int dl=(a[k].l)?getdis(a[k].l):INF;
      int dr=(a[k].r)?getdis(a[k].r):INF;
      if (dl<dr){if (dl<ans) ask(a[k].l);if (dr<ans) ask(a[k].r);}
      else {if (dr<ans) ask(a[k].r);if (dl<ans) ask(a[k].l);}
    }

    十六.Trie字典树

    用于维护字符串前缀的一种树,详见字符串总结


    十七.LCT(link-cut-tree)

    LCT用来维护动态的森林,以及一些链上操作,是处理节点无序的有根树组成的森林,进行一些列操作(例如合并,剪切,翻转,更新·····)

    struct node{                                        //定义结点
        int fa,ch[2]; //父亲和左右儿子。
        bool reverse,is_root;   //区间反转标记、是否是所在Splay的根
    }T[maxn];
    int getson(int x){
        return x==T[T[x].fa].ch[1];
    }
    void pushreverse(int x){
        if(!x)return;
        swap(T[x].ch[0],T[x].ch[1]);
        T[x].reverse^=1;
    }
    void pushdown(int x){
        if(T[x].reverse){
            pushreverse(T[x].ch[0]);
            pushreverse(T[x].ch[1]);
            T[x].reverse=false;
        }
    }
    void rotate(int x){
        if(T[x].is_root)return;
        int k=getson(x),fa=T[x].fa;
        int fafa=T[fa].fa;
        pushdown(fa);pushdown(x);    //先要下传标记
        T[fa].ch[k]=T[x].ch[k^1];
        if(T[x].ch[k^1])T[T[x].ch[k^1]].fa=fa;
        T[x].ch[k^1]=fa;
        T[fa].fa=x;
        T[x].fa=fafa;
        if(!T[fa].is_root)T[fafa].ch[fa==T[fafa].ch[1]]=x;
        else T[x].is_root=true,T[fa].is_root=false;
        //update(fa);update(x);    //如果维护了信息,就要更新节点
    }
    void push(int x){
        if(!T[x].is_root)push(T[x].fa);
        pushdown(x);
    }
    void Splay(int x){
        push(x);   //在Splay到根之前,必须先传完反转标记
        for(int fa;!T[x].is_root;rotate(x)){
            if(!T[fa=T[x].fa].is_root){
                rotate((getson(x)==getson(fa))?fa:x);
            }
        }
    }
    void access(int x){                   //访问x结点,专门开辟一条x到根的路径
        int y=0;
        do{
            Splay(x);
            T[T[x].ch[1]].is_root=true;
            T[T[x].ch[1]=y].is_root=false;
            //update(x);    //如果维护了信息记得更新。
            x=T[y=x].fa;
        }while(x);
    }
    void mroot(int x){                 // 把x点变成树根
        access(x);
        Splay(x);
        pushreverse(x);
    }
    void link(int u,int v){               // 连接两棵LCT
        mroot(u);
        T[u].fa=v;
    }
    void cut(int u,int v)                  // 分离出两棵LCT
        mroot(u);   //先把u变成根
        access(v);Splay(v);    //连接u、v
        pushdown(v);     //先下传标记
        T[u].fa=T[v].ch[0]=0;
        //v的左孩子表示v上方相连的重链
        //update(v);  //记得维护信息
    }

    十八.序列

    1.dfs序

    按照深度优先遍历树的顺序构成的数列
    常见用法:
    1.判断一个点是否是另一个点的子节点
    2.找出一个点的第一个子节点

    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    vector<int> g[100010];
    int dfs_[200020],len;
    
    void dfs(int u,int fa)
    {
        dfs_[++len]=u;  
        int sz=g[u].size();
        for(int i=0;i<sz;i++)
        {
            if(g[u][i]!=fa)
            {
                dfs(g[u][i],u);
            }
        }
    }
    
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int from,to;
            scanf("%d%d",&from,&to);
            g[from].push_back(to);
            g[to].push_back(from);
        }
        dfs(1,0);
        for(int i=1;i<=len;i++)
        {
            printf("%d ",dfs_[i]);
        }
        printf("\n");
    }

    2.欧拉序

    从根结点出发,按dfs的顺序在绕回原点所经过所有点的顺序
    常见用法:
    1.求LCA
    2.求子树权值之和

    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    vector<int> g[40010];
    int len,a[80020];
    
    void dfs(int u,int fa)
    {
        a[++len]=u;
        int sz=g[u].size();
        for(int i=0; i<sz; i++)
        {
            if(g[u][i]!=fa)
            {
                dfs(g[u][i],u);
                a[++len]=u;
            }
        }
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,m;
            len=0;
            memset(a,0,sizeof(a));
            scanf("%d",&n);
            for(int i=1; i<=n; i++)
            {
                g[i].clear();
            }
            for(int i=1; i<=n-1; i++)
            {
                int from,to;
                scanf("%d%d",&from,&to);
                g[from].push_back(to);
                g[to].push_back(from);
            }
            dfs(1,0);
            for(int i=1;i<=len;i++)
            {
                printf("%d ",a[i]);
            }
        }
    }

    十九.树链剖分

    常用方法:
    1.在一棵树上进行路径的修改、求极值、求和
    2.通常将树剖分后变成区间问题,再用线段树处理

    const int MAXN = (100000 << 2) + 10;
    //Heavy-light Decomposition STARTS FORM HERE
    int siz[MAXN];//number of son
    int top[MAXN];//top of the heavy link
    int son[MAXN];//heavy son of the node
    int dep[MAXN];//depth of the node
    int faz[MAXN];//father of the node
    int tid[MAXN];//ID -> DFSID
    int rnk[MAXN];//DFSID -> ID
    void dfs1(int u, int father, int depth) {
        /*
         * u: 当前结点
         * father: 父亲结点
         * depth: 深度
         */
        // 更新dep、faz、siz数组
        dep[u] = depth;
        faz[u] = father;
        siz[u] = 1;
        // 遍历所有和当前结点连接的结点
        for (int i = head[u]; i; i = edg[i].next) {
            int v = edg[i].to;
            // 如果连接的结点是当前结点的父亲结点,则不处理
            if (v != faz[u]) {
                dfs1(v, u, depth + 1);
                // 收敛的时候将当前结点的siz加上子结点的siz
                siz[u] += siz[v];
                // 如果没有设置过重结点son或者子结点v的siz大于之前记录的重结点son,则进行更新
                if (son[u] == -1 || siz[v] > siz[son[u]]) {
                    son[u] = v;
                }
            }
        }
    }
    void dfs2(int u, int t) {
        /**
         * u:当前结点
         * t:起始的重结点
         */
        top[u] = t;  // 设置当前结点的起点为t
        tid[u] = cnt;  // 设置当前结点的dfs执行序号
        rnk[cnt] = u;  // 设置dfs序号对应成当前结点
        cnt++;
        // 如果当前结点没有处在重链上,则不处理
        if (son[u] == -1) {
            return;
        }
        // 将这条重链上的所有的结点都设置成起始的重结点
        dfs2(son[u], t);
        // 遍历所有和当前结点连接的结点
        for (int i = head[u]; i; i = edg[i].next) {
            int v = edg[i].to;
            // 如果连接结点不是当前结点的重子结点并且也不是u的父亲结点,则将其的top设置成自己,进一步递归
            if (v != son[u] && v != faz[u]){
                dfs2(v, v);
            }
        }
    }
    INT64 query_path(int x, int y) {
        /**
         * x:结点x
         * y:结点y
         * 查询结点x到结点y的路径和
         */
        INT64 ans = 0;
        int fx = top[x], fy = top[y];
        // 直到x和y两个结点所在链的起始结点相等才表明找到了LCA
        while (fx != fy) {
            if (dep[fx] >= dep[fy]) {
                // 已经计算了从x到其链中起始结点的路径和
                ans += query(1, tid[fx], tid[x]);
                // 将x设置成起始结点的父亲结点,走轻边,继续循环
                x = faz[fx];
            } else {
                ans += query(1, tid[fy], tid[y]);
                y = faz[fy];
            }
            fx = top[x], fy = top[y];
        }
        // 即便找到了LCA,但是前面也只是分别计算了从一开始到最终停止的位置和路径和
        // 如果两个结点不一样,表明仍然需要计算两个结点到LCA的路径和
        if (x != y) {
            if (tid[x] < tid[y]) {
                ans += query(1, tid[x], tid[y]);
            } else {
                ans += query(1, tid[y], tid[x]);
            }
        } else ans += query(1, tid[x], tid[y]);
        return ans;
    }
    void update_path(int x, int y, int z) {
        /**
         * x:结点x
         * y:结点y
         * z:需要加上的值
         * 更新结点x到结点y的值
         */
        int fx = top[x], fy = top[y];
        while(fx != fy) {
            if (dep[fx] > dep[fy]) {
                update(1, tid[fx],tid[x], z);
                x = faz[fx];
            } else {
                update(1, tid[fy], tid[y], z);
                y = faz[fy];
            }
            fx = top[x], fy = top[y];
        }
        if (x != y)
            if (tid[x] < tid[y]) update(1, tid[x], tid[y], z);
            else update(1, tid[y], tid[x], z);
        else update(1, tid[x], tid[y], z);
    }
    
    INT64 query(int i, int x, int y) {
        /**
         * 查询操作
         */
        int lc = i << 1, rc = (i << 1) + 1;
        if (x <= tree[i].left && tree[i].right <= y)
            return tree[i].val;
        if (tree[i].left > y || tree[i].right < x)
            return 0;
        if (tag[i]) pushdown(i);
        return query(lc, x, y) + query(rc, x, y);
    }

    二十.根号算法

    1.分块算法:

    O(sqrt(n))
    本质还是暴力,是一种对暴力的优化
    处理区间问题,在线询问,可在一些情况代替线段树等区间数据结构

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn=1e5+7;
    
    int block,belong[maxn],l[maxn],r[maxn];
    long long a[maxn],Max[maxn];
    int n;
    void build()             //建块,通用模板,任何题目都一样
    {
        block=sqrt(n);           //每块大小
        num=n/block; if(n%block) num++;     //分块个数
        for(int i=1;i<=num;i++)
        {
            l[i]=(i-1)/block+1;       //l[i]表示i块的左端位置
            r[i]=i*block;             //r[i]表示i块的右端位置
        }
        r[num]=n;
        for(int i=1;i<=n;i++)
            belong[i]=(i-1)/block+1;      //i属于哪一个块
    
        for(int i=1;i<=n;i++)
            for(int j=l[i];j<=r[i];j++)
                Max[i]=max(Max[i],a[j]);     //初始化,保存每块最大值,具体问题具体修改
    }
    void update(int x,int y)        //单点更新,具体问题具体修改
    {
        a[x]+=y;
        Max[belong[x]]=max(Max[belong[x],a[x]);
    }
    
    long long query(int x,int y)     //区间查询,具体问题具体修改
    {
        long long ans=0;
        if(belong[x]==belong[y])     //若x和y在同一块中,直接遍历块中全部元素求最大值
        {
            for(int i=x;i<=y;i++)
                ans=max(a[i],ans);
            return ans;
        }
        for(int i=x;i<=r[belong[x]];i++)            //查询x到所在块最右端
            ans=max(ans,a[i]);
        for(int i=belong[x]+1;i<belong[y];i++)      //查询x与y之间的完整块
            ans=max(ans,Max[i]);
        for(int i=l[belong[y];i<=y;i++)            //查询y所在块的左端到y
            ans=max(ans,a[i]);
        return ans;
    }

    2.莫队算法:

    本质仍是暴力,处理区间问题,适用于只询问不修改,可以离线查询,在已知[l,r]的情况,可以在O(1)内推出[l,r-1],[l,r+1],[l+1,r],[l-1,r]的问题

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    
    struct node
    {
        int l,r,id;
    }Q[maxn];                 //储存询问
    
    int pos[maxn];          //记录每个点所在块的编号
    long long ans[maxn];            //记录每个点的答案
    long long flag[maxn];
    int a[maxn];
    bool cmp(node a,node b)
    {
        if(pos[a.l]==pos[b.l])
            return a.r<b.r;
        return pos[a.l]<pos[b.l];
    }
    
    int n,m,k;
    int L=1,R=0,Ans=0;
    void add(int x)         //具体问题具体修改
    {
    
    }
    void del(int x)
    {
    
    }
    
    int main()
    {
        cin>>n>>m>>k;
        int sz=sqrt(n);                   //块的大小
        for(int i=1;i<=n;i++)        //读入数据
        {
            cin>>a[i];
            .................
            pos[i]=i/sz;
        }
        for(int i=1;i<=m;i++)           //读入询问
        {
            cin>>Q[i].l>>Q[i].r;
            Q[i].id=i;
        }
        sort(Q+1,Q+m+1,cmp);       //离线询问,并排序
        for(int i=1;i<=n;i++)           //莫队算法
        {
            while(L<Q[i].l)
            {
                del(L-1);
                L++;
            }
            while(L>Q[i].l)
            {
                L--;
                add(L-1);
            }
            while(R<Q[i].r)
            {
                R++;
                add(R);
            }
            while(R>Q[i].r)
            {
                del(R);
                R--;
            }
            ans[Q[i].id]=Ans;
        }
       for(int i=1;i<=m;i++)
            cout<<ans[i]<<endl;
        return 0;
    }

    二十一.CDQ分治

    https://blog.csdn.net/wu_tongtong/article/details/78785836
    通过对时间复杂度加一个log实现对问题降维,常用来代替树套树等复杂数据结构,且优于其
    适用条件:
    修改操作对查询的贡献独立,修改操作互不影响,题目允许离线算法
    解决三维偏序或四维偏序问题

    步骤:
    1.将操作序列分为两个长度相等的部分
    2.递归处理前部分子问题
    3.计算前部分子问题中的修改操作对后部分子问题的影响
    4.递归处理后部分子问题

    1.三维偏序:

    把询问重复的去掉之后开始分治
    第一维排序第二维分治第三维建树状数组然后对每个询问求前缀和就是比他小的询问的数量

    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #define rep(i,l,r) for (int i=l;i<=r;i++)
    #define down(i,l,r) for (int i=l;i>=r;i--)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define maxn 200500
    using namespace std;
    struct data
    {
        int x,y,z,ans,s;
    }a[maxn],q[maxn];
    int t[maxn],ans[maxn],n,m;
    
    bool cmp(data a,data b){
        if (a.x==b.x&&a.y==b.y) return a.z<b.z;
        else if (a.x==b.x) return a.y<b.y;
        else return a.x<b.x;
    }
    int lowbit(int x){                    //树状数组相关
        return (x&(-x));
    }
    void add(int x,int y){
        while (x<=m){
            t[x]+=y; x+=lowbit(x);
        }
    }
    int query(int x){
        int ans=0;
        while (x){
            ans+=t[x]; x-=lowbit(x);
        }
        return ans;
    }
    bool cmp2(data a,data b){
        if (a.y==b.y) return a.z<b.z;
        else return a.y<b.y;
    }
    void cdq(int l,int r){
        if (l==r) return;
        int mid=(l+r)/2;
        cdq(l,mid); cdq(mid+1,r);
        sort(q+l,q+1+mid,cmp2); sort(q+1+mid,q+r+1,cmp2);
        int l1=l,l2=mid+1;
        while (l2<=r)
        {
            while (l1<=mid&&q[l1].y<=q[l2].y)
            {
                add(q[l1].z,q[l1].s);
                l1++;
            }
            q[l2].ans+=query(q[l2].z);
            l2++;
        }
        for(int i=l;i<l1;i++)
            add(q[i].z,-q[i].s);
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i].x>>a[i].y>>a[i].z;          //读入数据
        sort(a+1,a+1+n,cmp);                      //一维排序
        int cnt=0;
        int top=0;
        for(int i=1;i<=n;i++)
        {
            cnt++;
            if (a[i].x!=a[i+1].x||a[i].y!=a[i+1].y||a[i].z!=a[i+1].z)     //删除相同项
            {
                q[++top]=a[i];
                q[top].s=cnt;
                cnt=0;
            }
        }
        cdq(1,top);
        for(int i=1;i<=top;i++)
            ans[q[i].ans+q[i].s-1]+=q[i].s;
        for(int i=0;i<n;i++)
            cout<<ans[i]<<endl;
        return 0;
    }

    2.四维偏序

    具体思想同上

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define rec(i, x, n) for(int i = x; i <= n; i++)
    const int maxn = 200005, inf = 0x3f3f3f3f;
    int n, tot, rank[maxn], tr[maxn << 2];
    struct _mat {
        int a, b, c, d, ans; // a up, b up, c down, d down
    } c[maxn], tmp[maxn];
    inline int iread() {
        int f = 1, x = 0; char ch = getchar();
        for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
        for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
        return f * x;
    }
    void pushup(int p) {
        tr[p] = std::min(tr[p << 1], tr[p << 1 | 1]);
    }
    bool cmp1(_mat x, _mat y) {return x.c > y.c;}
    bool cmp2(_mat x, _mat y) {return x.d > y.d;}
    void change(int p, int l, int r, int x, int w) {
        if(l == r && r == x) {
            tr[p] = w;
            return;
        }
        int mid = l + r >> 1;
        if(x <= mid) change(p << 1, l, mid, x, w);
        else change(p << 1 | 1, mid + 1, r, x, w);
        pushup(p);
    }
    int query(int p, int l, int r, int x, int y) {
        if(x > y) return inf;
        if(x <= l && r <= y) return tr[p];
        int mid = l + r >> 1;
        int res = inf;
        if(x <= mid)
            res = std::min(res, query(p << 1, l, mid, x, y));
        if(y > mid)
            res = std::min(res, query(p << 1 | 1, mid + 1, r, x, y));
        return res;
    }
    void cdq(int l, int r) {
        if(l == r) return;
        int mid = l + r >> 1, q1 = l, q2 = mid;
        rec(i, l, r) tmp[c[i].c <= mid ? q1++ : ++q2] = c[i];
        rec(i, l, r) c[i] = tmp[i];
        for(int i = mid + 1, j = l; i <= r; i++) {
            for(; j <= mid && c[j].d > c[i].d; j++) change(1, 1, tot, c[j].a, c[j].b);
            if(c[i].b > query(1, 1, tot, 1, c[i].a - 1)) c[i].ans = 1;
        }
        for(int i = l; i <= mid && c[i].d > c[r].d; i++) change(1, 1, tot, c[i].a, inf);
        cdq(l, mid); cdq(mid + 1, r);
    }
    int main() {
        n = iread();
        rec(i, 1, n) {
            int x1 = iread(), y1 = iread(), x2 = iread(), y2 = iread();
            c[i] = (_mat){rank[i] = x1, y1, x2, y2};
        }
        std::sort(rank + 1, rank + 1 + n);
        tot = std::unique(rank + 1, rank + 1 + n) - rank - 1;
        std::sort(c + 1, c + 1 + n, cmp1);
        rec(i, 1, n) c[i].c = i, c[i].a = std::lower_bound(rank + 1, rank + 1 + tot, c[i].a) - rank;
        std::sort(c + 1, c + 1 + n, cmp2);
        memset(tr, 0x3f, sizeof(tr));    
        cdq(1, n);
        int ans = 0;
        rec(i, 1, n) ans += c[i].ans;
        printf("%d\n", ans);
        return 0;
    }
    展开全文
  • ACM常用数据结构

    2012-02-11 12:00:55
    基本结构 高级结构 题单 集合结构   幷查集 POJ 1182 POJ 1308 POJ 1611 POJ 1986 POJ 1988 线性结构 数组 栈 队列 双端队列 POJ POJ POJ POJ...

      基本结构 高级结构 题单
    集合结构  


    幷查集


    POJ 1182

    POJ 1308

    POJ 1611

    POJ 1986

    POJ 1988

    线性结构 数组

    队列

    双端队列

    POJ

    POJ

    POJ

    POJ

    POJ

    树状结构

    二叉树

    BST

    AVL树

    splay树(伸展树)

    Treap

    Cartesian Tree

    Size Balance Tree

    POJ 3580(splay tree)

    POJ 2761(Treap)

    POJ 2201(Cartesian Tree)

    POJ 3481(SBT)

    图形结构

    邻接矩

    阵邻接表

    十字链表

    邻接多重表

     

    POJ

    POJ

    POJ

    POJ

    POJ

    堆型结构 二叉堆

    左偏堆

    斜堆

    POJ 3016(可合并堆)

    POJ 3666(可合并堆)

    POJ

    POJ

    POJ

    数学结构  


    散列表(Hash表)


    POJ 3349

    POJ 2002

    POJ

    统计结构  

    树状数组

    线段树

    POJ 2482(线段树)

    POJ 1151(线段树)

    POJ 2155(二维树状数组)

    POJ

    POJ

    字符结构  

    前缀树

    后缀树

    后缀数组


    POJ 1743

    POJ 2744

    POJ 2758

    POJ 1056(Trie树)

    POJ 2001(Trie树)

    POJ 2503(Trie树)

    POJ 3630(Trie树)


    展开全文
  • ACM-数据结构总览

    2015-07-10 18:49:48
    ACM竞赛,谈到程序中数据的组织方式,那就不得不涉及到各种数据结构,这里将一些经典的数据结构整理出来: 并查集-用树来表示集合,支持快速查找、合并,数据结构-并查集()

    ACM竞赛,谈到程序中数据的组织方式,那就不得不涉及到各种数据结构,这里将一些经典的数据结构整理如下:


    并查集-用树来表示集合,支持快速查找、合并,数据结构-并查集()

    展开全文
  • ACM模板 数据结构

    2017-01-05 20:53:23
    数据结构 acm 模板

    一、并查集

    const int maxn = 30000+5;
    int n;
    int par[maxn], rk[maxn];//par记录祖先,rk记录其在所在树中的深度
    void init()
    {
        for(int i = 0; i < n; i++)
            par[i] = i, rk[i] = 0;
    }
    
    int finda(int x)
    {
        if(par[x] == x)  return x;
        return par[x] = finda(par[x]);
    }
    
    void unite(int x, int y)
    {
        x = finda(x);
        y = finda(y);
        if(x == y) return;
    
        if(rk[x] < rk[y]) par[x] = y;
        else
        {
            par[y] = x;
            if(rk[x] == rk[y]) rk[x]++;
        }
    }

    二、树状数组

    注意树状数组中最小的数为1,不能是0,当输入数据最小值为0时,可全体加一
    树状数组初始化为0

    1.一维单点更新、区间查询

    一维单点更新、区间求和
    maxb为所用最大数字,要初始化

    int lowbit(int x) {return x&-x;}
    
    void add(int x,int val)
    {for(int i=x;i<=maxb;i+=lowbit(i)) bit[i]+=val;}
    
    int getsum(int x)
    {
        int res=0;
        for(int i=x;i>0;i-=lowbit(i)) res+=bit[i];
        return res;
    }
    
    int query(int l,int r)
    {return getsum(r)-getsum(l-1);}

    例题:
    poj 2299 Ultra-QuickSort
    poj 3321 Apple Tree
    poj 3067 Japan
    poj 3416 Crossing

    2.一维区间更新、单点查询

    此时记录每个点与前面一点的增值,则查询某 点值即为从头到这个点的增值的累和,即由getsum()得到。
    更新区间如下:

    void update(int l,int r,int val)
    {
        add(l,val);
        add(r+1,-val);
    }

    3.二维单点更新、区间查询

    二维需要用容斥原理得到待求的二维区间

    inline int lowbit(int x){return x&-x;}
    void add(int x,int y,int val)
    {
        for(int i=x;i<=maxb;i+=lowbit(i))
            for(int j=y;j<=maxb;j+=lowbit(j))
                bit[i][j]+=val;
    }
    int getsum(int x,int y)
    {
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j))
                res+=bit[i][j];
        return res;
    }
    int calc(int x1,int y1,int x2,int y2)
    {
        return getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
    }

    例题:poj1195 Mobile phones

    4.二维区间更新、单点查询

    将一维区间更新、单点查询改为二维,同样记录的是增值。如图,更新黄色区域,用容斥原理,双斜线处增加,单斜线处减少。
        1处增加后,2、3两处再减回去,到了4被减了两遍,再加回来。
    Alt text

    int lowbit(int x){return x&-x;}
    void add(int x,int y,int val)
    {
        for(int i=x;i<=maxb;i+=lowbit(i))
            for(int j=y;j<=maxb;j+=lowbit(j))
                bit[i][j]+=val;
    }
    void update(int x1,int y1,int x2,int y2,int val)
    {
        add(x1,y1,val);
        add(x1,y2+1,-val);
        add(x2+1,y1,-val);
        add(x2+1,y2+1,val);
    }
    int getsum(int x,int y)
    {
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))
            for(int j=y;j>0;j-=lowbit(j)) 
                res+=bit[i][j];
        return res;

    例题:poj 2155 Matrix

    5.[技巧]双关键字排序预处理

    例题:
    poj 2352 Stars
    poj 2481 Cows
    poj 3067 Japan
    poj 3416 Crossing

    三、线段树

    1.单点更新、区间查询

    单点更新、区间求和
    #define lson l,mid,cur<<1
    #define rson mid+1,r,cur<<1|1
    const int maxn=50000+5;
    int st[maxn<<2];//开n的4倍大小
    int n;
    
    inline void push_up(int cur)
    {st[cur]=st[cur<<1]+st[cur<<1|1];}
    
    void build(int l,int r,int cur)
    //按节点从左至右的顺序初始化
    //自顶向下,先build(1,n,1);
    {
        if(l==r)
        {
            scanf("%d",&st[cur]);
            return;
        }
        int mid=(l+r)>>1;
        build(lson);
        build(rson);
        push_up(cur);
    }
    
    void update(int p,int val,int l,int r,int cur)
    //更新p点,使其增加val,当前在节点cur,对应区间[l,r]
    //自顶向下更新,先update(p,val,1,n,1);
    {
        if(l==r)
        {
            st[cur]+=val;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) update(p,val,lson);
        else update(p,val,rson);
        push_up(cur);
    }
    
    int query(int s,int t,int l,int r,int cur)
    //要求sum(s,t),当前在代表[l,r]的点cur上
    {
        if(s<=l && r<=t) return st[cur];
        if(t<l || s>r) return 0;
        int mid=(l+r)>>1;
        return query(s,t,lson)+query(s,t,rson);
    }

    例题:hdu 1166敌兵布阵

    单点更新、区间求最值

    下为求最大值,在上面类型1的基础上需要改:

    • push_up()中做和改为用max
    • update()中st[cur]+=val中的+=改为=
    • query()中return的也用max
      如下所示:
    inline void push_up(int cur)
    {st[cur]=max(st[cur<<1],st[cur<<1|1]);}
    
    void update(int p,int val,int l,int r,int cur)
    {
        if(l==r)
        {
            st[cur]=val;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) update(p,val,lson);
        else update(p,val,rson);
        push_up(cur);
    }
    
    int query(int s,int t,int l,int r,int cur)
    {
        if(s<=l && t>=r) return st[cur];
        if(t<l || s>r) return 0;
        int mid=(l+r)>>1;
        return max(query(s,t,lson),query(s,t,rson));
    }

    例题:hdu 1754 I Hate It

    2.区间更新、区间查询

    区间更新、区间求和
    展开全文
  • ACM 数据结构入门

    2016-03-24 22:07:44
    本文总结了基础的acm所能用到的数据结构 省略了栈,队列,并查集等基础知识 RMQ 优点:编写复杂度低,不容易错。倍增的思想非常好 缺点:不支持修改操作,用处小 初级题目见课件 进阶题目推荐 HDU5289...
  • ACM数据结构知识清单

    2018-08-27 09:10:25
    数据结构 栈,队列,链表 哈希表,哈希数组 堆,优先队列 双端队列 可并堆 左偏堆 二叉查找树 Treap 伸展树 并查集 集合计数问题 二分图的识别 平衡二叉树 二叉排序树 线段树 一维线段树 二维线段...
  • ACM数据结构学习小结

    2019-05-08 22:45:31
    数据结构acm课刚开始的时候已经大体学习过。以下是数据结构的小部分内容。 栈:栈是只能在某一端插入和删除的特殊线性表。 进行删除和插入的一端称栈顶,另一堆称栈底。插入一般称为进栈(PUSH),删除则称为退栈...
  • Problem Description 已知二叉树的一个按先序...连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。 Output 每组输入数据对应输出2行: 第1行输出中序遍历序列; 第2行输出后序遍历序列。  
  • Problem Description 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B,...
  • 快要考试了,帮Kiwinnn整理一些很基础的数据结构和算法。一、pair有时需要定义含有两个元素的结构体,但是又懒得定义结构体怎么办?可以使用pair这个结构定义方式pair&lt;类型1,类型2&gt;名字,如pair&...
  • 首先,数据结构是一门计算机语言学的基础学科,它不属于任何一门语言,其体现的是几乎所有标准语言的算法的思想。  上面的概念有一些模糊,我们现在来具体说一说,相信你门的数据结构使用的是一门具体的语言比如C/...
  • ACM题集以及各种总结大全! 虽然退役了,但是整理一下,供小弟小妹们以后切题方便一些,但由于近来考试太多,顾退役总结延迟一段时间再写!先写一下各种分类和题集,欢迎各位大牛路过指正。 一.ACM入门 关于ACM ...
  • 各种专题大全,精心整理,发上来供大家专题训练使用!
  • 数据结构实验之链表一:顺序建立链表Time Limit: 1000 ms Memory Limit: 65536 KiBSubmit StatisticProblem Description输入N个整数,按照输入的顺序建立单链表存储,并遍历所建立的单链表,输出这些数据。...
  • 前言:技术书阅读方法论 一.速读一遍(最好在1~2天内完成) 人的大脑记忆力有限,在一天内快速看完一本书会在大脑里留下深刻印象,对于之后复习以及总结都会有特别好的作用。 对于每一章的知识,先阅读标题,弄懂...
  • ACM必练50题

    2017-05-12 15:25:33
    POJ推荐50题 1. 标记“难”和“稍难”的题目可以看看,思考一下,不做要求,当然有能力的同学可以直接切掉。 2. 标记为 A and B 的题目是...4. 这里不少题目在 BUPT ACM FTP 上面都有代码,请大家合理利
  • 当前农村公路建设正如火如荼的展开,某乡镇政府决定实现村村通公路,工程师现有各个村落之间的原始道路统计数据表,表中列出了各村之间可以建设公路的若干条道路的成本,你的任务是根据给出的数据表,求使得每个村都...
  • 平衡树是二叉搜索树和堆合并构成的新数据结构,所以它的名字取了Tree和Heap各一半,叫做Treap。 堆和树的性质是冲突的,二叉搜索树满足左子树<根节点<右子树,而堆是满足根节点小于等于(或大于等于)左右儿子。因此...
  • acm常用高级数据结构

    2020-05-17 10:41:56
    acm常用高级数据结构,以及一些源码 二分法与统计问题
1 2 3 4 5 ... 20
收藏数 37,557
精华内容 15,022