本文主要是介绍【算法提高——第四讲】高级数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 第四章 高级数据结构
• • 4.1 并查集
  • • 4.1.1 1250. 格子游戏
    • 4.1.2 1252. 搭配购买
    • 4.1.3 237. 程序自动分析
    • 4.1.4 239. 奇偶游戏
    • 4.1.5 238. 银河英雄传说
  • 4.2 树状数组
  • • 4.2.1 241. 楼兰图腾
    • 4.2.2 242. 一个简单的整数问题
    • 4.2.3 243. 一个简单的整数问题2
    • 4.2.4 244. 谜一样的牛
  • 4.3 线段树
  • • 4.3.1 1275. 最大数
    • 4.3.2 245. 你能回答这些问题吗
    • 4.3.3 246. 区间最大公约数
    • 4.3.4 243. 一个简单的整数问题2
    • 4.3.5 247. 亚特兰蒂斯
    • 4.3.6 1277. 维护序列
  • 4.4 可持久化数据结构
  • • 4.4.1 256. 最大异或和
    • 4.4.2 255. 第K小数
  • 4.5 平衡树
  • • 4.5.1 253. 普通平衡树
    • 4.5.2 265. 营业额统计
  • 4.6 AC自动机
  • • 4.6.1 1282. 搜索关键词
    • 4.6.2 1285. 单词

第四章 高级数据结构

4.1 并查集

4.1.1 1250. 格子游戏

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=40010;

int n,m;
int p[N];
int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<=N;i++) p[i]=i;

    bool success=false;
    for(int i=0;i<m;i++)
    {
        int x,y;
        char c;
        cin>>x>>y>>c;
        int a=(x-1)*n+y-1;
        int b=a;
        if(c=='R')
        {
            b++;
        }
        else
            b+=n;

        int pa=findP(a),pb=findP(b);
        if(pa==pb)
        {
            cout<<i+1<<endl;
            success=true;
            break;
        }
        else
            p[pa]=pb;
    }

    if(!success)
        cout<<"draw"<<endl;
    return 0;
}

4.1.2 1252. 搭配购买

代码：

#include<bits/stdc++.h> //y总的

using namespace std;

const int N = 10010;

int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m >> vol;

    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            v[pb] += v[pa];
            w[pb] += w[pa];
            p[pa] = pb;
        }
    }

    // 01背包
    for (int i = 1; i <= n; i ++ )
        if (p[i] == i)
            for (int j = vol; j >= v[i]; j -- )
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[vol] << endl;

    return 0;
}
/* 自己写的
#include<bits/stdc++.h>
using namespace std;
const int N=10010;

int n,m,w;
map<int,pair<int,int> > mp;
int money[N],value[N];
int cnt;
int M[N],V[N];
int dp[N];
int p[N];
int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=1;i<=n;i++)
    {
        cin>>money[i]>>value[i];
    }

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        p[findP(a)]=findP(b);
    }

    for(int i=1;i<=n;i++)
    {
        int pa=findP(i);
        mp[pa].first+=money[i];
        mp[pa].second+=value[i];
    }

    for(map<int,pair<int,int> >::iterator it=mp.begin();it!=mp.end();it++)
    {
        cnt++;
        M[cnt]=it->second.first;
        V[cnt]=it->second.second;
    }

    for(int i=1;i<=cnt;i++)
    {
        for(int j=w;j>=M[i];j--)
        {
                dp[j]=max(dp[j],dp[j-M[i]]+V[i]);
        }
    }

    cout<<dp[w];

    return 0;
}
*/

4.1.3 237. 程序自动分析

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;

