UOJ919 【UR 28】环环相扣

答案性质分析

提取出指定区间内的数，个数记为 $n$，升序排序。

不妨设 $x > y > z$（此时有：$a_x > a_y > a_z$），那么答案只有以下两种情况：

1. $a_x \bmod a_y + a_y \bmod a_z + a_z \bmod a_x = a_x \bmod a_y + a_y \bmod a_z + a_z$
2. $a_x \bmod a_z + a_y \bmod a_x + a_z \bmod a_y = a_x \bmod a_z + a_y + a_z$

然后我们可以证明对于答案有 $x = n$，$y = n-1$。

第一种

首先我们在 $x = n$，$y = n-1$，$z = n-2$ 时有下界：$a_{n-2} + a_{n-1}$。

设：$a_x = k_1 a_y + r_1$，$a_y = k_2 a_z + r_2$。

根据 $a_x > a_y > a_z$，$k_1,k_2 \geq 1$。

那么有 $a_x \bmod a_y + a_y \bmod a_z + a_z = a_x + (1-k_1) a_y + (1-k_1) a_z \leq a_x$。

又有 $a_x \bmod a_y + a_y \bmod a_z + a_z \leq a_y - 1 + a_y + (1-k) a_z \leq 2 a_y - 1$。

那么 $a_x \bmod a_y + a_y \bmod a_z + a_z \leq min\{a_x, 2 a_y - 1\}$。

若要大于下界，必须有：$x = n$，$y = n-1$。

第二种

设：$a_x = k a_z + r$。

由于 $a_x > a_z$，那么有 $k \geq 1$。

那么：$a_x \bmod a_z + a_y + a_z = a_x + a_y + (1-k) a_z$。

若要使答案尽量大，应有 $x = n$，$y = n-1$。

至此，我们证明了答案必有 $x = n$，$y = n - 1$。

求答案方法

我们可以维护 $F(x,l,r)$ 表示区间 $[l,r]$ 中除去 $a_x$ 及 剩余的最大值 $a_y$ 后的最大 $a_x \bmod a_k + a_k$。

那么两种答案分别是：

1. $F(y,l,r) + a_x \bmod a_y$。
2. $F(x,l,r) + a_y$。

此时 $x$，$y$ 已经确定，所以我们只需要求 $F$。

然后我们考虑把 $F$ 拆成两边 $G(l,x)$ 和 $H(x,r)$，分别表示：

$k$ 在 $[l,x)$ 除去最大值 中 $a_x \bmod a_k + a_k$ 的最大值。

$k$ 在 $(x,r]$ 除去最大值 中 $a_x \bmod a_k + a_k$ 的最大值。

然后我们再补上两边最大值中较小的那一个的贡献。

由于 $H$ 的维护与 $G$ 同理，这里只叙述如何维护 $G$。

首先暴力维护是 $O(n^2)$ 的。

性质一

首先我们同样的设 $a_x = k a_i + r$。

那么根据 $a_x > a_i$，有 $k \geq 1$ 。

当 $2 a_i > a_x$ 即 $a_i > \frac{a_x}{2}$ 时取等 $k = 1$。

此时上式等于 $a_x$ 取得最大值。

我们固定 $x$，从右往左扫描 $l$：

那么有一个性质，如果有两个数（因为要排除最大值） $> \frac{a_x}{2}$ ，那么已经取得了最大值，无需扫描剩下的 $l$。

性质二

那么类似的，如果有两个 $a_i$ 满足 $a_i > 2 a_j$ 那么 $a_j$ 不会产生贡献，下面证明：

$$
a_x \bmod a_i + a_i \geq a_i \geq 2 a_j > a_x \bmod a_j + a_j
$$

拥有了这两条性质，我们从小到大枚举 $x$，用一个栈维护所有有贡献的点。

每一次我们直接从栈顶开始遍历栈，如果 $a_{top} > \frac{a_x}{2}$ 那么给标记 $tag$ 加一，表示性质一。

否则，给 $cnt_{top}$ 加一，表示性质二。

在遍历的过程中，维护答案，将遍历到的点和答案加入 $G(x)$ 中。

当 $tag = 2$ 时，停止遍历。

对于遍历过的数，将 $cnt_i < 2$ 的重新插入栈中。

时间复杂度是 O(n) 的。

查询的时候只需要在 $G(x)$ 中二分查找即可。

同时需要线段树查询最大值位置。

对于 $H$ 可同理求出，具体可见代码 Init() 函数。

总时间复杂度 $O(n + q \log n)$。

需要卡常，尤其注意查询时的线段树查询次数，记得开 O2。

参考资料

• https://www.cnblogs.com/Scarab/p/18569891。

