2741: 【FOTILE模拟赛】L - #include <Seter> - using namespace Orz;

2741: 【FOTILE模拟赛】L

Seter posted @ 2012年5月03日 20:21 in BZOJ with tags ChairTrie , 4225 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2741

RunID User Problem Result Memory Time Language Code_Length Submit_Time
249948 Seter 2741 Accepted 9620 kb 6680 ms C++/Edit 1362 B 2012-04-25 18:04:53

退役之前出道水题攒RP。好像卡了一些O(msqrtnlogn)的复杂度。。。我不是故意的。。。

我看神犇们的2K+代码,10S+时间,感觉是不是写傻了。。。或者是写了DYF神犇的神算法。。。

这种题首先感觉只有lg好像是不可做的,果断考虑分块。

分成长度为L的块,每块的第一个点叫做关键点,则总共有K=N/L个关键点。

处理出一个K*N的数组,表示每个关键点到之后每个点的答案。这个对于一个关键点是可以O(NlgN)弄出来的,用一般的trie就可以了,这个不会的话可以先去水水USACO再来。

然后对于一个询问(u,v),可以分解成(u,v)和(X,v),其中X是u之后的第一个关键点。

那么(X,v)已经处理出来了,剩下的就是u...X这O(L)个数在(u,v)中的max xor了。

问题转化为,求一段内与X的异或最大值。

这个东西用ChairTrie是可以随便减出来的。ChairTrie和ChairTree差不多,就是函数式Trie,从高到低处理X的某一位,如果可以往相反方向走,就走,就可以了。。。懒得说详细了,自己脑补吧。。。

复杂度是O(KNlgN+M(N/K)lgN),K=sqrtM,总复杂度为O(NsqrtMlgN),又快又好写  ><

PS:这题在SPOJ上叫做MAXOR我会告诉你们?

 

#include<cstdio>
#include<algorithm>
#include<cctype>
#define N 12002
#define M 80
using namespace std;
int n,m,ans[M+10][N],S,a[N],re;
struct CT{CT*c[2];int v;}null,*sT[N+1],**T=sT+1,st[N<<5],*stp;
inline int getint(){
	int re=0;char ch;
	while(!isdigit(ch=getchar()));re=ch-48;
	while(isdigit(ch=getchar()))re=re*10+ch-48;
	return re;
}inline int Q(CT*l,CT*r,int x){
	int a=0,k=31;
	while(k--){
		bool c=~x>>k&1;
		if(r->c[c]->v!=l->c[c]->v)a|=1<<k;else c=!c;
		r=r->c[c];l=l->c[c];
	}return a;
}inline CT*I(CT*R,int x){
	CT*r=stp;int k=31;
	while(k--){
		bool c=x>>k&1;
		stp->c[c]=stp+1;
		stp->c[!c]=R->c[!c];
		stp++->v=R->v+1;
		R=R->c[c];
	}stp->c[0]=stp->c[1]=&null;stp++->v=R->v+1;
	return r;
}inline void Init(int ans[N],int i){
	int o=0;stp=st;
	for(T[--i]=&null;++i!=n;T[i]=I(T[i-1],a[i]))o=ans[i]=max(o,Q(&null,T[i-1],a[i]));
}int main(){
	n=getint()+1;m=getint();S=n/M;null.c[0]=null.c[1]=&null;
	for(int i=0;++i!=n;)a[i]=a[i-1]^getint();
	for(int i=M;i--;)Init(ans[i],i*S);
	while(m--){
		re%=n-1;
		int l=(getint()+re)%(n-1),r=(getint()+re)%(n-1);
		if(l>r)l^=r^=l^=r;
		l--;r++;int bl=(l+S)/S;
		re=ans[bl][r];
		while(++l!=r&&l!=bl*S)re=max(re,Q(T[l],T[r],a[l]));
		printf("%d\n",re);
	}return 0;
}
By Seter
  • 无匹配
  • 无匹配
MyIdea 说:
2012年5月16日 21:42

Orz.......您会不会COT4的做法.......我和我们同学一起讨论了很久........但是一直不会做.......求拯救

Avatar_small
Seter 说:
2012年5月17日 12:46

我只会一种比较慢的可能会TLE的算法

MyIdea 说:
2012年5月17日 13:48

也可以......现在我第三四个操作不会搞

MyIdea 说:
2012年5月20日 11:15

感觉这个题的预处理可以再快一点的?

applepi 说:
2012年5月20日 13:30

我被D得一逼……

Avatar_small
Seter 说:
2012年5月21日 07:25

您的神方法我都看不懂……被您D出翔了……

MyIdea 说:
2012年6月08日 20:26

Seter悄悄的告诉你,Fotile没有卡掉nlog^2(n)

MyIdea 说:
2012年6月08日 20:29

我是指COT4


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee