NOIP T4 怎么把一个暴力改改直接变正解

· · 题解

首先需要会一个分治的 O(n\log n) 单次询问做法，膜拜感谢这篇题解。

简单讲就是一次询问给定了 L,R，我们 solve(x,y) 解决 x\le l\le i\le r\le y 的问题（[l,r] 是题目中长度 [L,R] 的区间）。我们假设 i\le mid，那枚举 l，要求 r>mid 且 r-l+1\in[L,R]，这样可行的 r 是区间，对于每个 l 可以单调队列求出来。然后每个左端点的 l 的答案可以贡献到 [l,mid] 的 i 上，做一个前缀 \max 即可。然后右边同理。这样一个子问题的时间复杂度是 O(\min(R,r-l+1))（注意这个 R 的 checkmin 哦）。然后显然区间长度 <L 就可以停。

然后考虑一个很深刻的事情：如果 \frac RL=O(1)，那只有 O(\frac nL) 个区间会被分治到，那么复杂度就是 O(\frac nLR)=O(n)。

我们考虑把询问的限制分成 \log n 段：[2^i,2^{i+1}-1]。每个询问可以拆成 O(\log n) 个整段和两个散段。注意每个小段内 \frac RL\le 2，分治是 O(n) 的，所以散块暴力。对于整块，我们预处理每个整块每个数的答案，查询的时候相当于每个 i 查询第 l_j 到 r_j 个块的答案，相当于大小为 \log n 的 RMQ，直接随便做。

时间复杂度 O(n\log n\log\log n+nq)。看代码理应很好理解。可惜应该是被卡常了。

分治可以是线性的，很深刻吧！

#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
int n,q;
int a[200005],b[200005],c[200005];
int L,R;
int Q[200005];
void solve(int l,int r){
    if(r-l+1<L)return;
    if(l==r){
        c[l]=max(c[l],a[l+1]-a[l]);
        return;
    }
    int m=(l+r)>>1;
    solve(l,m);solve(m+1,r);
    int x=m+1,f1=0,f2=-1;
    int mx=-1e18;
    REP(i,max(l,m+1-R+1),m+1){
        int ll=max(m+1,i+L-1),rr=min(r,i+R-1);
        if(ll>rr){
            c[i]=max(c[i],mx);
            continue;
        }
        while(x<=rr){
            while(f1<=f2&&a[Q[f2]+1]<a[x+1])--f2;
            Q[++f2]=x;
            ++x;
        }
        while(f1<=f2&&Q[f1]<ll)++f1;
        mx=max(mx,a[Q[f1]+1]-a[i]);
        c[i]=max(c[i],mx);
    }
    x=m;f1=0,f2=-1;mx=-1e18;
    for(int i=min(r,m+R-1);i>m;--i){
        int ll=max(l,i-R+1),rr=min(m,i-L+1);
        if(ll>rr){
            c[i]=max(c[i],mx);
            continue;
        }
        while(x>=ll){
            while(f1<=f2&&a[Q[f2]]>a[x])--f2;
            Q[++f2]=x;
            --x;
        }
        while(f1<=f2&&Q[f1]>rr)++f1;
        mx=max(mx,a[i+1]-a[Q[f1]]);
        c[i]=max(c[i],mx);
    }
}
int pc[50004][18][18];
void Main(){
    cin>>n;
    REP(i,0,n)cin>>a[i+1],a[i+1]+=a[i];
    cin>>q;
    int m=1;
    for(int j=1;(1<<j)<=n;++j){
        ++m;
        REP(i,0,n)c[i]=-1e18;
        int ll=(1<<j),rr=(1<<(j+1))-1;rr=min(rr,n);
        L=ll;R=rr;
        solve(0,n-1);
        REP(i,0,n)pc[i][j][j]=c[i];
    }
    REP(i,0,n){
        REP(j,1,m){
            REP(l,j+1,m){
                pc[i][j][l]=max(pc[i][j][l-1],pc[i][l][l]);
            }
        }
    }
    #define ull unsigned long long
    REP(i,0,q){
        cin>>L>>R;
        REP(j,0,n)c[j]=L==1? a[j+1]-a[j]:-1e18;
        int Ll=m,Rr=-1;
        REP(j,1,m){
            int ll=(1<<j),rr=(1<<(j+1))-1;rr=min(rr,n);
            if(L<=ll&&rr<=R){
                Ll=min(Ll,j);Rr=max(Rr,j);
            }else if(ll<=R||rr>=L){
                int sl=L,sr=R;
                L=max(L,ll);R=min(R,rr);
                solve(0,n-1);
                L=sl;R=sr;
            }
        }
        if(Ll<=Rr){
            REP(j,0,n)c[j]=max(c[j],pc[j][Ll][Rr]);
        }
        ull ans=0;
        REP(j,0,n)ans^=(ull)(c[j])*(j+1);
        cout<<ans<<"\n";
    }
}
signed main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int tc=1;
    while(tc--)Main();
    return 0;
}