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

前置知识

线段树
可持久化01trie

第一道线段树分治题

线段树分治是一种按时间分治的方法

由于其结构类似线段树，被称为线段树分治

题意坑点

下面这个讨论里叙述得很清楚了，这里不再赘述

传送门

线段树分治核心思想

将询问与修改离线

可能有这几种情况

单点修改，单点查询

这个完全不需要线段树分治吧
单点修改，区间查询（例如本题）

我们可以将每一个修改记录在包含该点的线段树上的 $log$ 个节点上

把查询分解成 $log$ 个线段树上的区间记录在这 $log$ 个节点上

由于查询的区间包括了我们记录下的每一个小区间

而在每一个线段树区间记录下的修改都会影响这个区间

正确性显然

那么我们遍历一边整棵线段树，在每个节点进行该结点所记录的修改，再进行该结点的询问即可
区间修改，单点查询

将每一个修改分解成 $log$ 个区间记录在线段树这 $log$ 个节点上

将每一个查询记录在包含该点的线段树上的 $log$ 个节点上

遍历线段树类比情况2即可
区间修改，区间查询

结合情况2，3就是这个东西

我们还需注意在所有中，应该是进行完了修改就直接查询

情况2中应在未递归时便撤销所有修改

本题做法

我们把答案分两个部分来求

第一部分

先用可持久化trie解决所有商店的特殊商品对询问的贡献

这一部分不清楚的可以去学习下最大异或和

第二部分

由于每个询问只能买某一段时间内的商品

暴力的对所有区间做的时间复杂度可达 $O(q\times n\times log T)$ ， $T$ 为值域

我们考虑刚刚学到的线段树分治

将所有修改和询问按照上述的做法记录在线段树上

进行线段树分治

inline void solve(register int k,register int l,register int r){
	Insert(k);//将所有修改加进可持久化01trie中
	if(l==r){
		for(register int i=0;i<que[k].size();i++){
			register int id=que[k][i].id;
			register int x=que[k][i].l,y=que[k][i].r,val=que[k][i].x;
			ans[id]=max(ans[id],query(x,y,val));
		}
        	//处理询问
		Delete(k);//清空可持久化01trie
		return ;
	}
	register int mid=l+((r-l)>>1);
	for(register int i=0;i<que[k].size();i++){
		register int id=que[k][i].id;
		register int x=que[k][i].l,y=que[k][i].r,val=que[k][i].x;
		ans[id]=max(ans[id],query(x,y,val));
	}
	Delete(k);
    //一定要先清空，这样做的原因应该比较显然
	solve(k<<1,l,mid);
	solve(k<<1|1,mid+1,r);
	return ;
}

这里处理可持久化01trie时需要用到一些叫常用的技巧

由于 $upd$ 的序列商店编号不连续，我们需要离散化

在query时需要二分一下

复杂度分析

根据上述的线段树分治需要记录的东西很容易看出空间复杂度 $nlogn+nlogT$

由于我们会遍历所有记录的询问和查询共 $nlogn$ 个

无论是可持久化01trie的插入还是询问时间复杂度均为 $O(logn)$

