ACM►老Blog迁移►stencil►data_struct

区间翻转0-1+区间赋值0-1+区间求和的双标记动态开点线段树

转移自老blog

线段树

/* http://acm.cug.edu.cn/problem.php?cid=1176&pid=1 */
// 区间赋值为0/1,区间的值取反
//线段树动态开点

//  区间翻转0/1+区间赋值0/1+区间求和的双标记动态开点线段树.html

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=5e4+5;
int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot;

void push_son(int&son,int l,int r,int covrt,int revrt){
    if(son==0) {
        son=++tot;
        cov[son]=-1;
        rev[son]=0;
        sum[son]=0;
        ls[son]=0;
        rs[son]=0;
    }
    if(covrt!=-1){
        sum[son]=(r-l+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=(r-l+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml,cov[rt],rev[rt]);
    push_son(rs[rt],mr,r,cov[rt],rev[rt]);
    cov[rt]=-1; rev[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}

void build(int&rt,int l,int r){
    rt=tot=0;
    push_son(rt,l,r,-1,0);
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        push_down(rt,l,r);
        int ret=0;
        if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr);
        if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr);
        return ret;
    }
}

离散化方法线段树

/*

3 6 
1 1 1 
1 1 4
1 2 2 
1 2 4 
1 3 3 
1 3 4


*/




#include<bits/stdc++.h>
using namespace std;

vector<int>disc;
int getid(int x){
    return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}

//hdu 4578
#define ls (rt<<1)
#define rs (ls|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=55555*6;
int rev[maxn<<2],cov[maxn<<2],sum[maxn<<2],a[maxn];

void push_son(int son,int l,int r,int covrt,int revrt){
    if(covrt!=-1){
        sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=((disc[r-1+1]-1)-disc[l-1]+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls,l,ml,cov[rt],rev[rt]);
    push_son(rs,mr,r,cov[rt],rev[rt]);
    cov[rt]=-1; rev[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls]+sum[rs];
}

void build(int rt,int l,int r){
    cov[rt]=-1;
    rev[rt]=0;
    if(l==r){
        sum[rt]=0;
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
    }
    else{
        if(ml>=ql) update(ls,l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs,mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr){
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        int ret=0;
        if(ml>=ql) ret+=query(ls,l,ml,ql,qr);
        if(mr<=qr) ret+=query(rs,mr,r,ql,qr);
        return ret;
    }
}

int read(){
    int ret=0,fu=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') fu=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9') {
        ret=(ret<<1)+(ret<<3)+(ch^48);
        ch=getchar();
    }
    return ret*fu;
}


int L[maxn],R[maxn],OP[maxn];

int main(){
    int n=read();
    int q=read();
    for(int i=0;i<q;i++) {
        L[i]=read();
        R[i]=read();
        OP[i]=read();
        disc.push_back(L[i]);
        disc.push_back(R[i]);
        disc.push_back(L[i]+1);
        disc.push_back(R[i]+1);
        disc.push_back(L[i]-1);
        disc.push_back(R[i]-1);
    }
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());

    build(1,1,disc.size());
    for(int i=0;i<q;i++){
        int l=getid(L[i]);
        int r=getid(R[i]);
        int op=OP[i];
        if(op==1) update(1,1,disc.size(),l,r,0,2);
        if(op==2) update(1,1,disc.size(),l,r,1,2);
        if(op==3) update(1,1,disc.size(),l,r,1,1);
        if(op==4) printf("%d\n",query(1,1,disc.size(),l,r));
    }
}
ACM►老Blog迁移►stencil►data_struct

吉司机线段树

转移自老blog

吉司机线段树

hdu5306

#define ml ((l+r)>>1)
#define mr (ml+1)
#define ls (rt<<1)
#define rs (ls|1)
int mx1[maxn<<2],num[maxn<<2],mx2[maxn<<2],lz[maxn<<2],a[maxn];
long long sum[maxn<<2];

void push_son(int son,int l,int r,int lzrt){//把最大值变为lzrt ，次大值不变
    if(lzrt<mx1[son]){
        sum[son]-=1ll*(mx1[son]-lzrt)*num[son];
        mx1[son]=lzrt;
        lz[son]=lzrt;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls,l,ml,lz[rt]);
    push_son(rs,mr,r,lz[rt]);
    lz[rt]=0x7fffffff;
}

void push_up(int rt,int l,int r){
    if(mx1[ls]==mx1[rs]){
        mx1[rt]=mx1[ls];
        num[rt]=num[ls]+num[rs];
        mx2[rt]=max(mx2[ls],mx2[rs]);
    }
    else{
        if(mx1[ls]>mx1[rs]){
            mx1[rt]=mx1[ls];
            num[rt]=num[ls];
            mx2[rt]=max(mx2[ls],mx1[rs]);
        }
        else{
            mx1[rt]=mx1[rs];
            num[rt]=num[rs];
            mx2[rt]=max(mx2[rs],mx1[ls]);
        }
    }
    sum[rt]=sum[ls]+sum[rs];
}

