luoguP4585 [FJOI2015]火星商店问题

题意

显然商店编号的限制能用可持久化trie解决。

特殊的商品预先判掉就好了，现在只考虑普通的商品。

发现商品的时间是单点，询问时一段时间，于是将询问区间在线段树上拆成\(log\)个区间，分别放上该询问。

之后dfs整颗线段树，先计算当前节点上的询问，之后将商品按照出现时间是在中点左右分成两类递归。

code:

#include<bits/stdc++.h>

using namespace std;

#define ls(p) (p<<1)

#define rs(p) (p<<1|1)

const int maxn=1e5+10;

int n,m,cnt1,cnt2,tot,num;

int ans[maxn],root[maxn],cnt[maxn*40],a[maxn];

int trie[maxn*40][2];

struct Buy{int tim,x,k;}buy[maxn],tmp1[maxn],tmp2[maxn];

struct Query{int sl,sr,tl,tr,k;}qr[maxn];

vector<int>seg[maxn<<2];

inline bool cmp(Buy a,Buy b){return a.x<b.x;}

void insert(int pre,int& now,int t,int k)

{

	now=++tot;

	trie[now][0]=trie[pre][0];trie[now][1]=trie[pre][1];cnt[now]=cnt[pre]+1;

	if(t<0)return;

	int c=(k>>t)&1;

	insert(trie[pre][c],trie[now][c],t-1,k);

}

int query(int pre,int now,int t,int k)

{

	if(t<0)return 0;

	int c=(k>>t)&1;

	if(cnt[trie[now][c^1]]-cnt[trie[pre][c^1]])return (1<<t)|query(trie[pre][c^1],trie[now][c^1],t-1,k);

	else return query(trie[pre][c],trie[now][c],t-1,k);

}

void change(int p,int l,int r,int ql,int qr,int id)

{

	if(ql>qr)return;

	if(l>=ql&&r<=qr){seg[p].push_back(id);return;}

	int mid=(l+r)>>1;

	if(ql<=mid)change(ls(p),l,mid,ql,qr,id);

	if(qr>mid)change(rs(p),mid+1,r,ql,qr,id);

}

inline int find(int x)

{

	int l=0,r=num,res;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(a[mid]<=x)res=mid,l=mid+1;

		else r=mid-1;

	}

	return res;

}

inline void calc(int p,int L,int R)

{

	tot=num=0;

	for(int i=L;i<=R;i++)

	{

		a[++num]=buy[i].x;

		insert(root[num-1],root[num],18,buy[i].k);

	}

	for(unsigned int i=0;i<seg[p].size();i++)

	{

		int id=seg[p][i],l,r;

		l=find(qr[id].sl-1),r=find(qr[id].sr);

		ans[id]=max(ans[id],query(root[l],root[r],18,qr[id].k));

	}

}

void solve(int p,int l,int r,int ql,int qr)

{

	if(ql>qr)return;

	calc(p,ql,qr);

	if(l==r)return;

	int mid=(l+r)>>1,cntl=0,cntr=0;

	for(int i=ql;i<=qr;i++)

	{

		if(buy[i].tim<=mid)tmp1[++cntl]=buy[i];

		else tmp2[++cntr]=buy[i];

	}

	for(int i=1;i<=cntl;i++)buy[ql+i-1]=tmp1[i];

	for(int i=1;i<=cntr;i++)buy[ql+cntl+i-1]=tmp2[i];

	solve(ls(p),l,mid,ql,ql+cntl-1);solve(rs(p),mid+1,r,ql+cntl,qr);

}

int main()

{

	//freopen("test.in","r",stdin);

	//freopen("test.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		int x;scanf("%d",&x);

		insert(root[i-1],root[i],18,x);

	}

	for(int i=1;i<=m;i++)

	{

		int op;scanf("%d",&op);

		if(!op)

		{

			int x,k;scanf("%d%d",&x,&k);

			cnt1++;buy[cnt1]=(Buy){cnt1,x,k};

		}

		else

		{

			int sl,sr,k,d;scanf("%d%d%d%d",&sl,&sr,&k,&d);

			qr[++cnt2]=(Query){sl,sr,max(1,cnt1-d+1),cnt1,k};

			ans[cnt2]=query(root[sl-1],root[sr],18,k);

		}

	}

	for(int i=1;i<=cnt2;i++)change(1,1,cnt1,qr[i].tl,qr[i].tr,i);

	sort(buy+1,buy+cnt1+1,cmp);

	solve(1,1,cnt1,1,cnt1);

	for(int i=1;i<=cnt2;i++)printf("%d\n",ans[i]);

	return 0;

}

巴特西

luoguP4585 [FJOI2015]火星商店问题

题意

最新文章

热门文章