int cnt;
struct Node{
    int a,b,c;
}op[100010];
unordered_map<int,int> mp;
int p[N];
int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cnt=1;
        mp.clear();
        for(int i=1;i<=N;i++) p[i]=i;
        for(int i=1;i<=n;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(mp.count(a)==0)
                mp[a]=cnt++;
            if(mp.count(b)==0)
                mp[b]=cnt++;
            op[i].a=a,op[i].b=b,op[i].c=c;
        }

        for(int i=1;i<=n;i++)
        {
            int a=op[i].a,b=op[i].b,c=op[i].c;
            if(c==1)
            {
                p[findP(mp[a])]=findP(mp[b]);
            }
        }

        bool success=true;
        for(int i=1;i<=n;i++)
        {
            int a=op[i].a,b=op[i].b,c=op[i].c;
            if(c==0)
            {
                if(findP(mp[a])==findP(mp[b]))
                {
                    success=false;
                    break;
                }
            }
        }
        if(success) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

4.1.4 239. 奇偶游戏

代码：

#include<bits/stdc++.h>     //带边权并查集
using namespace std;
const int N=20010;

int n,m;
int p[N],d[N];
map<int,int> S;

int get(int x)
{
    if(S.count(x)==0) S[x]=++n;
    return S[x];
}

int findP(int x)
{
    if(p[x]!=x)
    {
        int root=findP(p[x]);
        d[x]^=d[p[x]];
        p[x]=root;
    }
    return p[x];
}
int main()
{
    cin>>n>>m;
    n=0;

    for(int i=0;i<N;i++) p[i]=i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;
        cin>>a>>b>>type;
        a=get(a-1),b=get(b);

        int t=0;
        if(type=="odd") t=1;

        int pa=findP(a),pb=findP(b);
        if(pa==pb)
        {
            if(d[a]^d[b]!=t)
            {
                res=i-1;
                break;
            }
        }
        else
        {
            p[pa]=pb;
            d[pa]=d[a]^d[b]^t;
        }
    }

    cout<<res<<endl;

    return 0;
}

/* 扩展域
#include<bits/stdc++.h>
using namespace std;
const int N=40010,base=N/2;

int n,m;
int p[N],d[N];
map<int,int> S;

int get(int x)
{
    if(S.count(x)==0) S[x]=++n;
    return S[x];
}

int findP(int x)
{
    if(p[x]!=x) return p[x]=findP(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    n=0;

    for(int i=0;i<N;i++) p[i]=i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;
        cin>>a>>b>>type;
        a=get(a-1),b=get(b);

        if(type=="even")
        {
            if(findP(a+base)==findP(b))
            {
                res=i-1;
                break;
            }
            p[findP(a)]=findP(b);
            p[findP(a+base)]=findP(b+base);
        }
        else
        {
            if(findP(a)==findP(b))
            {
                res=i-1;
                break;
            }
            p[findP(a)]=findP(b+base);
            p[findP(a+base)]=findP(b);
        }
    }

    cout<<res<<endl;

    return 0;
}
*/

4.1.5 238. 银河英雄传说

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=30010;

int n;
int p[N],sz[N],d[N];
int findP(int x)
{
    if(p[x]!=x)
    {
        int root=findP(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}
int main()
{
    cin>>n;
    for(int i=1;i<=N;i++)
    {
        p[i]=i;
        sz[i]=1;
    }

    for(int i=0;i<n;i++)
    {
        string type;
        int a,b;
        cin>>type>>a>>b;
        int pa=findP(a),pb=findP(b);
        if(type=="M")
        {
            d[pa]=sz[pb];
            sz[pb]+=sz[pa];
            p[pa]=pb;
        }
        else
        {
            if(pa!=pb)
                cout<<-1<<endl;
            else
                cout<<max(0,abs(d[a]-d[b])-1)<<endl;
        }
    }
    return 0;
}

4.2 树状数组

4.2.1 241. 楼兰图腾

代码：

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

const int N=200010;

int n;
int a[N],tr[N];
int big[N],little[N];
int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  //从x开始
        tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=tr[i];
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        big[i]=sum(n)-sum(y);
        little[i]=sum(y-1);
        add(y,1);
    }

    memset(tr,0,sizeof tr);
    LL res1=0,res2=0;
    for(int i=n;i>=1;i--)
    {
        int y=a[i];
        res1+=big[i]*(LL)(sum(n)-sum(y));
        res2+=little[i]*(LL)sum(y-1);
        add(y,1);
    }

    cout<<res1<<" "<<res2<<endl;

    return 0;
}

