【洛谷P4585】 [FJOI2015]火星商店问题 线段树分治+可持久化trie

感觉这个线段树分治和整体二分几乎相同啊~  

code: 

#include <bits/stdc++.h>    
#define MAX 100300 
#define ll long long 
#define lson now<<1 
#define rson now<<1|1       
#define setIO(s) freopen(s".in","r",stdin)    
using namespace std; 
struct Buy  {int s,v,t; }q[MAX],tmp1[MAX],tmp2[MAX];   
struct ASK  {int l,r,tl,tr,x; }p[MAX];   
bool cmp(Buy a,Buy b) { return a.s<b.s; }    
int rt[MAX]; 
namespace Trie 
{ 
    struct Trie { int son[2],w; } t[MAX<<5];   
    int tot,rt[MAX];  
    void insert(int &x,int ff,int w,int now) 
    {
        t[x=++tot]=t[ff];  t[x].w++;  
        if(now==-1)  return;   
        bool c=(w&(1<<now));      
        insert(t[x].son[c],t[ff].son[c],w,now-1);  
    }   
    int Query(int l,int r,int w,int now) 
    {
        if(now==-1)   return 0; 
        bool c=w&(1<<now);   
        int tmp=t[t[r].son[c^1]].w-t[t[l].son[c^1]].w;  
        if(tmp)   return Query(t[l].son[c^1],t[r].son[c^1],w,now-1)+(1<<now);   
        else return Query(t[l].son[c],t[r].son[c],w,now-1);   
    }
};   
int n,m,ans[MAX];  
vector<int>seg[MAX<<2];   
int cnt1,cnt2;   
void Modify(int now,int l,int r,int L,int R,int x) 
{
    if(L>R)   return;    
    if(l>=L&&r<=R)   { seg[now].push_back(x);  return; }  
    int mid=(l+r)>>1;   
    if(L<=mid)   Modify(lson,l,mid,L,R,x);  
    if(R>mid)    Modify(rson,mid+1,r,L,R,x);   
} 
int S[MAX],top;   
int find(int x) 
{
    int l=1,r=top,re=0; 
    while(l<=r) 
    {
        int mid=(l+r)>>1;  
        if(S[mid]<=x)   re=mid,l=mid+1;  
        else r=mid-1;  
    } 
    return re;  
} 
void sol(int now,int L,int R) 
{
    top=Trie::tot=0;  
    for(int i=L;i<=R;++i) 
    {
        S[++top]=q[i].s;  
        Trie::insert(rt[top],rt[top-1],q[i].v,17);    
    } 
    for(int i=0;i<seg[now].size();++i) 
    {
        int k=seg[now][i];   
        int l=find(p[k].l-1), r=find(p[k].r);   
        ans[k]=max(ans[k],Trie::Query(rt[l],rt[r],p[k].x,17));    
    }
} 
void divide(int now,int l,int r,int L,int R) 
{
    if(L>R)  return;  
    int mid=(l+r)>>1,t1=0,t2=0;  
    sol(now,L,R);  
    if(l==r)  return; 
    for(int i=L;i<=R;++i) 
    {
        if(q[i].t<=mid)    tmp1[++t1]=q[i]; 
        else tmp2[++t2]=q[i]; 
    }  
    for(int i=1;i<=t1;++i)  q[i+L-1]=tmp1[i]; 
    for(int i=1;i<=t2;++i)  q[i+L-1+t1]=tmp2[i];   
    divide(lson,l,mid,L,L+t1-1);   
    divide(rson,mid+1,r,L+t1,R);   
}
int main() 
{    
    // setIO("input");  
    int i,j;     
    scanf("%d%d",&n,&m);  
    for(i=1;i<=n;++i)  
    {
        int x; 
        scanf("%d",&x); 
        Trie::insert(rt[i],rt[i-1],x,17);     
    } 
    for(i=1;i<=m;++i) 
    {
        int opt; 
        scanf("%d",&opt);  
        if(!opt) 
        { 
            int s,v; 
            scanf("%d%d",&s,&v); 
            ++cnt1;  
            q[cnt1]=(Buy){s,v,cnt1};   
        }
        else 
        { 
            int l,r,x,d; 
            scanf("%d%d%d%d",&l,&r,&x,&d);   
            ans[++cnt2]=Trie::Query(rt[l-1],rt[r],x,17);   
            p[cnt2]=(ASK){l,r,max(1,cnt1-d+1),cnt1,x};              
        }
    }    
    for(i=1;i<=cnt2;++i)   Modify(1,1,cnt1,p[i].tl,p[i].tr,i);   
    sort(&q[1],&q[cnt1+1],cmp); 
    divide(1,1,cnt1,1,cnt1);    
    for(int i=1;i<=cnt2;++i)      printf("%d
",ans[i]);    
    return 0; 
}