void build(int rt,int l,int r){
    lz[rt]=0x7fffffff;
    if(l==r){
        mx1[rt]=a[l];
        num[rt]=1;
        mx2[rt]=-1;// none 
        sum[rt]=a[l];
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update(int rt,int l,int r,int ql,int qr,int val){
    if(mx1[rt]<=val) return ;//无影响
    if(ql<=l&&r<=qr&&mx2[rt]<val){//只影响最大值，不影响次大值
        push_son(rt,l,r,val);
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql)update(ls,l,ml,ql,qr,val);
        if(mr<=qr)update(rs,mr,r,ql,qr,val);
        push_up(rt,l,r);
    }
}

long long query_sum(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        push_down(rt,l,r);
        long long ret=0;
        if(ml>=ql) ret+=query_sum(ls,l,ml,ql,qr);
        if(mr<=qr) ret+=query_sum(rs,mr,r,ql,qr);
        return ret;
    }
}

int query_max(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return mx1[rt];
    }
    else{
        push_down(rt,l,r);
        int ret=0;
        if(ml>=ql) ret=max(ret,query_max(ls,l,ml,ql,qr));
        if(mr<=qr) ret=max(ret,query_max(rs,mr,r,ql,qr));
        return ret;
    }
}
ACM►老Blog迁移►stencil►data_struct

树状数组

转移自老blog

一维树状数组

笔者眼中的一维树状数组

        一维树状数组，是一棵左偏树，他的每一个节点，维护的是一段区间的和,若该节点的 下标为i，那么他维护的区间就是(i&(i-1),i] ，熟悉位运算的人应该都知道，i&(i-1)与i的关系：i&(i-1)和i去掉i的二进制中的最低位的1后的值 相等。并且，树状数组就是做单点修改，前缀区间查询的数据结构。 为了利 于描述，下文暂时称一维树状数组为树状数组

树状数组询问操作

        原数组的前缀区间查询，根据定义，我们很容易知道，区间[1,x] 一定能够被树状数组的某些节点所表示的区间 并来表达，且唯一表达，且表达式最多lg(x)项，因为x的二进制中最多lg个1。于是任意前缀区间就能够在树状数组中查询得到。

树状数组更新操作

        原数组的点修改，我们必须找到所有包含了该点的树状数组节点，若要修改的点的下标为i，根据定义我们解不等式 (x&(x-1))+1<=i<=x,可以证明可以证明如果a是一个解，且存在另一个大于a的最小的解b，则b=a+a&-a。于是我们根据此操作 一步一步去更新树状数组节点即可，此节点数目lg级别

树状数组的用途

        根据定义，我们可以很容易的维护很多关于单点修改，前缀区间查询的操作，比如前缀最值、 前缀区间和。

区间加法与区间减法

        如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,b-1)和f(b,c)算出 f(a,c)，则此运算满足区间加法
        如果对于作用于区间[x,y]上的区间运算f(x,y)满足 若对于所有的a<b<=c可以根据f(a,c)和f(b,c)算出 f(a,b-1)，则此运算满足区间减法

让用途更广

        对于所有满足区间减法的操作，比如说:区间和，区间异或和。我们可以根据前缀区间 相减，得到任意区间的区间和与区间异或和。

差分操作

        如果我们要对一个区间进行修改，我们有这样一种做法，在区间起点加一个标记，在区间末尾 再加一个标记，于是我们就表面修改了此数组的一个区间,查询的话，查前缀和就可以了，由于本文重点不在此，简要 举个例子，对于一个数组，我们如果说要经常修改某些区间的值:整个区间的所有元素加上一个d，我们可以考虑这样做，让区间起点+d,区间末尾右边的元素-d, 当修改完之后，我们对此数组做一遍前缀和就能得到修改结果。我们称表面修改的数组为差分数组，差分数组的前缀和就是我们要的原数组。

再广一点

        考虑一个维护区间和的数组，如果要对随机区间修改，对单点查询怎么办呢？我们维护此数组 的差分数组，原数组的区间修改就是差分数组的点修改，原数组的点查询就是差分数组的前缀区间查询，于是我们解决了这个问题

还能更加广

        如果我们不仅仅满足与点查询，我们还要前缀和区间查询，也能办到，再来理一下，原数组的前缀 和区间查询等于差分数组的二阶前缀和区间查询，我们假定a为差分数组：
\sum_{i=1}^{N}\sum_{j=1}^{i} a_{j}=\sum_{j=1}^{N} (N+1-j)a_{j} =(N+1)\sum_{j=1}^{N} a_{j}-\sum_{j=1}^{N} ja_{j}
这里很明显了，我们维护一个原数组的差分数组ai和另一个数组i*ai的点修改区间查询即可。

