bzoj3217 ALOEXT

Description

给定一个序列,有以下 $4$ 种操作:

  1. I x y 插入 $y$ 到第 $x$ 个之前。
  2. D x 删除第 $x$ 个元素。
  3. C x y 修改第 $x$ 个元素为 $y$。
  4. F l r 询问区间 $[l,r]$ 的次大值与区间一个数的异或最大值。

强制在线,$1\leq N,M \leq 10^5$。

Solution

这道题显然可以用替罪羊树套 Trie 解决,但是对于不会替罪羊树的选手(比如我)就可以选择块状链表+Trie。

区间次大值直接用 Multiset 维护即可,异或最大值直接在 Trie 上跑一下即可。

注意块大小因为套了个 Trie 所以要适量调大。

然后本人调了一整天,祝你好运~

Code

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e5+10,S=5000,M=N/S+2,P=1048576;
I int RC(){char c=gc();W(c^'I'&&c^'D'&&c^'C'&&c^'F') c=gc();return c=='I'?1:c=='D'?2:c=='C'?3:4;}
int n,m,tot;
vector<int> b[M];
multiset<int> s[M];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
class TrieTree{
    private:
        int p[S*100][2],cnt,w[S*100];
        #define nw ((v>>i)&1)
    public:
        I void clear(){cnt=1;memset(p,0,sizeof(p));memset(w,0,sizeof(w));}
        I void A(CI v){RI i,u=1;for(i=20;~i;i--) !p[u][nw]&&(p[u][nw]=++cnt),w[p[u][nw]]++,u=p[u][nw];}
        I void K(CI v){RI i,u=1,t;for(i=20;~i;i--) w[p[u][nw]]--,u=p[u][nw];}
        I int Q(CI v){RI i,u=1,X=0;for(i=20;~i;i--) (p[u][nw^1]&&w[p[u][nw^1]])?X+=(1<<i),u=p[u][nw^1]:u=p[u][nw];return X;}
}T[M];
I void H(PA& X,CI v){v>X.fi?X.se=X.fi,X.fi=v:X.se=max(X.se,v);}
I PA G(CI l,CI x,CI y){PA o=MP(0,0);for(auto i=b[l].begin()+x;i!=b[l].begin()+y+1;i++) H(o,*i);return o;}
I int F(CI l,CI x,CI y,CI v){RI mx=0;for(auto i=b[l].begin()+x;i!=b[l].begin()+y+1;i++) mx=max(mx,(*i)^v);return mx;}
I int Z(CI L,CI R,CI v){RI i,mx=0;for(i=L;i<=R;i++) mx=max(mx,T[i].Q(v));return mx;}
I void O(PA& o,PA v){H(o,v.fi),H(o,v.se);}
I PA E(CI L,CI R){PA o=MP(0,0);RI i;for(i=L;i<=R;i++){auto it=s[i].rbegin();if(it!=s[i].rend()){H(o,*it);++it;if(it!=s[i].rend()) H(o,*it);}}return o;}
I int Q(RI l,RI r){
    PA o=MP(0,0);RI bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL++].size();W(r>=b[bR].size()) r-=b[bR++].size();if(bL==bR) return O(o,G(bL,l,r)),F(bL,l,r,o.se);
    else return O(o,G(bL,l,b[bL].size()-1)),O(o,G(bR,0,r)),O(o,E(bL+1,bR-1)),max(Z(bL+1,bR-1,o.se),max(F(bL,l,b[bL].size()-1,o.se),F(bR,0,r,o.se)));
}
I void C(CI i,CI v){s[i].erase(s[i].find(v)),T[i].K(v);}
I void J(CI i,CI v){s[i].insert(v),T[i].A(v);}
I void U(RI x,CI v){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL++].size();t=b[bL][x],C(bL,t);b[bL][x]=v,J(bL,v);}
I void A(RI x,CI v){
    RI i,t,bL=1;W(x>=b[bL].size()) x-=b[bL++].size();b[bL].insert(b[bL].begin()+x,v),J(bL,v);for(i=bL+1;i<=tot;i++) if(b[i-1].size()<=S) break ;
    else t=b[i-1].back(),C(i-1,t),b[i-1].pop_back(),b[i].insert(b[i].begin(),t),J(i,t);if(b[tot].size()>S) ++tot,T[tot].clear();++n;
}
I void K(RI x){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL++].size();t=b[bL][x];b[bL].erase(b[bL].begin()+x),C(bL,t);--n;} 
int main(){
//    freopen("I.in","r",stdin);freopen("I.out","w",stdout);
    RI i,x,l,r,p=0;for(read(n,m),tot=n/S+1,i=1;i<=tot;i++) T[i].clear();for(i=0;i<n;i++) read(x),b[i/S+1].push_back(x),s[i/S+1].insert(x),T[i/S+1].A(x);
    W(m--) if((x=RC())==1) read(l,r),l=(l+p)%n,r=(r+p)%P,A(l,r);else if(x==2) read(l),l=(l+p)%n,K(l);
    else if(x==3) read(l,r),l=(l+p)%n,r=(r+p)%P,U(l,r);else if(x==4) read(l,r),l=(l+p)%n,r=(r+p)%n,l>r&&(swap(l,r),0),writeln(p=Q(l,r));return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