洛谷P7577 「PMOI-3」简单模拟题

看到题目中一个求和我人就蒙了。。。

这啥啊这是？？

裸的暴力$O\left(q{n}^2\right)O(qn^2)$O(qn2)，铁定$TLETLE$TLE。。。

得，照惯例先把里面的玩意拽出来搞事。

首先要解决的是怎么在线计算$F(l,r)F(l,r)$F(l,r)，显然这个题我们不能用莫队了对吧。。。

于是拿出主席树来维护。

对于每一个数$val\left[i\right]val[i]$val[i]，找到上一次出现的位置$pos\left[val\right[i\left]\right]pos[val[i]]$pos[val[i]]，记为$last\left[i\right]last[i]$last[i]，如果第一次出现就是$00$0，然后把这个值放进主席树里维护就好，那么$F(l,r)F(l,r)$F(l,r)就是区间$[l,r][l,r]$[l,r]中上一次出现位置不在区间之内的数，即区间$[l,r][l,r]$[l,r]中$last\left[i\right]\le l-1last[i]\backslash leq\; l-1$last[i]≤l−1的个数。

再来看这个$G\left(F\right(L,i\left)\right)\mid i\in [c,d]G(F(L,i))|i\backslash in\; [c,d]$G(F(L,i))∣i∈[c,d]，为了方便我把这玩意改个形式：$G(L,c,d)=G\left(F\right(L,c),F(L,c+1),\cdots ,F(L,d\left)\right)G(L,c,d)=G(F(L,c),F(L,c+1),\backslash cdots,F(L,d))$G(L,c,d)=G(F(L,c),F(L,c+1),⋯,F(L,d))

首先我们发现，从$F(l,r)F(l,r)$F(l,r)到$F(l,r+1)F(l,r+1)$F(l,r+1)，仅仅是多了$val[r+1]val[r+1]$val[r+1]这个数的贡献，而这个贡献一定不是$00$0就是$11$1。

也就是说，从$F(L,c)F(L,c)$F(L,c)到$F(L,d)F(L,d)$F(L,d)一定是单调不下降的，并且相邻两项的差最多为$11$1。

那就好办了，可以直接利用这个性质来计算$GG$G函数了：

$G(L,c,d)=F(L,d)-F(L,c)+1G(L,c,d)=F(L,d)-F(L,c)+1$G(L,c,d)=F(L,d)−F(L,c)+1

现在这个复杂度变成了$O\left(qn{2}_{}n\right)O(qn\backslash log\_2n)$O(qnlog2​n)

好歹干掉了一个n嘛

现在重点就在如何枚举$LL$L上了。

当$L=kL=k$L=k的时候，$G(L,c,d)=F(k,d)-F(k,c)+1G(L,c,d)=F(k,d)-F(k,c)+1$G(L,c,d)=F(k,d)−F(k,c)+1；

当$L=k+1L=k+1$L=k+1的时候，$G(L,c,d)=F(k+1,d)-F(k+1,c)+1G(L,c,d)=F(k+1,d)-F(k+1,c)+1$G(L,c,d)=F(k+1,d)−F(k+1,c)+1。

可以发现这两者的差别就在于$val\left[k\right]val[k]$val[k]对区间$[k+1,d][k+1,d]$[k+1,d]的贡献。

分类讨论一下：

1. 若$val\left[k\right]val[k]$val[k]在$[k+1,d][k+1,d]$[k+1,d]中没有出现，则有：$F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)+1F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)+1$F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)+1。

   故：$G(k+1,c,d)=G(k,c,d)G(k+1,c,d)=G(k,c,d)$G(k+1,c,d)=G(k,c,d)

2. 若$val\left[k\right]val[k]$val[k]在$[k+1,c][k+1,c]$[k+1,c]中出现，则有：$F(k,c)=F(k+1,c),F(k,d)=F(k+1,d)F(k,c)=F(k+1,c),F(k,d)=F(k+1,d)$F(k,c)=F(k+1,c),F(k,d)=F(k+1,d)。

   故：$G(k+1,c,d)=G(k,c,d)G(k+1,c,d)=G(k,c,d)$G(k+1,c,d)=G(k,c,d)