二维树状数组

提升纬度

        我们定义,在二维数据结构中，让点(x,y)维护点(x&(x-1)+1,y&(y-1)+1)到(x,y)的矩阵的区间信息，根据 之前的推导，使用类似的方法，可以得出在每一维上最多lg个节点，故两维一起最多lg*lg个节点。类似的也可以得出更新的时候，节点依旧是lg*lg个。

二维的差分和任意区间维护此处不做细分析

        如果我们维护了二维前缀区间定义前缀区间为:(1,1)到(x,y) 的矩形区间。的信息，根据容斥原理，任意区间很容易算出来了，差分是一样的。

二维的区间修改，区间和查询

        一样的，是差分数组的二阶前缀和，化简公式如下:

于是我们维护四个普通树状数组即可 
struct Binary_Indexed_Tree{
    //点更新区间查询,最大可用范围[1,N），实际使用[1,n]
    //初始化N，n，初始化tree[]为0
    //函数输入，函数返回值输出
    static const int N;
    int n,tree[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;}
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=tree[i];
        return ret;
    }
    int sigma(int u,int v){return sigma(v)-sigma(u-1);}
};

struct Binary_Indexed_Tree{
    //区间更新点查询,最大可用范围[1,N）,实际使用[1,n]
    //初始化N，n初始化tree[]为0
    //函数输入，函数返回值输出
    static const int N;
    int n,tree[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){for(int i=k;i<=n;i+=i&-i)tree[i]+=d;}
    void add(int u,int v,int d){
        add(u,d);
        add(v+1,-d);
    }
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=tree[i];
        return ret;
    }
};

struct Binary_Indexed_Tree{
    //区间更新区间查询,最大可用范围[1,N）,实际使用[1,n]
    //初始化N，n初始化tree[]、tree2[]为0
    //函数输入，函数返回值输出
    static const int N;
    int n,tree[N],tree2[N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++)tree[i]=0;
    };
    void add(int k,int d){
        for(int i=k;i<=n;i+=i&-i)tree[i]+=d,tree2[i]+=k*d;
    }
    void add(int u,int v,int d){
        add(u,d);
        add(v+1,-d);
    }
    int sigma(int k){
        int ret=0;
        for(int i=k;i;i-=i&-i)ret+=(k+1)*tree[i]-tree2[i];
        return ret;
    }
    int sigma(int u,int v){
        return sigma(v)-sigma(u-1);
    }
};


struct Binary_Indexed_Tree{
    //二维点更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N，n初始化tree[][]为0
    //函数参数输入，函数返回值输出
    static const int N;
    int n, tree[N][N];
    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j)
                tree[i][j]+=d;
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j)
                ret+=tree[i][j];
        return ret;
    }
    int sigma(int x1,int y1,int x2,int y2){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x1--;y1--;
        return sigma(x1,y1)+sigma(x2,y2)-sigma(x1,y2)-sigma(x2,y1);
    }
};

struct Binary_Indexed_Tree{
    //二维区间更新点查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N，n初始化tree[][]为0
    //函数参数输入，函数返回值输出
    static const int N;
    int n,tree[N][N];
    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j)
                tree[i][j]+=d;
    }
    void add(int x1,int y1,int x2,int y2,int d){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        add(x1,y1,d);
        add(x2+1,y2+1,d);
        add(x1,y2+1,-d);
        add(x2+1,y1,-d);
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j)
                ret+=tree[i][j];
        return ret;
    }
};

struct Binary_Indexed_Tree{
    //二维区间更新区间查询,最大可用范围[1,N)[1,N),实际使用[1,n]
    //初始化N，n初始化tree[][]、treeij[][]、treei[][]、treej[][]为0
    //函数参数输入，函数返回值输出
    static const int N;
    int n,tree[N][N],treeij[N][N],treei[N][N],treej[N][N];

    void ini(int _n){
        n=_n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                tree[i][j]=treei[i][j]=treej[i][j]=treeij[i][j]=0;
            }
        }
    }
    void add(int x,int y,int d){
        for(int i=x;i<=n;i+=i&-i)
            for(int j=y;j<=n;j+=j&-j){
                tree[i][j]+=d;
                treei[i][j]+=x*d;
                treej[i][j]+=y*d;
                treeij[i][j]+=x*y*d;
            }
    }
    void add(int x1,int y1,int x2,int y2,int d){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x2++,y2++;
        add(x1,y1,d);
        add(x2,y2,d);
        add(x1,y2,-d);
        add(x2,y1,-d);
    }
    int sigma(int x,int y){
        int ret=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j){
                ret+=(x+1)*(y+1)*tree[i][j]+treeij[i][j];
                ret-=(x+1)*treej[i][j]+(y+1)*treei[i][j];
            }
        return ret;
    }
    int sigma(int x1,int y1,int x2,int y2){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x1--,y1--;
        return sigma(x1,y1)+sigma(x2,y2)-sigma(x2,y1)-sigma(x1,y2);
    }
};
ACM►老Blog迁移►stencil►data_struct

