P4855 MloVtry的idea 题解

· · 题解

P4855题解

思路

这道题乍一看非常不可做，要实现区间加一个数，区间加等差数列和区间第 k 小。

不过手玩样例后可以发现每次查询中对 a 产生的变化仅在当次查询中生效。

而且因为 zz 给定，所以对于所有查询中 i\le j 的部分变化后的量都相同，于是可以维护一个数组 a_i-zz。

因此，不难想到分两部分处理。

再思考 i\gt j 的部分如何处理，尝试找通性，a_i+i-j_1 和 a_i+i-j_2 中，仅有每次的 j 不同，但在单个询问中固定，于是可以再维护一个数组 a_i+i。

做法

由于要区间第 k 小，且题面中未明确值域，所以使用主席树解决此题。

用两棵主席树分别维护 a_i-zz 和 a_i+i。

对于每次查询，由于不便于（或者我太蒟）直接查询第 k 小，于是改为二分查找。

二分一个最小在当前的 a 中小于等于自己的数的个数大于等于 k 的数就是答案。

小于等于 x 的数的个数可以分两部分求，为 x 在 a_i-zz,i\le j 中的最大排名，和 x+j 在 a_i+i,i\gt j 中的最大排名的和。

AC代码

#include<bits/stdc++.h>
#define R(x) x=read()
using namespace std;
char pbuf[1<<20], *pp=pbuf;
void swap(int &a,int &b){a^=b^=a^=b;}
inline void push(const char &c){if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;*pp++ = c;}
class io{public:~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}}_;
inline void write(int x) {
    if (x<0)x=-x,push('-');
    int sta[35],top=0;
    do{sta[top++]=x%10,x/=10;}while (x);
    while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
    char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,q,zz;
#define N 60010
int a[N];
struct node{
    int ls,rs,s;
}t[N<<6];
int siz;
int rt[N],r2[N];
void update(int u,int v,int l,int r,int pos){
    t[v].s=t[u].s+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(!t[u].ls)t[u].ls=++siz;
    if(!t[u].ls)t[u].rs=++siz;
    t[v].ls=t[u].ls;
    t[v].rs=t[u].rs;
    if(pos<=mid){
        t[v].ls=++siz;
        update(t[u].ls,t[v].ls,l,mid,pos);
    }
    else{
        t[v].rs=++siz;
        update(t[u].rs,t[v].rs,mid+1,r,pos);
    }
}
int query(int u,int v,int l,int r,int x){
    if(l==r)return t[v].s-t[u].s;
    int mid=(l+r)>>1;
    if(x<=mid)return query(t[u].ls,t[v].ls,l,mid,x);
    else return t[t[v].ls].s-t[t[u].ls].s+query(t[u].rs,t[v].rs,mid+1,r,x);
}
int ls;
signed main(){
    R(n);R(q);R(zz);
    for(int i=1;i<=n;i++)R(a[i]);
    rt[0]=++siz;
    r2[0]=++siz;
    for(int i=1;i<=n;i++){
        rt[i]=++siz;
        r2[i]=++siz;
        update(rt[i-1],rt[i],-1e9,1e9,a[i]-zz);
        update(r2[i-1],r2[i],-1e9,1e9,a[i]+i);
    }
    while(q--){
        int R(j),R(k);
        j=(j^ls)%n+1;
        k=(k^ls)%n+1;
        int l=-1e9,r=1e9;
        while(l<r){
            int mid=(l+r)>>1;
            if(query(rt[0],rt[j],-1e9,1e9,mid)+query(r2[j],r2[n],-1e9,1e9,mid+j)>=k)r=mid;
            else l=mid+1;
        }
        // for(int i=1;i<=n;i++){
        //     if(i<=j)write(a[i]-zz);
        //     else write(a[i]-j+i);
        //     push(' ');
        // }
        // push('\n');
        // int x=11932;
        // write(query(rt[0],rt[j],-1e9,1e9,x));write(query(r2[j],r2[n],-1e9,1e9,x+j));push('\n');
        // write(j);push(' ');
        // write(k);push('|');
        write(l);
        // push(' ');
        // write(query(rt[0],rt[j],-1e9,1e9,l));write(query(r2[j],r2[n],-1e9,1e9,l+j));
        push('\n');
        ls=l>0?l:-l;
    }
    return 0;
}