萌新刚学OI,一直80分

回复帖子

@wycero 2019-04-03 22:10 回复
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m;
const int maxn=600005;
int ch[maxn<<5][2],cnt[maxn<<5];int din=1;
void ins(int&pos,int x,int i=26){
    din++;
    rep(j,0,1)ch[din][j]=ch[pos][j];
    cnt[din]=cnt[pos];
    pos=din;
    cnt[pos]++;
    if(i<0)return;
    int fx=(x>>i)&1;
    ins(ch[pos][fx],x,i-1);
}
int vv[maxn];int din2=0;
int rec[maxn];
int maxyh(int x,int y,int ta,int i=26){
    if(i<0)return 0;
    //cout<<"$"<<x<<" "<<y<<" "<<ta<<" "<<i<<endl;
    rep(j,0,1){
        int fx=((ta>>i)&1)^j^1;
        if(cnt[ch[y][fx]]>cnt[ch[x][fx]]){
            return maxyh(ch[x][fx],ch[y][fx],ta,i-1)|((j^1)<<i);
        }
    }
return 0;}
void pr(){
    return;
    cout<<endl<<endl;
    cout<<"digraph{";
    rep(i,1,din)cout<<i<<"[label=\""<<i<<" "<<cnt[i]<<"\"];";
    rep(i,1,din)rep(j,0,1)if(ch[i][j])
        cout<<i<<"->"<<ch[i][j]<<"[label=\""<<j<<"\"];";
    cout<<"}";
    cout<<endl<<endl;
}
int main(){
    cin>>n>>m;
    int las=0;
    vv[0]=1;
    pr();
    rep(i,1,n){
        int x;cin>>x;vv[din2+1]=vv[din2];din2++;
        x^=las;
        rec[din2]=x;
        ins(vv[din2],x);
        pr();
        las=x;
    }
    rep(i,1,m){
        string ty;cin>>ty;
        if(ty=="A"){
            int x;cin>>x;vv[din2+1]=vv[din2];din2++;
            x^=las;
            rec[din2]=x;
            ins(vv[din2],x);
            pr();
            las=x;
        }else{
            int l,r,x;cin>>l>>r>>x;
            int ta=rec[din2]^x;
            cout<<(l>1?maxyh(vv[l-2],vv[r-1],ta):max(maxyh(0,vv[r-1],ta),ta))<<endl;
        }
    }
    return 0;
}
@Marser 2019-04-03 23:40 回复 举报

@wycero wyc您头像这么好认,最近又总是一类似标题发帖,不被认出来就有鬼了

@first_fan 2019-04-03 23:41 回复 举报

那两个点卡飞起……

开了$\text{O3+O2}$都救不了你

试试别的优化,卡常恐怕很难。

cin cout巨慢啊好吧

@wycero

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。