本文最后更新于:2020年4月20日 上午

对于一类区间询问问题,如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去,当前区间[l,r][l , r]中点为midmid,那么我们将所有的询问分成三类,一类包括midmid这个点,一类完全在左侧,一类完全在右侧,我们只要在当前这层解决第一类的所有询问,后两类分治下去即可。怎么快速的求呢?方法也非常简单,因为信息可以快速合并,那么我们以midmid为界,往前处理出所有后缀信息,往后处理出所有前缀信息,对于一个跨过midmid的询问,拿两部分拼一下就算出答案了!

比在线算法优秀的地方在于可以优雅的去掉询问数所乘的log。

练习题目

1.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest J. Subsequence Sum Queries

考虑背包dp,如果用普通的线段树,时间复杂度O((n+q)m2logn)O((n+q)m^2logn),因为拆成logn个区间,要完全合并两个背包log次,合并一次(循环卷积)复杂度是O(m2)O(m^2),必T无疑。用优秀的分治就可以降到O(m(nlogn+q))O(m(nlogn+q))

#include<bits/stdc++.h>
using namespace std;
#define N 200010
const int mod=1e9+7;
struct node
{
    int l,r,o;
} t[N],tmp[N];
int n,m,len;
int sub[N][22],pre[N][22];
int a[N],ans[N];
int calc(int *f,int *g)
{
    int ans=0;
    for(int i=0;i<m;++i)
    {
        ans+=1LL*f[i]*g[(m-i)%m]%mod;
        if(ans>=mod) ans-=mod;
    }
    return ans;
}
void solve(int l,int r,int L,int R)
{
    if(l>r||L>R) return ;
    int mid=l+r>>1;
    int x=L-1,y=R+1,now=L,j;
    for(int i=L;i<=R;++i)
        if(t[i].r<mid) tmp[++x]=t[i];
        else if(t[i].l>mid) tmp[--y]=t[i];
        else t[now++]=t[i];

    sub[mid+1][0]=1;
    for(int i=1;i<m;++i) sub[mid+1][i]=0;
    for(int i=mid;i>=l;--i)
        for(int j=0;j<m;++j)
            sub[i][j]=(sub[i+1][j]+sub[i+1][(j-a[i]+m)%m])%mod;

    pre[mid][0]=1;
    for(int i=1;i<m;++i) pre[mid][i]=0;
    for(int i=mid+1;i<=r;++i)
        for(int j=0;j<m;++j)
            pre[i][j]=(pre[i-1][j]+pre[i-1][(j-a[i]+m)%m])%mod;

    for(int i=L;i<now;++i)
        ans[t[i].o]=calc(sub[t[i].l],pre[t[i].r]);

    for(int i=L;i<=x;++i) t[i]=tmp[i];
    for(int i=y;i<=R;++i) t[i]=tmp[i];
    solve(l,mid-1,L,x);
    solve(mid+1,r,y,R);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        a[i]%=m;
    }
    scanf("%d",&len);
    for(int i=1;i<=len;++i)
    {
        scanf("%d%d",&t[i].l,&t[i].r);
        t[i].o=i;
    }
    solve(1,n,1,len);
    for(int i=1;i<=len;++i)
        printf("%d\n",ans[i]);
    return 0;
}

2.2018 Multi-University Training Contest 3 Problem J. Rectangle Radar Scanner

对x轴分治,对于y用线段树维护一下就好了