树链剖分

转移自老blog

树链剖分

       如果给出一棵树并为每个节点标号1234...n;并定义区间[x,y]为树上节点x到节点y的最短路所经过的所有节点组成的集合，注意是闭区间，包括x，y两个节点      

       树链剖分能够解决树上区间的操作，是线段树功能的强化版，但他也依赖着线段树。

       树链剖分尝试着把树分割为多条链，并按照dfs序对链排序并交给线段树维护，如果这个想法成立，那么所有的树上区间操作都成了多段区间的线段树操作。

       现在的问题转移到如何分链，能够保证任何树上区间进行分解时分出的链都较少？否则上诉尝试没有任何意义，前人给出了分法。按轻重链分，

       这里有必要介绍几种名词

               重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；

               轻儿子：父亲节点中除了重儿子以外的儿子；

               重边：父亲结点和重儿子连成的边；

               轻边：父亲节点和轻儿子连成的边；

               重链：由多条重边连接而成的路径；

               轻链：由多条轻边连接而成的路径；

       如此想必读者已经知道如何去分了，但为什么这样分保证任何树上区间进行分解时分出的链都较少

简单证明：

       假设根编号为root

       则区间[x,y]分出的链一定少于[root,x][root,y]这两个区间分出的链的和

       问题可以简化为对于区间[root,x]分出的链的数量的复杂度的证明，

       我们尝试从根往节点x走，一走就走一整条剖分链，如果没有到达x，一定会走上一个轻儿子，每当走上一个轻儿子，问题递归为以轻儿子为根走向节点x，

       可以证明这样的走法每走一步，当前子树的节点数目减半，这是轻儿子的性质。

       我们顶多走Olgn步，这意味着分出的链为Olgn个。子问题证毕。

over

如何分链呢？

       两次dfs

       第一次记录父亲，记录子孙数量，回溯重儿子，

       第二次根据重儿子优先dfs，标记每个节点所属重链的起点，标记dfs序，

       依据dfs序把树变成链并交给线段树处理

       查询的时候便只需要依据每个节点所属重链起点和dfs序进行线段树区间查询，修改也是一样，都交给线段树处理



struct dissection:segment_tree,graph
{
    static const ll maxn=2.1e5;
    ll treen;
    ll dep[maxn],dad[maxn],son[maxn],siz[maxn],tid[maxn],chain[maxn];
    
    //siz,dep,son,dad,
    void dfs1(ll u=1,ll father=1,ll deep=1)
    {
        dep[u]=deep;
        dad[u]=father;
        siz[u]=1;
        for(ll i=head[u]; ~i; i=g[i].nex)
        {
            ll v=g[i].v;
            if(v!=father)
            {
                dfs1(v,u,deep+1);
                siz[u]+=siz[v];
                if (son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
            }
        }
    }
    
    //chain,tid,rnk;
    void dfs2(ll u=1,ll s=1)
    {
        chain[u]=s;
        tid[u]=++treen;
        rnk[treen]=u;
        
        if(son[u]==-1)return;
        dfs2(son[u],s);
        for (ll i=head[u]; ~i; i=g[i].nex)
        {
            ll v=g[i].v;
            if(v!=son[u]&&v!=dad[u])dfs2(v,v);
        }
    }
    
    ll query_path(ll x,ll y)
    {
        ll ans=0;
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            ans+=query(tid[chain[x]],tid[x]);
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        return ans+query(tid[x],tid[y]);
    }
    
    ll query_path_max(ll x,ll y)
    {
        ll ans=-1e9;
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            ans=max(ans,query_max(tid[chain[x]],tid[x]));
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        return max(ans,query_max(tid[x],tid[y]));
    }
    
    void update_path(ll x,ll y,ll d)
    {
        while(chain[x]!=chain[y])
        {
            if(dep[chain[x]]<dep[chain[y]])swap(x,y);
            update(tid[chain[x]],tid[x],d);
            x=dad[chain[x]];
        }
        if(tid[x]>tid[y])swap(x,y);
        update(tid[x],tid[y],d);
    }
    
    void ini()
    {
        graph::ini();
    }
    
    void build()
    {
        treen=0;
        memset(son,-1,sizeof(son));
        dfs1();
        dfs2();
        segment_tree::build(treen);
    }
    
} tree;
ACM►老Blog迁移►stencil►data_struct

线段树

转移自老blog

线段树

线段树

        线段树是树状数组的强化版，它每次对区间进行二分，每一个深度都维护了整个区间，在同一深度里面，每个节点维护的区间长度大致相同，而每深入一层又大致比上一层多一倍的节点，故空间复杂度为Onlgn

节点信息