3. 若$val\left[k\right]val[k]$val[k]只在$[c+1,d][c+1,d]$[c+1,d]中出现，则有：$F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)$F(k,c)=F(k+1,c)+1,F(k,d)=F(k+1,d)。

   故：$G(k+1,c,d)=G(k,c,d)+1G(k+1,c,d)=G(k,c,d)+1$G(k+1,c,d)=G(k,c,d)+1

我们发现这个$G(L,c,d)G(L,c,d)$G(L,c,d)又是一个单调不下降的，并且相邻两项的差最多为$11$1的函数。

这咋办？总不能写一个主席树套主席树吧。。。

我们想到因为我们是在线做法，所以这个玩意并不需要记录。

那就直接二分。

二分第一个满足下限$ee$e的$L_{1}L\_1$L1​，和最后一个满足上限$ff$f的$L_{2}L\_2$L2​，最终答案就是$L_2-L_1+1L\_2-L\_1+1$L2​−L1​+1。

记得里离散化和判断解是否成立即可。

复杂度$O\left(q{2}_2^{}n\right)O(q\backslash log\_2^2n)$O(qlog22​n)，有点卡 ，但能过就行

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 300010
#define MAX 999999999
using namespace std;
int n,m,q,size=0;
int val[MAXN],lsh[MAXN],root[MAXN],pos[MAXN],last[MAXN];
struct Chairman_Tree{
    int data,lson,rson;
}a[MAXN*20];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void insert(int k,int l,int r,int &rt){
    a[++size]=a[rt];rt=size;
    a[rt].data++;
    if(l==r)return;
    int mid=l+r>>1;
    if(k<=mid)insert(k,l,mid,a[rt].lson);
    else insert(k,mid+1,r,a[rt].rson);
}
int query(int i,int j,int k,int l,int r){
    if(l==r)return a[j].data-a[i].data;
    int mid=l+r>>1;
    if(k<=mid)return query(a[i].lson,a[j].lson,k,l,mid);
    else return a[a[j].lson].data-a[a[i].lson].data+query(a[i].rson,a[j].rson,k,mid+1,r);
}
int check(int l,int r,int k){
    return query(root[k-1],root[r],k,1,n+1)-query(root[k-1],root[l],k,1,n+1)+1;
}
void work(){
    int lastans=0,l,r,mid,s1,s2,f[10];
    while(q--){
        for(int i=1;i<=4;i++)f[i]=(read()+lastans%n)%n+1;
        sort(f+1,f+5);
        for(int i=5;i<=6;i++)f[i]=read();
        s1=s2=MAX;
        l=f[1];r=f[2];
        while(l<=r){
            mid=l+r>>1;
            if(check(f[3],f[4],mid)>=f[5]){
                s1=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        if(s1==MAX){
            lastans=0;
            printf("0\n");
            continue;
        }
        l=f[1];r=f[2];
        while(l<=r){
            mid=l+r>>1;
            if(check(f[3],f[4],mid)<=f[6]){
                s2=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(s2==MAX){
            lastans=0;
            printf("0\n");
            continue;
        }
        lastans=s2-s1+1;
        printf("%d\n",lastans);
    }
}
void init(){
    n=read();q=read();
    for(int i=1;i<=n;i++){
        val[i]=lsh[i]=read();
        pos[i]=0;
    }
    sort(lsh+1,lsh+n+1);
    m=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        val[i]=lower_bound(lsh+1,lsh+m+1,val[i])-lsh;
        last[i]=pos[val[i]]+1;
        pos[val[i]]=i;
    }
    for(int i=1;i<=n;i++){
        root[i]=root[i-1];
        insert(last[i],1,n+1,root[i]);
    }
}
int main(){
    init();
    work();
    return 0;
}