4.2.2 242. 一个简单的整数问题

代码：

#include<bits/stdc++.h> //差分，树状数组综合应用
using namespace std;
const int N=100010;

int n,m;
int a[N];
int b[N];   //差分数组
int tr[N];  //差分数组的树状数组

void myinsert(int l,int r,int c)    //差分
{
    b[l]+=c,b[r+1]-=c;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  //从x开始
        tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=tr[i];
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++)
        myinsert(i,i,a[i]);

    for(int i=1;i<=n;i++)
        add(i,b[i]);

    while(m--)
    {
        string op;
        cin>>op;
        if(op=="Q")
        {
            int x;
            cin>>x;
            cout<<sum(x)<<endl;
        }
        else
        {
            int l,r,c;
            cin>>l>>r>>c;
            add(l,c),add(r+1,-c);
        }
    }
    return 0;
}

4.2.3 243. 一个简单的整数问题2

代码：

#include<bits/stdc++.h> //差分，树状数组综合应用
using namespace std;
typedef long long LL;
const int N=100010;

int n,m;
int a[N];
LL tr_b[N];  //差分数组b[i]的树状数组
LL tr_bi[N]; //差分数组b[i]*i的树状数组


int lowbit(int x)
{
    return x&(-x);
}

void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i))  //从x开始
        tr[i]+=c;
}

LL sum(LL tr[],int x)
{
    LL res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=tr[i];
    return res;
}

LL prefix_sum(int x)
{
    return sum(tr_b,x)*(x+1)-sum(tr_bi,x);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        add(tr_b,i,b);
        add(tr_bi,i,(LL)b*i);
    }

    while(m--)
    {
        string op;
        int l,r,d;
        cin>>op>>l>>r;
        if(op=="Q")
        {
            cout<<prefix_sum(r)-prefix_sum(l-1)<<endl;
        }
        else
        {
            cin>>d;
            add(tr_b,l,d),add(tr_b,r+1,-d);
            //均只要修改两处
            add(tr_bi,l,l*d),add(tr_bi,r+1,(r+1)*-d);
        }
    }
    return 0;
}

4.2.4 244. 谜一样的牛

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=c;
}
int sum(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        res+=tr[i];
    return res;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
        cin>>h[i];

    for(int i=1;i<=n;i++)
        tr[i]=lowbit(i);

    for(int i=n;i>0;i--)
    {
        int k=h[i]+1;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(sum(mid)>=k) r=mid;
            else l=mid+1;
        }
        ans[i]=r;
        add(r,-1);
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;

    return 0;
}

4.3 线段树

4.3.1 1275. 最大数

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010,INF=0x3f3f3f3f;

int m,p;
int n;
struct Node
{
    int l,r;
    int v;  // 区间[l, r]中的最大值
    Node(){}
    Node(int _l,int _r,int _v)
    {
        l=_l,r=_r,v=_v;
    }
}tr[4*N];

void pushup(int u)  // 由子节点的信息，来计算父节点的信息 u表示父节点编号
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

void build(int u,int l,int r)   //u表示父节点编号,从u开始建立[l,r]的线段树
{
    tr[u]=Node(l,r,0);
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了

    int mid=tr[u].l+tr[u].r>>1;
    int v=-INF;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v=max(v,query(u<<1|1,l,r));

    return v;
}

void modify(int u,int x,int v) //单点修改，将u父节点编号，x是要修改的点，v是要修改为多少
{
    if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else  modify(u<<1|1,x,v);
        pushup(u);
    }
}
int main()
{
    cin>>m>>p;
    int num=0;

    build(1,1,m);

    while(m--)
    {
        string op;
        int x;
        cin>>op>>x;
        if(op=="Q")
        {
            num=query(1,n-x+1,n);
            cout<<num<<endl;
        }
        else
        {
            n++;
            modify(1,n,(num+x)%p);
        }
    }
    return 0;
}

4.3.2 245. 你能回答这些问题吗

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500010,INF=0x3f3f3f3f;

int n,m;
int w[N];
struct Node
{
    int l,r;
    int sum,tmax,lmax,rmax;
    Node(){}
    Node(int _l,int _r,int _sum,int _tmax,int _lmax,int _rmax)
    {
        l=_l,r=_r,sum=_sum,tmax=_tmax,lmax=_lmax,rmax=_rmax;
    }
}tr[N*4];

void pushup(Node &u,Node &l,Node &r)
{
    u.sum=l.sum+r.sum;
    u.lmax=max(l.lmax,l.sum+r.lmax);
    u.rmax=max(r.rmax,r.sum+l.rmax);
    u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],w[r],w[r],w[r]);
    else
    {
        tr[u]=Node(l,r,0,0,0,0);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x) tr[u]=Node(x,x,v,v,v,v);
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}

Node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else
    {
        Node left=query(u<<1,l,r);
        Node right=query(u<<1|1,l,r);
        Node res;
        pushup(res,left,right);
        return res;
    }
}
int main()
{
    ios::sync_with_stdio(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i];

    build(1,1,n);

    while(m--)
    {
        int k,x,y;
        cin>>k>>x>>y;
        if(k==1)
        {
            if(x>y) swap(x,y);
            cout<<query(1,x,y).tmax<<endl;
        }
        else modify(1,x,y);
    }
    return 0;
}

4.3.3 246. 区间最大公约数

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;

int n,m;
LL w[N];
struct Node
{
    int l,r;
    LL sum,d;
    Node(){}
    Node(int _l,int _r,LL _sum,LL _d)
    {
        l=_l,r=_r,sum=_sum,d=_d;
    }
}tr[N*4];

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

void pushup(Node &u,Node &l,Node &r)
{
    u.sum=l.sum+r.sum;
    u.d=gcd(l.d,r.d);
}

void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        LL b=w[r]-w[r-1];
        tr[u]=Node(l,r,b,b);
    }
    else
    {
        tr[u].l=l,tr[u].r=r;
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int x,LL v)
{
    if(tr[u].l==x&&tr[u].r==x)
    {
        LL b=tr[u].sum+v;
        tr[u]=Node(x,x,b,b);
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}

Node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];

    //注意三种情况
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else
    {
        Node left=query(u<<1,l,r);
        Node right=query(u<<1|1,l,r);
        Node res;
        pushup(res,left,right);
        return res;
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];

    build(1,1,n);

    string op;
    int l,r;
    LL d;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op=="Q")
        {
            Node left=query(1,1,l);
            Node right=Node(0,0,0,0);
            if(l+1<=r) right=query(1,l+1,r);
            cout<<abs(gcd(left.sum,right.d))<<endl;
        }
        else
        {
            cin>>d;
            modify(1,l,d);
            if(r+1<=n) modify(1,r+1,-d);
        }
    }
    return 0;
}

4.3.4 243. 一个简单的整数问题2

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;

int n,m;
int w[N];
struct Node
{
    int l,r;
    LL sum,add;
    Node(){}
    Node(int _l,int _r,LL _sum,LL _add)
    {
        l=_l,r=_r,sum=_sum,add=_add;
    }
}tr[N*4];

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add)
    {
        left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],0);
    else
    {
        tr[u]=Node(l,r,0,0);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else // 一定要分裂
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,d);
        if(r>mid) modify(u<<1|1,l,r,d);
        pushup(u);
    }
}

LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    LL sum=0;
    if(l<=mid) sum+=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}
int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];

    build(1,1,n);

    string op;
    int l,r,d;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op=="C")
        {
            cin>>d;
            modify(1,l,r,d);
        }
        else
            cout<<query(1,l,r)<<endl;
    }
    return 0;
}

4.3.5 247. 亚特兰蒂斯

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
typedef pair<double,double> PII;

int n;
struct Segment
{
    double x,y1,y2;
    int k;
    Segment(){}
    Segment(double _x,double _y1,double _y2,int _k)
    {
        x=_x,y1=_y1,y2=_y2,k=_k;
    }
    bool operator < (const Segment &t) const
    {
        return x<t.x;
    }
}seg[N*2];
struct Node
{
    int l,r;
    int cnt;
    double len;
    Node(){}
    Node(int _l,int _r,int _cnt,double _len)
    {
        l=_l,r=_r,cnt=_cnt,len=_len;
    }
}tr[N*2*4];

