答案比正解少1,+1AC但是样例过不去
查看原帖
答案比正解少1,+1AC但是样例过不去
37409
Episode9楼主2020/5/21 20:18

啊啊啊你是一个一个一个一个一个一个

#include<bits/stdc++.h>
using namespace std;

inline void read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n,cnt=0,rt[50005],Max=0;
struct trie{int ls,rs,size;}t[50005*32];
struct seg{int L,R;}tree[4*50005];
struct node{int num,wz;}a[50005];
bool cmp1(node x,node y){return x.num>y.num;}
inline void update(int root)
{
    if (tree[root<<1].L==0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1|1].L==0) tree[root].L=tree[root<<1].L;
    if (tree[root<<1].L!=0&&tree[root<<1|1].L!=0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1].R==0) tree[root].R=tree[root<<1|1].R;
    if (tree[root<<1|1].R==0) tree[root].R=tree[root<<1].R;
    if (tree[root<<1].R!=0&&tree[root<<1|1].R!=0) tree[root].R=tree[root<<1].R;
}
inline void add(int root,int l,int r,int x)
{
    if (l==r) {tree[root].L=x;tree[root].R=x;return;}
    int mid=l+r>>1;
    if (x<=mid) add(root<<1,l,mid,x);
    else add(root<<1|1,mid+1,r,x);
    update(root);
}
inline int ask_L(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].L;
    int mid=l+r>>1;
    if (qr<=mid) return ask_L(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_L(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_L(root<<1|1,mid+1,r,mid+1,qr)!=0?ask_L(root<<1|1,mid+1,r,mid+1,qr):ask_L(root<<1,l,mid,ql,mid)); 
}
inline int ask_R(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].R;
    int mid=l+r>>1;
    if (qr<=mid) return ask_R(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_R(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_R(root<<1,l,mid,ql,mid)!=0?ask_R(root<<1,l,mid,ql,mid):ask_R(root<<1|1,mid+1,r,mid+1,qr)); 
}
inline void insert(int pre,int &root,int i,int x)
{
    if (i<0) return;
    root=++cnt;
    t[root]=t[pre];
    t[root].size++;
    if ((x>>i)&1) insert(t[pre].rs,t[root].rs,i-1,x);
    else insert(t[pre].ls,t[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
    if (i<0) return 0;
    if ((x>>i)&1)
    {
    	if (t[t[root].ls].size-t[t[pre].ls].size>0) return query(t[pre].ls,t[root].ls,i-1,x)+(1<<i);
    	else return query(t[pre].rs,t[root].rs,i-1,x);
	}
    else
    {
    	if (t[t[root].rs].size-t[t[pre].rs].size>0) return query(t[pre].rs,t[root].rs,i-1,x)+(1<<i);
    	else return query(t[pre].ls,t[root].ls,i-1,x);
    }
}
int main()
{
    read(n);
    for (int i=1;i<=n;i++) read(a[i].num),a[i].wz=i,insert(rt[i-1],rt[i],30,a[i].num);
    sort(a+1,a+n+1,cmp1);
    for (int i=1;i<=n;i++) 
    {
		add(1,1,n,a[i].wz);
        if (i==1) continue;
        if (i==2){Max=max(Max,query(rt[0],rt[n],30,a[i].num));continue;}
        int L=ask_L(1,1,n,1,a[i].wz-1),R=ask_R(1,1,n,a[i].wz+1,n);
        int LL=ask_L(1,1,n,1,L-1),RR=ask_R(1,1,n,R+1,n);
        if (LL==0&&L!=0) Max=max(Max,query(rt[0],rt[R-1],30,a[i].num));
        if (RR==0&&R!=0) Max=max(Max,query(rt[L],rt[n],30,a[i].num));
        if (L==0) Max=max(Max,query(rt[0],rt[RR-1],30,a[i].num));
        if (R==0) Max=max(Max,query(rt[LL],rt[n],30,a[i].num));
        if (LL!=0&&R!=0) Max=max(Max,query(rt[LL],rt[R-1],30,a[i].num));
        if (L!=0&&RR!=0)Max=max(Max,query(rt[L],rt[RR-1],30,a[i].num));
    }
    cout<<Max+1<<endl;
	return 0;
} 

求求帮康康,嗯哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

2020/5/21 20:18
加载中...