P8264 TEST_100

题面

原题链接 click

题解

分块题，视 \(n,m,v\) 同阶，设块长为 \(B\)。
考虑维护每个值在经过一个块后会变成什么，这可以用第二分块的想法，用并查集来维护每一块，然后计算即可，用时 \(O(\frac {n^2\alpha(n)}B)\)。
询问时散块暴力，整块直接用处理好的数据即可，用时 \(O(n(B+\frac nB))\)。
总复杂度 \(O(n(B+\frac{n\alpha(n)}B))\)，取 \(B=\Theta\large(\normalsize\sqrt{n\alpha(n)}\large)\) 可平衡至 \(O\large(\normalsize n\sqrt{n\alpha(n)}\large)\)，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000,B=400;
int fa[MAXN+5];
int w[MAXN/B+5][MAXN+5];
int l[MAXN/B+5],r[MAXN/B+5],h[MAXN+5];
int n,q;
int a[MAXN+5];
int nl,nr,tl,tr;//nl,nr代表现在的并查集值域，其中并查集nl对应实际tl，并查集nr对应实际tr
int tmp[MAXN+5];
//保证nl<nr，不保证tl<tr
void init(){
    for(int i=0;i<=MAXN;i++) fa[i]=i;
    nl=tl=0; nr=tr=MAXN;
}
int getf(int u){
    if(fa[u]==u) return u;
    return fa[u]=getf(fa[u]);
}
void solve(int *w,int l,int r){
    // cerr<<l<<' '<<r<<'\n';
    init();
    for(int i=l;i<=r;i++){
        if(a[i]>=tl&&a[i]>=tr){
            tl=a[i]-tl; tr=a[i]-tr;
        }else if(a[i]<=tl&&a[i]<=tr){
            tl-=a[i]; tr-=a[i];
        }else{
            if(abs(nl-nr)!=abs(tl-tr)) exit(5);
            int m=tl+tr>>1;
            if(a[i]<=m){
                if(tl<tr){
                    // cerr<<"*";
                    for(int k=a[i]-tl+nl,j=k;k>=nl;k--,j++){
                        // cerr<<"&";
                        fa[k]=j;
                        // if(j>nr) exit(1);
                    }
                    nl=a[i]-tl+nl;
                    tr=abs(tr-a[i]); tl=0;
                }else{
                    for(int k=tl-a[i]+nl,j=k;k<=nr;k++,j--){
                        fa[k]=j;
                        // if(j<nl) exit(2);
                    }
                    nr=tl-a[i]+nl;
                    tl=abs(tl-a[i]); tr=0;
                }
            }else{
                if(tl<tr){
                    for(int k=a[i]-tl+nl,j=k;k<=nr;k++,j--){
                        fa[k]=j;
                        // if(j<nl) exit(3);
                    }
                    nr=a[i]-tl+nl;
                    tl=abs(tl-a[i]); tr=0;
                }else{
                    for(int k=tl-a[i]+nl,j=k;k>=nl;k--,j++){
                        fa[k]=j;
                        // if(j>nr) exit(4);
                    }
                    nl=tl-a[i]+nl;
                    tr=abs(tr-a[i]); tl=0;
                }
            }
        }
        // cerr<<"nl="<<nl<<"  nr="<<nr<<"  tl="<<tl<<"  tr="<<tr<<"\n";
        // for(int i=0;i<=MAXN;i++) cerr<<"fa["<<i<<"]="<<fa[i]<<"\n";
    }
    for(int i=nl;i<=nr;i++){
        if(tl<tr) tmp[i]=tl-nl+i;
        else tmp[i]=tl+nl-i;
        // cerr<<"tmp["<<i<<"]="<<tmp[i]<<'\n';
    }
    // for(int i=0;i<=MAXN;i++) cerr<<"fa["<<i<<"]="<<fa[i]<<"\n";
    for(int i=0;i<=MAXN;i++){
        // cerr<<"fa["<<i<<"]="<<fa[i]<<"\n";
        w[i]=tmp[getf(i)];
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        h[i]=i/B+1; if(!l[h[i]]) l[h[i]]=i; r[h[i]]=i;
    }
    for(int i=1;i<=h[n];i++){
        solve(w[i],l[i],r[i]);
    }
    int lastans=0;
    // return 0;
    while(q--){
        int ll,rr,v; cin>>ll>>rr>>v;
        ll^=lastans; rr^=lastans; v^=lastans;
        if(ll>n||ll<1||rr<1||rr>n) exit(1);
        // cerr<<ll<<' '<<rr<<' '<<v<<'\n';
        if(rr-ll<=B){
            while(ll<=rr){
                v=abs(v-a[ll]); ll++;
            }
        }else{
            while(ll!=l[h[ll]]){
                v=abs(v-a[ll]); ll++;
            }
            // cerr<<v<<'\n';
            while(h[ll]!=h[rr]){
                // cerr<<ll<<' '<<h[ll]<<'\n';
                v=w[h[ll]][v];
                ll+=B; if(ll==B+1) ll--;
                // cerr<<v<<'\n';
            }
            while(ll<=rr){
                v=abs(v-a[ll]); ll++;
            }
        }
        cout<<(lastans=v)<<'\n';
        // cerr<<(lastans=v)<<'\n';
    }
    return 0;
}