一类区间分治技巧

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

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

练习题目

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

考虑背包dp，如果用普通的线段树，时间复杂度$O((n+q)m^2logn)$，因为拆成logn个区间，要完全合并两个背包log次，合并一次(循环卷积)复杂度是$O(m^2)$，必T无疑。用优秀的分治就可以降到$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(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;
}