        每个非叶子节点维护一个区间[l,r]，令mid=(l+r)>>1,则该节点的左儿子维护[l,mid]，右儿子维护[mid+1,r]；
        每个叶子节点维护一个点；

线段树的平衡性

        线段树是一颗几乎完全平衡的树。

线段树的区间操作

        因此当我们对于一个长度为n区间[l,r]进行操作的时候，我们就要操作所有与这些区间相关节点，这些节点数目接近2*N。要操作2*N个节点，，，，复杂度过高，，，问题无法解决。
        我们的操作相当于对树进行函数递归。

对节点分类

        这里我们把这个问题简化一下，对于那些节点对应区间属于[l,r]的我们分为一类，对于那些节点对应区间与[l,r]有交集，但不是[l,r]的子区间的节点我们分为第二类，第二类节点一定是某个第一类节点的父亲节点，借此我们可以在函数回溯时候利用区间加法处理，容易解决。

继续分析复杂度

        我们容易发现第一类节点数目接近ON而第二类节点数目接近OlgN，第二类节点一个一个处理可以接受，第一类节点必须安排一下。可以证明第一类节点恰好可以用OlgN颗子树的所有节点唯一表达。
        在这里我们简化问题为对于OlgN个节点以及OlgN颗子树的操作，

子树的操作

        现在我们只需要考虑对某颗子树进行操作

懒惰标记（懒修改）

        当我们进行修改的时候，我们试着只对该子树的根进行修改，并为其加入一个懒惰标记，表示他的所有子孙都有一个与懒惰标记有关的操作还未进行，(例如整段区间加上d，我们就设懒惰标记为d) ，如此区间修改就不用跑到叶子节点，就成了OlgN
        当我们进行查询时，每当我们查询一个节点，我们要查询的恰好为该节点所对应的区间，直接就处理了；如果不是该区间，而是该区间的某个子区间，那么我们考虑把该区间的懒惰标记下放到左右儿子，然后递归左右儿子，回溯答案。over
        为什么线段树快，因为它把区间分成OlgN个处理，并且每次在树上只跑了OlgN个节点，依据区间加法处理询问，依据区间加法回溯处理修改，依据懒惰标记不实时更新叶子节点。所以线段树快。

线段树和树状数组

        为什么我在开头说线段树是树状数组的强化版，因为树状数组虽然能依据区间加法处理询问，也可以依靠区间加法处理更新，但是它的非叶子节点过少，导致复杂的数据维护时程序较为复杂，不太好处理。
#define ls (u<<1)
#define rs (u<<1|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
struct segment_tree{
    static const ll maxn=2.1e5;
    ll n;
    ll a[maxn],tree[maxn<<2],lazy[maxn<<2];
    //////////////
    //树链剖分接口
    ll rnk[maxn];
    //////////////
    void pushdown(ll u,ll l,ll r){
        //lazy[ls]+=lazy[u];
        //lazy[rs]+=lazy[u];
        //tree[ls]+=lazy[u]*(ml-l+1);
        //tree[rs]+=lazy[u]*(r-mr+1);
        lazy[u]=0;
    }
    void pushup(ll u){
        //tree[u]=tree[ls]+tree[rs];
    }
    void build(ll nn){
        n=nn;
        build(1,n,1);
    }


    void build(ll l,ll r,ll u){
        lazy[u]=0;
        if(l==r){
            //tree[u]=a[rnk[l]];
            return ;
        }

        build(l,ml,ls);
        build(mr,r,rs);
        pushup(u);
    }
    void update(ll ql,ll qr,ll d){
        update(ql,qr,d,1,1,n);
    }
    void update(ll ql,ll qr,ll d,ll u,ll l,ll r){
        if(ql<=l&&r<=qr){
            //tree[u]+=(r-l+1)*d;
            //lazy[u]+=d;
            return ;
        }
        if(lazy[u])pushdown(u,l,r);
        if(ql<=ml)update(ql,qr,d,ls,l,ml);
        if(qr>=mr)update(ql,qr,d,rs,mr,r);
        pushup(u);
    }
    ll query(ll ql,ll qr){
        return query(ql,qr,1,1,n);
    }
    ll query(ll ql,ll qr,ll u,ll l,ll r){
        if(ql<=l&&r<=qr)return tree[u];
        ll ret=0;
        if(lazy[u])pushdown(u,l,r);
        if(ql<=ml)ret+=query(ql,qr,ls,l,ml);
        if(qr>=mr)ret+=query(ql,qr,rs,mr,r);
        return ret;
    }
};

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=5e4+5;
int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot;

void push_son(int&son,int l,int r,int covrt,int revrt){// 这个函数要注意重写
    if(son==0) {
        son=++tot;
        cov[son]=-1;
        rev[son]=0;
        sum[son]=0;
        ls[son]=0;
        rs[son]=0;
    }
    if(covrt!=-1){
        sum[son]=(r-l+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=(r-l+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml,cov[rt],rev[rt]);// 这行要注意重写
    push_son(rs[rt],mr,r,cov[rt],rev[rt]);// 这行要注意重写
    cov[rt]=-1; rev[rt]=0;// 这行要注意重写
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];// 这行要注意重写
}

void build(int&rt,int l,int r){
    rt=tot=0;
    push_son(rt,l,r,-1,0);// 这行要注意重写
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){//
    if(ql<=l&&r<=qr){// 这行要注意重写
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
        return;
    }
    push_down(rt,l,r);
    if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type);
    if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type);
    push_up(rt,l,r);
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[rt];// 这行要注意重写
    push_down(rt,l,r);
    int ret=0;// 这行要注意重写
    if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr);// 这行要注意重写
    if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr);// 这行要注意重写
    return ret;
}
ACM►老Blog迁移►stencil►data_struct