时间复杂度O(nlog2n+mlogn)O(nlog^2n+mlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
#define M 1000010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int INF=0x3f3f3f3f;
struct segment
{
    int l,r;
    int min,max,prod;
} t[N<<2];
struct REC
{
    int xl,xr,yl,yr,o;
} rec[M],tmp[M];
int n,m,K;
int mn[M],mx[M],prod[M];
pair<int,int> val[N];
bool cmpl(const REC &a,const REC &b)
{
    return a.xl>b.xl;
}
bool cmpr(const REC &a,const REC &b)
{
    return a.xr<b.xr;
}
void push_up(int p)
{
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
    t[p].prod=1LL*t[ls(p)].prod*t[rs(p)].prod%K;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    t[p].min=INF;
    t[p].max=-INF;
    t[p].prod=1;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
}
void insert(int p,int x,int y)
{
    if(t[p].l==t[p].r)
    {
        t[p].min=min(t[p].min,y);
        t[p].max=max(t[p].max,y);
        t[p].prod=1LL*t[p].prod*y%K;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) insert(ls(p),x,y);
    else insert(rs(p),x,y);
    push_up(p);
}
void ask(int p,int x)
{
    if(rec[x].yl<=t[p].l && t[p].r<=rec[x].yr)
    {
        int o=rec[x].o;
        mn[o]=min(mn[o],t[p].min);
        mx[o]=max(mx[o],t[p].max);
        prod[o]=1LL*prod[o]*t[p].prod%K;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(rec[x].yl<=mid) ask(ls(p),x);
    if(rec[x].yr>mid) ask(rs(p),x);
}
void travel(int p)
{
    if(t[p].min==INF) return;
    t[p].min=INF;
    t[p].max=-INF;
    t[p].prod=1;
    if(t[p].l==t[p].r) return;
    travel(ls(p));
    travel(rs(p));
}
void solve(int l,int r,int L,int R)
{
    if(l>r||L>R) return;
    int mid=l+r>>1;
    int x=L-1,y=R+1,now=L,j;
    for(int i=L;i<=R;++i)
        if(rec[i].xr<mid) tmp[++x]=rec[i];
        else if(rec[i].xl>mid) tmp[--y]=rec[i];
        else rec[now++]=rec[i];
    sort(rec+L,rec+now,cmpl);
    j=mid+1;
    for(int i=L;i<now;++i)
    {
        while(j>rec[i].xl)
        {
            --j;
            insert(1,val[j].first,val[j].second);
        }
        ask(1,i);
    }
    travel(1);
    sort(rec+L,rec+now,cmpr);
    j=mid;
    for(int i=L;i<now;++i)
    {
        while(j<rec[i].xr)
        {
            ++j;
            insert(1,val[j].first,val[j].second);
        }
        ask(1,i);
    }
    travel(1);
    for(int i=L;i<=x;++i) rec[i]=tmp[i];
    for(int i=y;i<=R;++i) rec[i]=tmp[i];
    solve(l,mid-1,L,x);
    solve(mid+1,r,y,R);
}
void read()
{
    int a[2],b[2],c[2],d[2];
    int p,q,r,mod;
    scanf("%d%d%d%d%d%d%d%d%d%d",&m,a,b,c,d,&p,&q,&r,&mod,&K);
    for(int i=1;i<=m;++i)
    {
        a[i&1]=(1LL*p*a[(i&1)^1]+1LL*q*b[(i&1)^1]+r)%mod;
        b[i&1]=(1LL*p*b[(i&1)^1]+1LL*q*a[(i&1)^1]+r)%mod;
        c[i&1]=(1LL*p*c[(i&1)^1]+1LL*q*d[(i&1)^1]+r)%mod;
        d[i&1]=(1LL*p*d[(i&1)^1]+1LL*q*c[(i&1)^1]+r)%mod;
        rec[i].xl=min(a[i&1]%n,b[i&1]%n)+1;
        rec[i].xr=max(a[i&1]%n,b[i&1]%n)+1;
        rec[i].yl=min(c[i&1]%n,d[i&1]%n)+1;
        rec[i].yr=max(c[i&1]%n,d[i&1]%n)+1;
        rec[i].o=i;
        mn[i]=INF;
        mx[i]=-INF;
        prod[i]=1;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            val[i]=make_pair(x,y);
        }
        build(1,1,n);
        read();
        solve(1,n,1,m);
        long long ans=0;
        for(int i=1;i<=m;++i)
        if(mn[i]!=INF)
            ans+=prod[i]^mx[i]^mn[i];
        printf("%lld\n",ans);
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

小清新线段树 上一篇
高维前缀和 下一篇