3166: [Heoi2013]Alo
这题大意是给你一个序列，求一个最优区间[l,r],使其中的次大值xor上区间中任意另一个数，使xor和最大（对不起，我又语死了）
这题其实暴力能a= =
但是写暴力太没节操了（- -b）
网上似乎没有除暴力以外的题解= =我来写一篇吧= =
我的大致想法就是用线段树维护i前面第二个比他大的值f[i]（这里可以用权值线段树），然后用函数式trie找(f[i]+1,i)上与a[i]的最大xor。。
貌似很基础的样子= =也很暴力= =
有更优解请告诉我= =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=3000010;struct re{ int l,r,lc,rc,ms,mf;} t[N];int root[N],col[N],a[N],b[N],c[N],d[N];int tr[N][2];int n,sum=0,num=0,tot=0,ans=0;inline void inse(int pp,int i,int x){ root[i]=++sum; int pos=root[i]; col[pos]=i; for (int j=30;j>=0;j--){ int y=(x>>j)&1; tr[pos][y^1]=tr[pp][y^1]; tr[pos][y]=++sum; col[sum]=i; pos=tr[pos][y]; pp=tr[pp][y]; }}inline int ques(int l,int r,int x){ int pos=root[r]; int ans=0; for (int j=30;j>=0;j--){ int z=(x>>j)&1; if (col[tr[pos][z^1]]>=l){ ans+=1<<j; pos=tr[pos][z^1]; }else pos=tr[pos][z]; } return ans;}inline int buildtree(int l,int r){ int x=++num; t[x].l=l; t[x].r=r; t[x].mf=t[x].ms=0; if (l==r){ t[x].lc=t[x].rc=0; return x; } int mm=(l+r)/2; t[x].lc=buildtree(l,mm); t[x].rc=buildtree(mm+1,r); return x;}inline void renew(int c,int x){ if (t[x].mf<c){ t[x].ms=t[x].mf; t[x].mf=c; return; } if (t[x].mf==c) return; if (t[x].ms<c) t[x].ms=c;}inline void down(int x){ int l=t[x].lc,r=t[x].rc; renew(t[x].ms,l); renew(t[x].mf,l); renew(t[x].ms,r); renew(t[x].mf,r);}inline int query(int x,int pos){ if (t[x].l==t[x].r) return t[x].ms; down(x); int mm=(t[x].l+t[x].r)/2; if (pos<=mm) return query(t[x].lc,pos); return query(t[x].rc,pos);}inline void add(int x,int l,int r,int c){ if (t[x].l==0) return; if (l<=t[x].l&&t[x].r<=r){ t[x].ms=t[x].mf; t[x].mf=c; return; } down(x); int mm=(t[x].l+t[x].r)/2; if (l<=mm) add(t[x].lc,l,r,c); if (mm<r) add(t[x].rc,l,r,c);}inline void calc(){ memset(col,0,sizeof(col)); memset(tr,0,sizeof(tr)); sum=0; tot=0; inse(0,0,0); for (int i=1;i<=n;i++){ b[++tot]=a[i]; inse(root[i-1],i,a[i]); } std::sort(b+1,b+n+1); for (int i=1;i<=n;i++){ c[i]=lower_bound(b+1,b+n+1,a[i])-b; } num=0; int ro=buildtree(1,n); for (int i=1;i<=n;i++){ int x; x=query(ro,c[i]); x++; ans=max(ans,ques(x,i,a[i])); if (c[i]>1) add(ro,1,c[i]-1,i); }}inline void read(int &T){ int ch=getchar(); while (ch<'0'||ch>'9'){ ch=getchar(); } T=0; while (ch>='0'&&ch<='9'){ T=T*10+ch-'0'; ch=getchar(); }}int main(){ scanf("%d",&n); num=0; for (int i=1;i<=n;i++){ scanf("%d",&d[i]); a[i]=d[i]; } calc(); for (int i=1;i<=n;i++) a[i]=d[n-i+1]; calc(); printf("%d\n",ans);} |