线段树套线段树

转移自老blog

线段树套线段树

我的第一颗树套树

       树套树的思路估计都这样子了，树套树分为外树和内树，也可以分为第一维树和 第二维树，我这里把他们叫做x树和y树，即x树为外树，y树为内树。我们描述时 用内外，代码用xy。
       首先树套树，顾名思义，给出定义，树套树是一棵节点是树的树。
       于是作为一棵树,他有这些函数：
             建树build，更新update，查询query
       一个一个来说

建树

       建树先建外层树，递归建树，递归出口为当前外树所代表的只有一行， 他是叶子结点树，这时调用建内层树，并退出函数，回溯时，意味着此时 是非叶子节点树，意味着外树所代表的不止一行， 意味着此节点树的儿子 节点树以经建立完成，此时我们调用建 内层树，
       建树建内层树，依旧递归，和一维线段树相比，只是递归出口有所区别， 建内层树时，如果该树为叶子节点树，直接处理，但是当他为非叶节点树 的时候要注意，此时不能直接对当前节点（不是节点树，是节点树的递归 出口所对应的节点）修改值，而是借助上诉结论“意味着此节点树的儿子 节点树以经建立完成”，我们可以通过跨越树来更新值，
       这里有点难以理解，其实仔细的想想，我们建立的虽然说是一颗二维的 二叉树，两颗内树之间的关系确并不是我们想象的那么简单，举个例子， 如果mi[i][j]记录了外树节点树i对应的内树节点j的数据，那么mi[i][j]只能 由mi[i][j<<1]和mi[i][j<<1|1]推过来吗,这里显然不对,如果细心点,我们会发现 我们建立的并不是简单的二维树,它更是一个超级复杂的图,我们站在更高的 角度上看,mi[i<<1][j]和mi[i<<1|1][j]又何尝不能作为mi[i][j]的后继呢?
       于是我们就有了通过mi[i<<1][j]和mi[i<<1|1][j]来更新值的做法,跨越树,用另一棵树 来更新自己,ok? 于是建树完成.

更新

       和建树是一样的

查询

       查询的话就简单很多了，不需要跨越树就能完成，这个的依据是区间的可加性


这只是一颗单点修改，区间最值查询的树 
#define pii pair<int,int>
struct segment{
    static const int maxn=1000;
    int ma[maxn<<2][maxn<<2],mi[maxn<<2][maxn<<2];
    int tmp[maxn][maxn];
    int lenx,leny;
    //x为行 y为列
    