vector<double> ys;

int find_y(double y)
{
    return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}

void pushup(int u)
{
    if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
    else if(tr[u].l!=tr[u].r)
    {
        tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    }
    else tr[u].len=0;
}

void build(int u,int l,int r)
{
    tr[u]=Node(l,r,0,0);
    if(l!=r)
    {
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    }
}

void modify(int u,int l,int r,int k)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].cnt+=k;
        pushup(u);
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,k);
        if(r>mid) modify(u<<1|1,l,r,k);
        pushup(u);
    }
}
int main()
{
    int T=1;
    while(true)
    {
        cin>>n;
        if(n==0) break;
        ys.clear();
        for(int i=0,j=0;i<n;i++)
        {
            double x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            seg[j++]=Segment(x1,y1,y2,1);
            seg[j++]=Segment(x2,y1,y2,-1);
            ys.push_back(y1),ys.push_back(y2);
        }

        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());

        build(1,0,ys.size()-2);

        sort(seg,seg+n*2);

        double res=0;
        for(int i=0;i<n*2;i++)
        {
            if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);
            modify(1,find_y(seg[i].y1),find_y(seg[i].y2)-1,seg[i].k);
        }

        printf("Test case #%d\n",T++);
        printf("Total explored area: %.2f\n\n",res);
    }
    return 0;
}

4.3.6 1277. 维护序列

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;

int n,p,m;
int w[N];
struct Node
{
    int l,r;
    int sum,add,mul;
    Node(){}
    Node(int _l,int _r,int _sum,int _add,int _mul)
    {
        l=_l,r=_r,sum=_sum,add=_add,mul=_mul;
    }
}tr[N*4];

void pushup(int u)
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

void eval(Node &t,int add,int mul)
{
    t.sum=((LL)t.sum*mul+(LL)(t.r-t.l+1)*add)%p;
    t.mul=(LL)t.mul*mul%p;
    t.add=((LL)t.add*mul+add)%p;
}

void pushdown(int u)
{
    eval(tr[u<<1],tr[u].add,tr[u].mul);
    eval(tr[u<<1|1],tr[u].add,tr[u].mul);
    tr[u].add=0,tr[u].mul=1;
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],0,1);
    else
    {
        tr[u]=Node(l,r,0,0,1);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int add,int mul)
{
    if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);
    else
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,add,mul);
        if(r>mid) modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}

int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;
    return sum;
}
int main()
{
    cin>>n>>p;

    for(int i=1;i<=n;i++) cin>>w[i];

    build(1,1,n);

    cin>>m;
    while(m--)
    {
        int t,l,r,d;
        cin>>t>>l>>r;
        if(t==1)
        {
            cin>>d;
            modify(1,l,r,0,d);
        }
        else if(t==2)
        {
            cin>>d;
            modify(1,l,r,d,1);
        }
        else
            cout<<query(1,l,r)<<endl;
    }
    return 0;
}

4.4 可持久化数据结构

4.4.1 256. 最大异或和

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=600010,M=N*25;

int n,m;
int s[N];
int tr[M][2],max_id[M];
int root[N],idx;

void my_insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        max_id[q]=i;
        return;
    }
    int v=s[i]>>k&1;
    if(p) tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    my_insert(i,k-1,tr[p][v],tr[q][v]);
    max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
}

