自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:31:12，当前版本为作者最后更新于2021-05-08 19:19:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们不妨从最暴力的方法想一想，总共有 $q$ 个询问需要 $O(q)$，枚举 $[a,b]$ 的 $L$ 值需要 $O(n)$，枚举 $[c,d]$ 中的值需要 $O(n)$，暴力计算 $F$ 函数的值还要 $O(n)$，总共 $O(n^3q)$，铁定超时。

显然那个 $O(q)$ 是不能够消除的，那我们考虑优化那三个 $O(n)$。

首先 在线 计算 $F$ 函数可以用分块 $O(\sqrt{n})$ 或 $O(\sqrt{n}\log n)$，但是前一种做法需要预处理前缀块的出现次数，空间复杂度 $O(n\sqrt{n})$ 会被卡。而第二种做法时间复杂度太高，也会被卡。于是我们考虑主席树，时间复杂度 $O(\log n)$，空间复杂度 $O(40n)$，刚刚好。现在时间复杂度被优化到了 $O(n^2q\log n)$。

接着，我们发现 $F(l,r)$ 与 $F(l,r+1)$ 之间只差了 $s_{r+1}$ 对函数的贡献，而它不小于 0，最多为 1。也就是说，$F(L,c)$ 到 $F(L,d)$ 之间的值必然 不下降，而且每相邻两个数相差 至多为 1。所以，$G(F(L,c),F(L,c+1),\cdots,F(L,d))=F(L,d)-F(L,c)+1$ ，又优化掉了一个 $O(n)$，此时时间复杂度变为 $O(nq\log n)$。

现在时间复杂度瓶颈就变成了枚举 $L$ 上。这个时候，我们就可以试着猜一猜求和符号右边的式子有什么规律了。事实上，求和符号右边的式子是 随着 $L$ 的增大而增大 的。我们来证明一下：

当 $L=k$ 时，右边的值为 $F(k,d)-F(k,c)+1$，而当 $L=k+1$ 时，右边为 $F(k+1,d)-F(k+1,c)$。两者的区别仅仅在于 $s_k$ 产生的贡献。

• 当 $s_k$ 在 $[k+1,d]$ 不出现时，$F(k,d)$ 和 $F(k,c)$ 分别会比 $F(k+1,d)$ 和 $F(k+1,c)$ 大 1，相当于没起到作用。
• 当 $s_k$ 在 $[k+1,c]$ 出现时，$F(k,d)$ 和 $F(k,c)$ 和后面相比没有任何变化，相当于不起作用。
• 当 $s_k$ 仅在 $[c+1,d]$ 出现时，$F(k,d)$ 相较后面没有变化，而 $F(k,c)$ 加上了 1，总共 减去了 1。

综上，证明成立，且 $L=k+1$ 相较 $L=k$ 时，值至多会增加 1。于是我们便可以愉快地二分了，总时间复杂度变成了 $O(q\log^2 n)$，在有 O2 优化的情况下可以跑过去。

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=3e5;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(ch>'9' || ch<'0')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

struct Node{int l,r,siz;} t[Maxn*40+5];
int tot,rt[Maxn+5];
#define ls(x) t[x].l
#define rs(x) t[x].r

int n,m,lst,h[Maxn+5],cnt[Maxn+5],nxt[Maxn+5],Q[10];
vector<int> v;

inline void Insert(int l,int r,int L,int &R,int val)
{
    t[++tot]=t[L],R=tot,t[R].siz++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(val<=mid) Insert(l,mid,ls(L),ls(R),val);
    else Insert(mid+1,r,rs(L),rs(R),val);
}
inline int Find(int l,int r,int L,int R,int val)
{
    if(l==r) return t[R].siz-t[L].siz;
    int mid=(l+r)>>1;
    if(val<=mid) return t[rs(R)].siz-t[rs(L)].siz+Find(l,mid,ls(L),ls(R),val);
    else return Find(mid+1,r,rs(L),rs(R),val);
}
inline int F(int l,int r) {return Find(1,n+1,rt[l-1],rt[r],r+1);}
inline void Solve()
{
    while(m--)
    {
        int a,b,c,d,e,f,l,r,siz=-1;
        for(int i=1;i<=4;++i) Q[i]=(read()+lst)%n+1;
        sort(Q+1,Q+5),a=Q[1],b=Q[2],c=Q[3],d=Q[4],e=read(),f=read(),l=a-1,r=b;
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(mid==a-1 || F(mid,d)-F(mid,c)+1<e) l=mid;
            else r=mid-1;
        }
        siz-=l,l=a,r=b+1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(mid==b+1 || F(mid,d)-F(mid,c)+1>f) r=mid;
            else l=mid+1;
        }
        siz+=l,lst=siz; printf("%d\n",siz);
    }
}
inline void Init()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i) v.push_back(h[i]=read()),cnt[i]=n+1;
    sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;++i) h[i]=lower_bound(v.begin(),v.end(),h[i])-v.begin()+1;
    for(int i=n;i>=1;--i) nxt[i]=cnt[h[i]],cnt[h[i]]=i;
    for(int i=1;i<=n;++i) Insert(1,n+1,rt[i-1],rt[i],nxt[i]);
}

int main()
{
    Init(),Solve();
    return 0;
}