    void build(int n){
        lenx=leny=n;
        build_x(1,n,1);
    }
    void build_x(int x1,int x2,int rtx){
        if(x1==x2){
            build_y(x1,x2,1,leny,rtx,1);
            return;
        }
        int midx=(x1+x2)>>1;
        build_x(x1,midx,rtx<<1);
        build_x(midx+1,x2,rtx<<1|1);
        
        build_y(x1,x2,1,leny,rtx,1);
    }
    void build_y(int x1,int x2,int y1,int y2,int rtx,int rty){
        if(y1==y2){
            if(x1==x2){
                mi[rtx][rty]=tmp[x1][y1];
                ma[rtx][rty]=tmp[x1][y1];
            }else{
                mi[rtx][rty]=min(mi[rtx<<1][rty],mi[rtx<<1|1][rty]);
                ma[rtx][rty]=max(ma[rtx<<1][rty],ma[rtx<<1|1][rty]);
            }
            return;
        }
        int midy=(y1+y2)>>1;
        build_y(x1,x2,y1,midy,rtx,rty<<1);
        build_y(x1,x2,midy+1,y2,rtx,rty<<1|1);
        
        mi[rtx][rty]=min(mi[rtx][rty<<1],mi[rtx][rty<<1|1]);
        ma[rtx][rty]=max(ma[rtx][rty<<1],ma[rtx][rty<<1|1]);
    }
    
    
    void update(int x,int y,int d){
        update_x(x,y,d,1,lenx,1);
    }
    void update_x(int x,int y,int d,int x1,int x2,int rtx){
        if(x1==x2){
            update_y(y,d,x1,x2,1,leny,rtx,1);
            return;
        }
        int midx=(x1+x2)>>1;
        if(x<=midx)update_x(x,y,d,x1,midx,rtx<<1);
        else update_x(x,y,d,midx+1,x2,rtx<<1|1);
        update_y(y,d,x1,x2,1,leny,rtx,1);
    }
    void update_y(int y,int d,int x1,int x2,int y1,int y2,int rtx,int rty){
        if(y1==y2){
            if(x1==x2){
                mi[rtx][rty]=d;
                ma[rtx][rty]=d;
            }else{
                mi[rtx][rty]=min(mi[rtx<<1][rty],mi[rtx<<1|1][rty]);
                ma[rtx][rty]=max(ma[rtx<<1][rty],ma[rtx<<1|1][rty]);
            }
            return;
        }
        int midy=(y1+y2)>>1;
        if(y<=midy)update_y(y,d,x1,x2,y1,midy,rtx,rty<<1);
        else update_y(y,d,x1,x2,midy+1,y2,rtx,rty<<1|1);
        mi[rtx][rty]=min(mi[rtx][rty<<1],mi[rtx][rty<<1|1]);
        ma[rtx][rty]=max(ma[rtx][rty<<1],ma[rtx][rty<<1|1]);
    }
    
    
    pii query(int qx1,int qx2,int qy1,int qy2){
        return query_x(qx1,qx2,qy1,qy2,1,lenx,1);
    }
    pii getpii(pii a,pii b){
        return pii(min(a.first,b.first),max(a.second,b.second));
    }
    pii query_x(int qx1,int qx2,int qy1,int qy2,int x1,int x2,int rtx){
        if(qx1<=x1&&x2<=qx2){
            return query_y(qy1,qy2,1,leny,rtx,1);
        }
        
        pii ret=pii(2e9,0);
        int midx=(x1+x2)>>1;
        if(midx>=qx1)ret=getpii(ret,query_x(qx1,qx2,qy1,qy2,x1,midx,rtx<<1));
        if(midx+1<=qx2)ret=getpii(ret,query_x(qx1,qx2,qy1,qy2,midx+1,x2,rtx<<1|1));
        return ret;
    }
    pii query_y(int qy1,int qy2,int y1,int y2,int rtx,int rty){
        if(qy1<=y1&&y2<=qy2){
            return pii(mi[rtx][rty],ma[rtx][rty]);
        }
        
        pii ret(2e9,0);
        int midy=(y1+y2)>>1;
        if(midy>=qy1)ret=getpii(ret,query_y(qy1,qy2,y1,midy,rtx,rty<<1));
        if(midy+1<=qy2)ret=getpii(ret,query_y(qy1,qy2,midy+1,y2,rtx,rty<<1|1));
        return ret;
    }
}tree;
ACM►老Blog迁移►stencil►data_struct

镜像并查集

转移自老blog

镜像并查集

镜像处理时都有这种关系
朋友的朋友是朋友，敌人的敌人是朋友，朋友的敌人是敌人，敌人的朋友是朋友，

如何快速判断朋友与敌人呢？
我们让每个人都有两重身份，一个是自己，一个是自己的相反面，即a与a'是天生的敌人，b与b'是天生的敌人
当a和b成为朋友的时候，我们让a'与b'成为朋友，a与b'，b与a'成为敌人
当a和b成为敌人的时候，我们让a'与b'成为敌人，a与b'，b与a'成为朋友
如此我们就可以迅速判断多组输入时候的朋友与敌人关系了

