P11745 题解

lmh_qwq · 2025-02-14 22:28:56 · 题解

首先对询问的 x 从大到小做扫描线，相当于选一个区间使得其中至少有 m 个数 \ge x。

维护一个 \ge x 的数的链表，对每个左端点可能的区间（每个区间与右侧第一个 \ge x 的数一一对应）维护其对答案的贡献，在链表中插入数的时候暴力重构受到影响的 O(m) 个区间即可。

时间复杂度 O(nm)，注意常数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000007,INF=2147483647;
ll cid,n,m,k,nQ,B,a[N],p[N],R[N],stk[N],top,pre[N],nxt[N],q[N],val[N],ans,now;
struct myrand{
    ll A,B,P,X;
    myrand(ll a,ll b,ll p,ll x){A=a;B=b;P=p;X=x;}
    ll next(){return X=(A*X+B)%P;}
}rng(0,0,0,0);
ll convert(ll x){
    if (cid==7) return x%2;
    return x%(n+1);
}
void rebuild(ll l,ll r){
    if (r>n) return;
//  cout<<"rebuild "<<l<<' '<<r<<endl;
    now-=val[l];
    ll& v=val[l];
    ll L=pre[l]+1;l=min(l,n-k+1);
    if (L>l){v=0;return;}
    v=(n+1)*(l-L+1);
    ll p=min(l+1,max(L,r-k+1));
    if (L<p) v-=r*(p-L);
    if (p<=l) v-=(k-1)*(l-p+1)+(p+l)*(l-p+1)/2;
    now+=v;
}
void add(int x){
    ll r=R[x];
    nxt[x]=r;pre[x]=pre[r];
    nxt[pre[x]]=x;pre[r]=x;
//  s.insert(x);
    ll l=x,i=1;
    while(i<m){
        if (pre[l]==0) break;
        l=pre[l];++i;
    }
    r=l;
    for (int i=1;i<m;++i) r=nxt[r];
    for (;~i;--i){
        rebuild(l,r);
        l=nxt[l];r=nxt[r];
    }
}
int main(){
    cin>>n>>k>>m>>B>>cid>>nQ;
    rng=myrand(16807,B,INF,0);
    for (int i=1;i<=n;++i) a[i]=i;
    for (int i=1;i<=n;++i){
        int l=rng.next()%n+1,r=rng.next()%n+1;
        swap(a[l],a[r]);
    }
    for (int i=1;i<=n;++i) p[a[i]]=i;
    for (int i=1;i<=nQ;++i) q[convert(rng.next())]^=1;
    stk[0]=n+1;a[n+1]=n+1;
    for (int i=n;i;--i){
        while(a[stk[top]]<a[i]) --top;
        R[i]=stk[top];stk[++top]=i;
    }
//  for (int i=1;i<=n;++i){cout<<a[i]<<' ';}cout<<endl;
    q[1]^=q[0];
//  s.insert(0);s.insert(n+1);
    nxt[0]=nxt[n+1]=n+1;
    for (int i=n;i;--i){
        add(p[i]);
//      cout<<i<<' '<<now<<endl;
        if (q[i]) ans^=now;
    }
    cout<<ans<<endl;
    return 0;
}