故总复杂度 $O(nlog^2n)$

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005,maxm=100005;
struct Upd{
	int s,v;
	bool operator <(Upd i)const{
		return s<i.s;
	}
};
struct Que{
	int id,l,r,x;
};
int ans[maxm];
struct trie{
	int s[2];
	int b;
}t[20*maxm];
int tot=0;
int rt[maxn];
int lp[maxn],rp[maxn];
int W=0;
int shop[maxn];
bool vis[maxm];
vector<Upd>upd[maxm<<2];
vector<Que>que[maxm<<2];
inline int read(){
    register int x=0,y=1;
    register char ch=getchar();
    while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
    while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
inline void write(register int x){
	if(!x)return ;
	write(x/10);
	putchar(x%10+'0');
	return ;
}
inline void clear(register int k){
	t[k].s[0]=t[k].s[1]=t[k].b=0;
	return ;
}
inline int newnode(){
	clear(tot+1);
	return ++tot;
}
inline void ins(register int x,register int y,register int val){
	if(!rt[x])rt[x]=newnode();
	register int k=rt[x],l=rt[y];
	t[k].b=x;
	for(register int i=16;i>=0;i--){
		register bool to=((val&(1<<i))>>i);
		if(!t[k].s[to])t[k].s[to]=newnode();
		t[k].s[to^1]=t[l].s[to^1];
		k=t[k].s[to];
		t[k].b=x;
		l=t[l].s[to];
	}
	return ;
}
inline int search(register int x){
	register int l=0,r=W+1;
	while(l+1<r){
		register int mid=l+((r-l)>>1);
		if(shop[mid]<=x)
			l=mid;
		else
			r=mid;
	}
	return l;
}
inline int query(register int l,register int r,register int val){
	register int lft=l;
	l=search(l);
	r=search(r);
	if(shop[l]<lft)l++;
	l=lp[l];r=rp[r];
	register int k=rt[r],ans=0;
	for(register int i=16;i>=0;i--){
		register bool to=((((val&(1<<i)))>>i)^1);
		if(t[k].s[to]==0||t[t[k].s[to]].b<l)to^=1;
		else ans+=(1<<i);
		k=t[k].s[to];
	}
	return ans;
}
inline void modify1(register int k,register int l,register int r,register int x,register int p,register int val){
	if(l>x||r<x)return ;
	if(l==r){
		upd[k].push_back((Upd){p,val});
		return ;
	}
	register int mid=l+((r-l)>>1);
	modify1(k<<1,l,mid,x,p,val);
	modify1(k<<1|1,mid+1,r,x,p,val);
	upd[k].push_back((Upd){p,val});
	return ;
}
inline void modify2(register int k,register int l,register int r,register int x,register int y,register int id,register int p,register int q,register int val){
	if(y<x)return ;
	if(l>y||r<x)return ;
	if(l>=x&&r<=y){
		que[k].push_back((Que){id,p,q,val});
		return ;
	}
	register int mid=l+((r-l)>>1);
	modify2(k<<1,l,mid,x,y,id,p,q,val);
	modify2(k<<1|1,mid+1,r,x,y,id,p,q,val);
	return ;
}
inline void Insert(register int k){
	sort(upd[k].begin(),upd[k].end());
	if(upd[k].size()){
		ins(1,0,upd[k][0].v);
		W=1;
		shop[W]=upd[k][0].s;
		lp[W]=1;
	}
	for(register int i=1;i<upd[k].size();i++){
		register int p1=upd[k][i].s,p2=upd[k][i-1].s;
		ins(i+1,i,upd[k][i].v);
		if(p1>p2){
			W++;
			shop[W]=p1;
			rp[W-1]=i;lp[W]=i+1;
		}
	}
	rp[W]=upd[k].size();
	return ;
}
inline void Delete(register int k){
	for(register int i=1;i<=tot;i++)clear(i);
	for(register int i=1;i<=upd[k].size();i++)rt[i]=0;
	tot=0;
	return ;
}
inline void solve(register int k,register int l,register int r){
	Insert(k);
	if(l==r){
		for(register int i=0;i<que[k].size();i++){
			register int id=que[k][i].id;
			register int x=que[k][i].l,y=que[k][i].r,val=que[k][i].x;
			ans[id]=max(ans[id],query(x,y,val));
		}
		Delete(k);
		return ;
	}
	register int mid=l+((r-l)>>1);
	for(register int i=0;i<que[k].size();i++){
		register int id=que[k][i].id;
		register int x=que[k][i].l,y=que[k][i].r,val=que[k][i].x;
		ans[id]=max(ans[id],query(x,y,val));
	}
	Delete(k);
	solve(k<<1,l,mid);
	solve(k<<1|1,mid+1,r);
	return ;
}
int main(){
    freopen("[FJOI2015]火星商店问题.in","r",stdin);
    freopen("[FJOI2015]火星商店问题.out","w",stdout);
   	register int n,m;
	n=read();m=read();
	clear(0);
	for(register int i=1;i<=n;i++){
		W++;
		shop[W]=i;
		lp[W]=i;rp[W]=i;
		ins(i,i-1,read());
	}
	register int day=1;
	for(register int i=1;i<=m;i++){
		register int opt,l,r,x,d;
		opt=read();l=read();r=read();
		if(!opt){
			if(i>1)day++;
			modify1(1,1,m,day,l,r);
		}
		else{
			vis[i]=1;
			x=read();d=read();
			modify2(1,1,m,max(day-d+1,1),day,i,l,r,x);
			ans[i]=query(l,r,x);
		}
	}
	for(register int i=1;i<=tot;i++)clear(i);
	for(register int i=1;i<=n;i++)rt[i]=0;
	tot=0;
	solve(1,1,m);
	for(register int i=1;i<=m;i++)
		if(vis[i]){
			if(ans[i])write(ans[i]);
			else putchar('0');
			putchar('\n');
		}
    return 0;
}