例如1与2是敌人，2与3是敌人，3与4是敌人，4与5是敌人
   问1与5什么关系
   我们来建立模型
       1与2是敌人 [1,  2']. [1',  2]
       2与3是敌人[1,  2',  3]. [1',  2,  3']
       3与4是敌人[1,  2',  3,  4']. [1',  2,  3',  4]
       4与5是敌人[1,  2',  3,  4',  5]. [1',  2,  3',  4,  5']
       以经很明显了1和5是朋友

1.判断一个图是否是二分图
 把每个点分成两个点，一个代表本身，一个代表对立面（镜像），对每条边（u,v）都使用join（u+n,v）,join(u,n+v)
最后判断find（1）==find（n+1）？相等则不是二分图，反之为二分图

ACM►学习笔记►图论

斯坦纳树

dp的意义代码中写的很清楚，唯一要注意的是，有一个卡常的地方，显然对于n个点m条边取k个点的斯坦纳树，我们的dp有意义开到dp[1<<k][n]吗？ 这里是不必的，我们只需要开到dp[1<<(k-1)][n]即可，很容易想到dp[(1<<k)-1][any]中对于所有0<any<=k都是答案,然而却不一定能想到 dp[(1<<(k-1))-1][k]也是答案，借此我们可以提升50%的时空性能

牛客上的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int k;

/**graph*/
struct star {
    int v, nex;
} edge[1000 * 2];
int head[50], cnt, n, m;

void ini() {
    cnt = -1;
    for (int i = 0; i < n; i++) head[i] = -1;
}

void add_edge(int u, int v) {
    edge[++cnt] = star{v, head[u]}, head[u] = cnt;
    edge[++cnt] = star{u, head[v]}, head[v] = cnt;
}


/**dp*/
struct dpnode {
    int w, ct;

    dpnode(int w = 0, int ct = 0) : w(w), ct(ct) {}
};

dpnode dp[3][1 << 12][50];

// dp[0][s][i] 保证s联通的斯坦纳树的答案中 包含节点i的部分
// dp[1][s][i] 保证s联通 且 删除i节点以后依旧联通 的斯坦纳树的答案中 包含节点i的部分
// dp[2][s][i] 保证s联通 且 删除i节点以后不联通了 的斯坦纳树的答案中 包含节点i的部分
// if   ( dp[1].w==dp[2].w ) dp[0]=merge(dp[1],dp[2])
// elif ( dp[1].w< dp[2].w ) dp[0]=dp[1]
// else                      dp[0]=dp[2]
dpnode dpmerge(dpnode a, dpnode b) {
    return dpnode(a.w + b.w, 1ll * a.ct * b.ct % mod);
}

void upd(dpnode &a, dpnode b) {
    if (b.w < a.w) a = b;
    else if (b.w == a.w) {
        a.ct = a.ct + b.ct;
        if (a.ct >= mod) a.ct -= mod;
    }
}


int main() {
    while (~scanf("%d%d%d", &n, &m, &k)) {
        ini();
        for (int i = 0, u, v; i < m; i++) {
            scanf("%d%d", &u, &v);
            add_edge(u - 1, v - 1);
        }
        k--;
        for (int s = 0; s < 1 << k; s++) {
            for (int i = 0; i < n; i++) dp[0][s][i] = dp[1][s][i] = dp[2][s][i] = dpnode(1e9, 0);
        }

        for (int i = 0; i < k; i++) {
            upd(dp[1][1 << i][i], dpnode(0, 1));
            upd(dp[0][1 << i][i], dpnode(0, 1));
        }
        for (int s = 1; s < 1 << k; s++) {
            for (int i = 0; i < n; i++) {
                for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) {//枚举s的非空真子集
                    if ((s0 & -s0) == (s & -s)) {// s0 必然包含s的最小的点
//                      upd(dp[2][s][i], dpmerge(dp[1][s0][i], dp[0][s ^ s0][i]));
                        upd(dp[0][s][i], dpmerge(dp[1][s0][i], dp[0][s ^ s0][i]));// type1
                    }
                }
            }
            // dij
            struct dijnode {
                int w,id;

                bool operator<(const dijnode &rhs) const { return w > rhs.w; }
            };
            priority_queue<dijnode> q;
            for (int i = 0; i < n; i++) q.push(dijnode{dp[0][s][i].w, i});
            while (!q.empty()) {
                dijnode top = q.top(); q.pop();
                if(top.w!=dp[0][s][top.id].w) continue;
                for (int i = head[top.id]; ~i; i = edge[i].nex) {
                    if (top.w + 1 <= dp[0][s][edge[i].v].w) {
                        upd(dp[1][s][edge[i].v], dpmerge(dp[0][s][top.id], dpnode(1, 1)));
                        upd(dp[0][s][edge[i].v], dpmerge(dp[0][s][top.id], dpnode(1, 1))); // type2
                        q.push(dijnode{dp[0][s][edge[i].v].w, edge[i].v});
                    }
                }
            }
        }
        cout << dp[0][(1 << k) - 1][k].ct+1-1 << endl;
    }
}
ACM►学习笔记►图论

树的最小路径覆盖

用最少条数的路径覆盖树，这是一个树dp问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int u,int father){
    int sum=0;
    for(int i=head[u];~i;i=edge[i].nex){
        if(edge[i].v==father) continue;
        dfs(edge[i].v,u);
        sum+=dp[edge[i].v][0];
    }
    dp[u][0]=sum+1;//子树路径覆盖的答案
    dp[u][1]=sum+1;
    vector<int>update;
    for(int i=head[u];~i;i=edge[i].nex){
        if(edge[i].v==father) continue;
        update.push_back(-dp[edge[i].v][0]+dp[edge[i].v][1]-1);
    }
    sort(update.begin(),update.end());
    if(update.size()>=1) {
        if(update[0]<0) dp[u][0]+=update[0];
        if(update[0]<0) dp[u][1]+=update[0];
    }
    if(update.size()>=2){
        if(update[1]<0) dp[u][0]+=update[1];
    }
}// dp[root][0] is min path cover the tree