【算法提高——第四讲】高级数据结构

2021-08-27 22:09:45

文章目录

第四章高级数据结构

第四章高级数据结构

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;
}

码农公寓

文章目录

第四章 高级数据结构

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. 单词

相关文章

第四章高级数据结构