int query(int root,int C,int L)
{
    int p=root;
    for(int i=23;i>=0;i--)
    {
        int v=C>>i&1;
        if(max_id[tr[p][v^1]]>=L) p=tr[p][v^1];
        else p=tr[p][v];
    }

    return C^s[max_id[p]];
}
int main()
{
    ios::sync_with_stdio(0);

    cin>>n>>m;

    max_id[0]=-1;
    root[0]=++idx;
    my_insert(0,23,0,root[0]);

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s[i]=s[i-1]^x;
        root[i]=++idx;
        my_insert(i,23,root[i-1],root[i]);
    }

    string op;
    int l,r,x;
    while(m--)
    {
        cin>>op;
        if(op=="A")
        {
            cin>>x;
            n++;
            s[n]=s[n-1]^x;
            root[n]=++idx;
            my_insert(n,23,root[n-1],root[n]);
        }
        else
        {
            cin>>l>>r>>x;
            cout<<query(root[r-1],s[n]^x,l-1)<<endl;
        }
    }
    return 0;
}

4.4.2 255. 第K小数

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=10010;

int n,m;
int a[N];
vector<int> nums;

struct Node
{
    int l,r;
    int cnt;
}tr[N*4+N*17];

int root[N],idx;

int find_x(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

int build(int l,int r)
{
    int p=++idx;
    if(l==r) return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

int my_insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid) tr[q].l=my_insert(tr[p].l,l,mid,x);
    else tr[q].r=my_insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l==r) return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        nums.push_back(a[i]);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    root[0]=build(0,nums.size()-1);

    for(int i=1;i<=n;i++)
        root[i]=my_insert(root[i-1],0,nums.size()-1,find_x(a[i]));

    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;
    }
    return 0;
}

4.5 平衡树

4.5.1 253. 普通平衡树

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010,INF=1e9;

int n;
struct Node
{
    int l,r;
    int key,val;
    int cnt,sz;
}tr[N];

int root,idx;

void pushup(int p)
{
    tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt;
}

int get_node(int key)   //创建新的节点
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].cnt=tr[idx].sz=1;
    return idx;
}

void zig(int &p)    // 右旋
{
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);
}

void zag(int &p)    // 左旋
{
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
    pushup(tr[p].l),pushup(p);
}

void build()
{
    get_node(-INF),get_node(INF);
    root=1,tr[1].r=2;
    pushup(root);

    if(tr[1].val<tr[2].val) zag(root);
}

void my_insert(int &p,int key)
{
    if(!p) p=get_node(key);
    else if(tr[p].key==key) tr[p].cnt++;
    else if(tr[p].key>key)
    {
        my_insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val) zig(p);
    }
    else
    {
        my_insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val) zag(p);
    }
    pushup(p);
}

void my_remove(int &p,int key)
{
    if(!p) return;
    if(tr[p].key==key)
    {
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].l||tr[p].r)
        {
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
            {
                zig(p);
                my_remove(tr[p].r,key);
            }
            else
            {
                zag(p);
                my_remove(tr[p].l,key);
            }
        }
        else
            p=0;
    }
    else if(tr[p].key>key) my_remove(tr[p].l,key);
    else my_remove(tr[p].r,key);

    pushup(p);
}

int get_rank_by_key(int p,int key)  // 通过数值找排名
{
    if(!p) return 0;    // 本题中不会发生此情况
    if(tr[p].key==key) return tr[tr[p].l].sz+1;
    if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].sz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rk) // 通过排名找数值rk:rank
{
    if(!p) return INF;  // 本题中不会发生此情况
    if(tr[tr[p].l].sz>=rk) return get_key_by_rank(tr[p].l,rk);
    if(tr[tr[p].l].sz+tr[p].cnt>=rk) return tr[p].key;
    return get_key_by_rank(tr[p].r,rk-tr[tr[p].l].sz-tr[p].cnt);
}