参考代码

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,ll>
#define fir first
#define sec second
const int maxn=2e6;
int n,m,op;
ll a[maxn+5];
int st[maxn+5],stt;
int cnt[maxn+5];
vector<P> lv[maxn+5];
vector<P> rv[maxn+5];
int mx[(maxn<<2)+5];
inline int Get(int x,int y){
    return (a[x]>a[y])?x:y;
}
void Build(int x,int L,int R){
    if(L==R) mx[x]=L;
    else{
        int mid=(R-L)/2+L;
        Build(x<<1,L,mid);
        Build(x<<1|1,mid+1,R);
        mx[x]=Get(mx[x<<1],mx[x<<1|1]);
    }
}
int Query(int x,int L,int R,int l,int r){
    if(l>r) return 0;
    if(l<=L&&R<=r) return mx[x];
    else{
        int mid=(R-L)/2+L,res=0;
        if(l<=mid)
            res=Get(res,Query(x<<1,L,mid,l,r));
        if(mid<r)
            res=Get(res,Query(x<<1|1,mid+1,R,l,r));
        return res;
    }
}
inline void Init(){
//    int tim=0;
    stt=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        int tag=0,top=stt,mx=0;
        ll res=0;
        for(;stt;stt--){
            if(!mx) mx=st[stt];
            else if(a[st[stt]]<a[mx])
                res=max(res,a[i]%a[st[stt]]+a[st[stt]]);
            else res=max(res,a[i]%a[mx]+a[mx]),mx=st[stt];
            lv[i].emplace_back(P(st[stt],res));
            if(a[st[stt]]>a[i]/2) tag++;
            else ++cnt[st[stt]];
            if(tag>=2) break;
        }
        for(int j=stt+1;j<=top;j++)
            if(cnt[st[j]]<2) st[++stt]=st[j];
        st[++stt]=i;
        reverse(lv[i].begin(),lv[i].end());
//        tim+=lv[i].size();
    }
    stt=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=n;i>=1;i--){
        int tag=0,top=stt,mx=0;
        ll res=0;
        for(;stt;stt--){
            if(!mx) mx=st[stt];
            else if(a[st[stt]]<a[mx])
                res=max(res,a[i]%a[st[stt]]+a[st[stt]]);
            else res=max(res,a[i]%a[mx]+a[mx]),mx=st[stt];
            rv[i].emplace_back(P(-st[stt],res));
            if(a[st[stt]]>a[i]/2) tag++;
            else ++cnt[st[stt]];
            if(tag>=2) break;
        }
        for(int j=stt+1;j<=top;j++)
            if(cnt[st[j]]<2) st[++stt]=st[j];
        st[++stt]=i;
        reverse(rv[i].begin(),rv[i].end());
//        tim+=rv[i].size();
    }
//    cerr<<tim<<endl;
}
inline ll Getans(int x,int l,int r,int smx){
    ll res=0;
    if(smx) res=a[x]%a[smx]+a[smx];
    vector<P>::iterator lp,rp;
    lp=lower_bound(lv[x].begin(),lv[x].end(),P(l,LLONG_MIN));
    rp=lower_bound(rv[x].begin(),rv[x].end(),P(-r,LLONG_MIN));
    if(lp!=lv[x].end()) res=max(res,lp->sec);
    if(rp!=rv[x].end()) res=max(res,rp->sec);
    return res;
}
namespace IO{
    inline ll Read(){
        ll res=0;char ch=getchar();
        while(ch<'0'||'9'<ch) ch=getchar();
        while('0'<=ch&&ch<='9')
            res=(res<<1)+(res<<3)+ch-'0',ch=getchar();
        return res;
    }
    short s[50],st;
    inline void Write(ll x){
        if(x==0){puts("0");return;}
        while(x) s[++st]=x%10,x/=10;
        while(st) putchar('0'+s[st--]);
        putchar('\n');
    }
}
using IO::Read;
using IO::Write;
signed main(){
//    freopen("ex_cycle9.in","r",stdin);
//    freopen("cycle.out","w",stdout);
    n=Read(),m=Read(),op=Read();
    for(int i=1;i<=n;i++) a[i]=Read();
    Build(1,1,n);
    Init();
    int l,r;
    ll ans=0;
    while(m--){
//        const double tim=clock();
        l=Read(),r=Read();
        l=(l+op*ans-1)%n+1;
        r=(r+op*ans-1)%n+1;
        int x=Query(1,1,n,l,r);
        int y=Query(1,1,n,l,x-1);
        int z=Query(1,1,n,x+1,r);
        int t=Get(y,z);
        ans=0;
        if(y!=t) ans=max(ans,Getans(x,l,r,y)+a[t]);
        if(z!=t) ans=max(ans,Getans(x,l,r,z)+a[t]);
        if(t<x) ans=max(ans,Getans(t,l,r,Query(1,1,n,l,t-1))+a[x]%a[t]);
        if(x<t) ans=max(ans,Getans(t,l,r,Query(1,1,n,t+1,r))+a[x]%a[t]);
        Write(ans);
//        cerr<<clock()-tim<<endl;
    }
    return 0;
}