MnZn求助分块

rt,WA 80pts

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,a[20005],b[20005],c[20005],bl[20005],ans[200][20005],sum1[200][20005],sum2[200][20005],
block,pos[20005],cnt[20005],sum[20005],mus[20005],l1,r1,l2,r2,lst;//<->=
inline int s(int l,int r,int x){
    int res=0;
    for(int i=l;i<=min(r,bl[l]*block);i++)
        res=res+(x<=a[i])*2-1;
    if(bl[l]^bl[r])
        for(int i=(bl[r]-1)*block+1;i<=r;i++)
            res=res+(x<=a[i])*2-1;
    for(int i=bl[l]+1;i<bl[r];i++)
        res+=ans[i][x];
    return res;
}
inline int calc1(int l,int r,int x){
    int res=-1,sm=0;
    if(bl[l]^bl[r]){
        for(int i=l;i<=bl[l]*block;i++)
            sm+=(x<=a[i])*2-1,res=max(res,sm);
        for(int i=bl[l]+1;i<bl[r];i++)
            res=max(res,sm+sum1[i][x]),sm+=ans[i][x];
        for(int i=(bl[r]-1)*block+1;i<=r;i++)
            sm+=(x<=a[i])*2-1,res=max(res,sm);
    }
    else for(int i=l;i<=r;i++)
        sm+=(x<=a[i])*2-1,res=max(res,sm);
    return res;
}
inline int calc2(int l,int r,int x){
    int res=-1,sm=0;
    if(bl[l]^bl[r]){
        for(int i=r;i>(bl[r]-1)*block;i--)
            sm+=(x<=a[i])*2-1,res=max(res,sm);
        for(int i=bl[r]-1;i>bl[l];i--)
            res=max(res,sm+sum2[i][x]),sm+=ans[i][x];
        for(int i=bl[l]*block;i>=l;i--)
            sm+=(x<=a[i])*2-1,res=max(res,sm);
    }
    else for(int i=r;i>=l;i--)
        sm+=(x<=a[i])*2-1,res=max(res,sm);
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    memset(sum1,-1,sizeof(sum1));
    memset(sum2,-1,sizeof(sum2));
    cin>>n,block=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i],bl[i]=(i-1)/block+1;
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        c[i]=a[i]=lower_bound(b+1,b+n+1,a[i])-b;
        int t=c[i];
        c[i]+=cnt[t];
        cnt[t]++;
        pos[c[i]]=i;
    }
//  for(int i=1;i<=n;i++) cout<<pos[i]<<endl;
    for(int i=1;i<=bl[n];i++){
        sort(c+(i-1)*block+1,c+min(i*block,n)+1);
        sum[(i-1)*block+1]=mus[min(i*block,n)]=-1;
        for(int j=(i-1)*block+2;j<=min(i*block,n);j++)
            sum[j]=sum[j-1]-1;
        for(int j=min(i*block,n)-1;j>(i-1)*block;j--)
            mus[j]=mus[j+1]-1;
    }
    for(int i=1;i<=bl[n];i++){
        for(int j=1,k=(i-1)*block;j<=n;j++){
            while(k<min(i*block,n)&&j>c[k+1]) k++;
            ans[i][j]=(k-(i-1)*block)*-1+(min(n,i*block)-k);
        }
    }
    for(int i=n;i;i--){
        for(int j=1;j<=bl[n];j++)
            sum1[j][i]=sum1[j][i+1],sum2[j][i]=sum2[j][i+1];
        int bi=bl[pos[i]];
        for(int j=(bi-1)*block+1;j<=min(bi*block,n);j++){
            if(j>=pos[i])
                sum[j]+=2,sum1[bi][i]=max(sum1[bi][i],sum[j]);
            if(j<=pos[i])
                mus[j]+=2,sum2[bi][i]=max(sum2[bi][i],mus[j]); 
        }
    }
//  for(int i=1;i<=n;i++)
//      cout<<c[i]<<endl;
//  for(int i=1;i<=bl[n];i++)
//      for(int j=1;j<=n;j++)
//          cout<<i<<' '<<b[j]<<' '<<ans[i][j]<<' '<<sum1[i][j]<<' '<<sum2[i][j]<<'\n';
//  cout<<calc2(1,5,5)<<endl;
    cin>>q;
    while(q--){
        cin>>l1>>r1>>l2>>r2;
        l1=(l1+lst)%n+1,l2=(l2+lst)%n+1,r1=(r1+lst)%n+1,r2=(r2+lst)%n+1;
        if(l1>r1) swap(l1,r1);
        if(r1>l2) swap(l2,r1);
        if(l2>r2) swap(l2,r2);
        if(l1>r1) swap(l1,r1);
        if(r1>l2) swap(l2,r1);
        if(l1>r1) swap(l1,r1);
//      cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<endl;
        int lt=1,rt=n+1;
        while(lt<rt-1){
            int mid=lt+rt>>1;
            if(calc2(l1,r1,mid)+s(r1+1,l2-1,mid)+calc1(l2,r2,mid)>=0)
                lt=mid;
            else rt=mid;
        }
        cout<<b[lt]<<'\n',lst=b[lt];
    } 
    return 0;
}