P6638 「JYLOI Round 1」常规 题解

· · 题解

题目大意

给出常数 k 与 n 组信息，第 i 组信息表示 a_i+Bk（B 为正整数）上有一个点，m 次询问区间 [l_i,r_i] 内的点数，强制在线。

题目分析

查询转换为前缀思路往往会变得清晰，考虑如何求 [1,x] 内的点数。

考虑将 a_i 排序，二分到最后一个 p 使得 a_p<x。则答案为：

\sum\limits_{1\le i\le p}\lfloor\frac{x-a_i}{k}\rfloor

暴力拆开式子，得到：

\frac{1}{k}\sum\limits_{1\le i\le p}x-a_i-(x-a_i)\bmod k

前两项可以维护前缀和 O(1) 算，最后一项继续暴力拆：

(x-a_i)\bmod k=x\bmod k-a_i\bmod k+[x\bmod k<a_i\bmod k]k

新的前两项依旧可以 O(1) 算，第三项相当于二维偏序，离散化并使用主席树即可，复杂度 O((n+m)\log n)。

请仔细阅读强制在线的要求。

#include<bits/stdc++.h>
#define ll long long
#define L(x) xd[x].l
#define R(x) xd[x].r
#define mid (l+r>>1)
#define lc(x) L(x),l,mid
#define rc(x) R(x),mid+1,r
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
void pf(ll x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N =1e5+5,M=1e7+5;
bool ty=read();
int n=read(),m=read(),k=read(),md,a[N],lsh[N],b[N],ln,c[N],tot,ct[N],rt[N];
ll lastans,pr[N],pc[N];
int in(int i){
    int x=read();
    if(ty&&i>1)x=(lastans+x-1)%md+1;
    return x;
}
struct seg{
    int l,r,w;
}xd[M];
inline int modify(int &x,int X,int l,int r,int p){
    xd[++x]=xd[X],xd[x].w++;
    int nw=x;
    if(l==r)return x;
    p<=mid?L(nw)=modify(x,lc(X),p):R(nw)=modify(x,rc(X),p);
    return nw;
}
inline int query(int x,int l,int r,int Ll,int Rr){
    if(OK)return xd[x].w;
    if(Rr<=mid)return query(lc(x),Ll,Rr);
    if(Ll>mid)return query(rc(x),Ll,Rr);
    return query(lc(x),Ll,Rr)+query(rc(x),Ll,Rr);
}
int find(int x){
    int l=1,r=n,ans=0;
    while(l<=r)if(a[mid]<=x)ans=mid,l=mid+1;
    else r=mid-1;
    return ans;
}
int gt(int x){
    int l=1,r=ln,ans=ln+1;
    while(l<=r)if(b[mid]>x)ans=mid,r=mid-1;
    else l=mid+1;
    return ans;
}
ll calc(int x){
    int p=find(x);
    if(!p)return 0;
    ll ans=1LL*x*p-pr[p]-1LL*(x%k)*p+pc[p];
    int ps=gt(x%k);
    if(ps!=ln+1)ans-=1LL*k*query(rt[p],1,ln,ps,ln);
    return ans/k;
}
signed main(){
    if(ty)md=read();
    repn(i)a[i]=read();
    sort(a+1,a+n+1);
    repn(i)pr[i]=pr[i-1]+a[i],c[i]=lsh[i]=a[i]%k;
    sort(lsh+1,lsh+n+1),lsh[n+1]=-1;
    repn(i)if(lsh[i]^lsh[i+1])b[++ln]=lsh[i];
    repn(i)pc[i]=pc[i-1]+c[i],c[i]=lower_bound(b+1,b+ln+1,c[i])-b,rt[i]=modify(tot,rt[i-1],1,ln,c[i]);
    repm(i){
        int l=in(i),r=in(i);
        if(l>r)swap(l,r);
        lastans=calc(r)-calc(l-1),pf(lastans),putchar('\n');
    }
    return 0;
}