int get_prev(int p,int key)     // 找到严格小于key的最大数
{
    if(!p) return -INF;
    if(tr[p].key>=key) return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_next(int p,int key)     // 找到严格大于key的最小数
{
    if(!p) return INF;
    if(tr[p].key<=key) return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}
int main()
{
    build();

    cin>>n;
    while(n--)
    {
        int op,x;
        cin>>op>>x;
        if(op==1) my_insert(root,x);
        else if(op==2) my_remove(root,x);
        else if(op==3) cout<<get_rank_by_key(root,x)-1<<endl;
        else if(op==4) cout<<get_key_by_rank(root,x+1)<<endl;
        else if(op==5) cout<<get_prev(root,x)<<endl;
        else cout<<get_next(root,x)<<endl;
    }
    return 0;
}

4.5.2 265. 营业额统计

代码：

/* Treep
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,INF=1e9;
int n;
struct Node
{
    int l,r;
    int key,val;
    int cnt,sz;
}tr[N];

int root,idx;

void pushup(int p)
{
    tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt;
}

int get_node(int key)   //创建新的节点
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].cnt=tr[idx].sz=1;
    return idx;
}

void zig(int &p)    // 右旋
{
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);
}

void zag(int &p)    // 左旋
{
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
    pushup(tr[p].l),pushup(p);
}

void build()
{
    get_node(-INF),get_node(INF);
    root=1,tr[1].r=2;
    pushup(root);

    if(tr[1].val<tr[2].val) zag(root);
}

void my_insert(int &p,int key)
{
    if(!p) p=get_node(key);
    else if(tr[p].key==key) tr[p].cnt++;
    else if(tr[p].key>key)
    {
        my_insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val) zig(p);
    }
    else
    {
        my_insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val) zag(p);
    }
    pushup(p);
}

int get_prev(int p,int key)     // 找到严格小于等于key的最大数
{
    if(!p) return -INF;
    if(tr[p].key>key) return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_next(int p,int key)     // 找到严格大于等于key的最小数
{
    if(!p) return INF;
    if(tr[p].key<key) return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}

int main()
{
    ios::sync_with_stdio(0);

    build();

    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int key;
        cin>>key;
        if(i==1) res+=key;
        else
        {
            int aj1=get_prev(root,key),aj2=get_next(root,key);
            if(aj1==-INF) aj1=INF;
            int aj=min(abs(aj1-key),abs(aj2-key));
            res+=aj;
        }
        my_insert(root,key);
    }

    cout<<res<<endl;

    return 0;
}
*/
//STL set lower_bound >=
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n;
set<int> st;
int main()
{
    cin>>n;
    int res=0;
    set<int>::iterator it;
    st.insert(-INF);
    st.insert(INF);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(i==0)
            res+=x;
        else
        {
            int aj1,aj2;
            it=st.lower_bound(x);
            aj1=*it;
            aj2=*(--it);
            res+=min(aj1-x,x-aj2);
        }
        st.insert(x);
    }
    cout<<res<<endl;
    return 0;
}

4.6 AC自动机

4.6.1 1282. 搜索关键词

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010,S=55,M=1000010;

int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],ne[N*S];

void my_insert()    //trie中插入节点
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++;
}

void build()
{
    queue<int> q;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i])
            q.push(tr[0][i]);
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];
            else
            {
                ne[p]=tr[ne[t]][i];
                q.push(p);
            }
        }
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(ne,0,sizeof ne);
        idx=0;

        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>str;
            my_insert();
        }

        build();

        cin>>str;

        int res=0;
        for(int i=0,j=0;str[i];i++)
        {
            int t=str[i]-'a';
            j=tr[j][t];

            int p=j;
            while(p)
            {
                res+=cnt[p];
                cnt[p]=0;
                p=ne[p];
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

4.6.2 1285. 单词

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;

int n;
int tr[N][26],f[N],idx;
int ne[N];
char str[N];
int id[210];
vector<int> seq;

void my_insert(int x)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
        f[p]++;
    }
    id[x]=p;
}

void build()
{
    queue<int> q;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i])
        {
            q.push(tr[0][i]);
            seq.push_back(tr[0][i]);
        }
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int &p=tr[t][i];
            if(!p) p=tr[ne[t]][i];
            else
            {
                ne[p]=tr[ne[t]][i];
                q.push(p);
                seq.push_back(p);
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>str;
        my_insert(i);
    }

    build();

    for(int i=seq.size()-1;i>=0;i--) f[ne[seq[i]]]+=f[seq[i]];

    for(int i=0;i<n;i++)
        cout<<f[id[i]]<<endl;

    return 0;
}

这篇关于【算法提高——第四讲】高级数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！