题解 P4585 【[FJOI2015]火星商店问题】

· · 题解

在 Trie 上走的过程相当于是每次询问一个值域区间内是否有值，那么可以用整体二分来做这个过程. 先不考虑一开始的那些东西，那么对于分治到的某一个区间需要求出位置在 [l,r] 内时间在 [L,R] 内是否有点，这是个经典二维数点问题，可以离线做到 O(len\log len)，len 是点和询问的数量之和. 于是这部分的整体复杂度是 O(n\log ^2 n). 对于一开始的东西再做一次整体二分，那么这次需要只求出位置在 [l,r] 内是否有点. 可以做到 O(n\log n)，但为了简便还是用实现成 O(n\log ^2n).

该做法的时间复杂度是 O(n\log ^2n)，而空间复杂度达到了线性.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+500;
int ans1[N],ans2[N],n,m,qn,cn;
struct BIT
{
    int a[N];
    void update(int x,int w){for(;x<=n;x+=x&-x)a[x]+=w;}
    int query(int x){int ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}
    int query(int l,int r){return query(r)-query(l-1);}
}s,sl,sr;
struct WNode{int l,L,w;}w[N],c[N],tmpwl[N],tmpwr[N];
struct QNode{int l,r,L,R,w,id,exi;}q[N],ql[N],qr[N],tmpq[N<<1];

void solve1(int wl,int wr,int l,int r,int L,int R,int dep)
{
    if(l>r||L>R)return;
    if(wl==wr)return;
    int mid=(wl+wr)>>1;int wnl=0,wnr=0,qnl=0,qnr=0;
    for(int i=l;i<=r;i++)
        if(w[i].w<=mid)
            tmpwl[++wnl]=w[i],sl.update(w[i].l,1);
        else tmpwr[++wnr]=w[i],sr.update(w[i].l,1);
    for(int i=L;i<=R;i++)
        if(q[i].w>>dep&1)
        {
            if(sl.query(q[i].l,q[i].r))ql[++qnl]=q[i],ans1[q[i].id]|=1<<dep;
            else qr[++qnr]=q[i];
        }
        else
        {
            if(sr.query(q[i].l,q[i].r))qr[++qnr]=q[i],ans1[q[i].id]|=1<<dep;
            else ql[++qnl]=q[i];
        }
    for(int i=l;i<=r;i++)
        if(w[i].w<=mid)sl.update(w[i].l,-1);
        else sr.update(w[i].l,-1);
    for(int i=1;i<=wnl;i++)w[l+i-1]=tmpwl[i];
    for(int i=1;i<=wnr;i++)w[l+wnl+i-1]=tmpwr[i];
    for(int i=1;i<=qnl;i++)q[L+i-1]=ql[i];
    for(int i=1;i<=qnr;i++)q[L+qnl+i-1]=qr[i];
    solve1(wl,mid,l,l+wnl-1,L,L+qnl-1,dep-1);
    solve1(mid+1,wr,l+wnl,r,L+qnl,R,dep-1);
}
int cmpq(const QNode &a,const QNode &b){return a.L<b.L;}
void calc(const WNode w[],int wn,QNode q[],int qn)
{
    int tn=0;
    for(int i=1;i<=qn;i++)
    {
        q[i].exi=0;
        tmpq[++tn]=q[i],tmpq[tn].L=q[i].L-1,tmpq[tn].w=-1,tmpq[tn].id=i;
        tmpq[++tn]=q[i],tmpq[tn].L=q[i].R,tmpq[tn].w=1,tmpq[tn].id=i;
    }
    sort(tmpq+1,tmpq+tn+1,cmpq);
    int j=1;
    for(int i=1;i<=tn;i++)
    {
        while(j<=wn&&w[j].L<=tmpq[i].L)s.update(w[j].l,1),++j;
        q[tmpq[i].id].exi+=tmpq[i].w*s.query(tmpq[i].l,tmpq[i].r);
    }
    for(int i=1;i<j;i++)s.update(w[i].l,-1);
}
void solve2(int wl,int wr,int l,int r,int L,int R,int dep)
{
    if(l>r||L>R)return;
    if(wl==wr)return;
    int mid=(wl+wr)>>1;int wnl=0,wnr=0,qnl=0,qnr=0;
    for(int i=l;i<=r;i++)
        if(c[i].w<=mid)tmpwl[++wnl]=c[i];
        else tmpwr[++wnr]=c[i];
    for(int i=L;i<=R;i++)
        if(q[i].w>>dep&1)ql[++qnl]=q[i];
        else qr[++qnr]=q[i];
    calc(tmpwl,wnl,ql,qnl),calc(tmpwr,wnr,qr,qnr);
    int nl=L,nr=R;
    for(int i=1;i<=qnl;i++)
        if(ql[i].exi)q[nl++]=ql[i],ans2[ql[i].id]|=1<<dep;
        else q[nr--]=ql[i];
    for(int i=1;i<=qnr;i++)
        if(qr[i].exi)q[nr--]=qr[i],ans2[qr[i].id]|=1<<dep;
        else q[nl++]=qr[i];
    for(int i=1;i<=wnl;i++)c[l+i-1]=tmpwl[i];
    for(int i=1;i<=wnr;i++)c[l+wnl+i-1]=tmpwr[i];
    solve2(wl,mid,l,l+wnl-1,L,nr,dep-1),solve2(mid+1,wr,l+wnl,r,nl,R,dep-1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i].w),w[i].l=i;
    qn=0,cn=0;int tim=0;
    for(int i=1,opt=-1;i<=m;i++)
    {
        scanf("%d",&opt);
        if(opt==0)
        {
            ++tim;
            ++cn,scanf("%d%d",&c[cn].l,&c[cn].w),c[cn].L=tim;
        }
        else ++qn,scanf("%d%d%d%d",&q[qn].l,&q[qn].r,&q[qn].w,&q[qn].L),q[qn].R=tim,q[qn].L=tim-q[qn].L+1,q[qn].id=qn;
    }
    solve1(0,131071,1,n,1,qn,16);
//    for(int i=1;i<=qn;i++)cout<<q[i].id<<" ";puts("");
    solve2(0,131071,1,cn,1,qn,16);
//    for(int i=1;i<=qn;i++)cout<<ans1[i]<<" ";puts("");
//    for(int i=1;i<=qn;i++)cout<<ans2[i]<<" ";puts("");
    for(int i=1;i<=qn;i++)printf("%d\n",max(ans1[i],ans2[i]));
}