题解 P7577【「PMOI-3」简单模拟题】

· · 题解

思路

我们不妨从最暴力的方法想一想，总共有 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 产生的贡献。

综上，证明成立，且 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;
}