火星商店问题[FJOI2015][线段树分治][01Trie]

题目

dark

思路

对于线段树分治“时间”的选择这道题很有技巧，我们可以分时间和位置两个方面考虑：

1. 时间维度除了每个店的特殊商品外修改都是单点，询问是区间
2. 位置，修改操作都是单点，询问是区间

如果用时间维度进行分治也是可做的，这里选择位置作为线段树分治的“时间”
这道题比较有特点，是区间查询，我们将询问裂成 $O(nlogn)$ 段，那修改操作怎么办呢，都是单点的？
利用标记永久化即可，对于一次修改将路径上的 $logn$ 个点都加入这个 $val$


这就能保证对于询问 $[L,R]$ 中裂开的节点都有对自区间的 $val$ 了（不管时间对不对）
线段树的每个节点是一颗 $Trie$
查询如果只是异或最大值直接 $01Trie$ 即可，但是还有时间限制 $[L,R]$
考虑将所有操作按右端点排序（实际过程中按输入顺序已经有序了）再插入
那么对 $Trie$ 节点额外增加 $Ma{x}_u$ 表示该子树内最晚插入时间，询问时候判断一些即可
时间复杂度线段树分治修改每次影响 $logn$ 个节点，每个节点是 $01Trie$ 插入又是一个 $logn$ ，每个询问分成 $logn$ 个节点，每个节点字典树中查询 $logn$
总是时间复杂度为 $O(nlo{g}^{2}n)$

代码

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline LL read() {
    bool f=0;LL x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define lch (u<<1)
#define rch (u<<1|1)
#define MAXN 100000
#define INF 0x3f3f3f3f
struct node{
    int type,tl,tr,pl,pr,val,id;friend bool operator < (node a,node b){
    return a.tr==b.tr?a.type<b.type:a.tr<b.tr;}
}Q[MAXN+5];
int qcnt,ans[MAXN+5];
vector<node> tree[5*MAXN+5];
void Insert_Seg(int u,int L,int R,node p){
    if(p.type==0)tree[u].push_back(p);if(p.pl<=L&&R<=p.pr){
    if(p.type==1)tree[u].push_back(p);return ;}int Mid=(L+R)>>1;if(p.pl<=Mid)Insert_Seg(lch,L,Mid,p);if(Mid+1<=p.pr)Insert_Seg(rch,Mid+1,R,p);return ;
}
int ncnt,Root,ch[30*MAXN+5][2],Max[30*MAXN+5];
void Init(){
    for(int i=1;i<=ncnt;i++)ch[i][0]=ch[i][1]=Max[i]=0;ncnt=Root=1;return ;
}
void Insert(int pos,int val){
    int u=Root;for(int i=19;i>=0;i--){
    int t=(val>>i)&1;if(!ch[u][t])ch[u][t]=++ncnt;u=ch[u][t];Max[u]=max(Max[u],pos);}return ;
}
int Query(int pos,int val){
    int u=Root,ret=0;for(int i=19;i>=0;i--){
    int t=((val>>i)&1)^1;if(ch[u][t]&&pos<=Max[ch[u][t]])ret+=(1<<i),u=ch[u][t];else u=ch[u][t^1];}return ret;
}
void DFS(int u,int L,int R){
    Init();for(int i=0;i<(int)tree[u].size();i++){
    node p=tree[u][i];if(p.id==1){
    i++;i--;}if(p.type==0)Insert(p.tr,p.val);elseans[p.id]=max(ans[p.id],Query(p.tl,p.val));}if(L==R)return ;int Mid=(L+R)>>1;DFS(lch,L,Mid),DFS(rch,Mid+1,R);return ;
}
int main(){
    int n=read(),m=read(),day=1,cnt=0;for(int i=1;i<=n;i++)Insert_Seg(1,1,n,(node){
    0,1,m+1,i,i,read(),0});for(int i=1;i<=m;i++){
    int opt=read();node p;if(opt==0){
    day++;int s=read(),v=read();p=(node){
    0,day,day,s,s,v,0};}else{
    int pl=read(),pr=read(),x=read(),tl=day-read()+1,tr=day;p=(node){
    1,tl,tr,pl,pr,x,++cnt};}Insert_Seg(1,1,n,p);}DFS(1,1,n);for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);return 0;
}

思考

对于线段树分治本身已经可以保证"时间"有序，那么尝试离线后排序使得另外一些参数有序不失为好办法