Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#define z 65536
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

int f[z+1];

void ad(int x,int v)
{
     while (x<=z)
     {
           f[x]+=v;
           x+=(x&(-x));
     }
}

int calc(int x)
{
    int r=0;
    while (x)
    {
       r+=f[x];
       x-=(x&(-x));
    }
    return r;
}

int find(int v)
{
    int l=1,r=z,m,i;
    while (l<=r)
    {
          m=(l+r)/2;
          if (calc(m)<v) l=m+1;
          else r=m-1;
    }
    fr(i,m-1,m+1)
      if (i && i<=z && calc(i)>=v) return i-1;
}

int main()
{
    int n,test,seed,mul,add,k,med,i,it;
    long long a[250025];
    long long re;
    cin >> test;
    fr(it,1,test)
    {
          cin >> seed >> mul >> add >> n >> k;
          fr(i,0,z) f[i]=0;
          a[1]=seed; 
          fr(i,2,n) a[i]=(a[i-1]*mul+add)%z;
          fr(i,1,k) ad(a[i]+1,1);
          med=(k+1)/2;
          re=0;
          fr(i,k+1,n+1)
          {
              re+=find(med);
              if (i>n) break;
              ad(a[i-k]+1,-1);
              ad(a[i]+1,1);
          }
          cout << "Case #" << it << ": " << re << endl;              
    }
    return 0;
}

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

const int N = 250000, MAX = 65536;
int bit[MAX+1], a[N];

void update(int i, int v) {
    for(int x = i+1; x <= MAX; x += x & -x) bit[x] += v;
}

int find(int cumfre) {
    int res = MAX;
    for(int mask = MAX >> 1; mask != 0; mask >>= 1) {
        int t = res - mask;
        if(bit[t] >= cumfre) res = t;
        else cumfre -= bit[t];
    }
    return res;
}

long long solve(int seed, int mul, int add, int n, int k) {
    a[0] = seed;
    for(int i = 1; i < n; ++i)
        a[i] = (1LL * a[i-1] * mul + add) % MAX;
    memset(bit, 0, sizeof bit);
    for(int i = 0; i < k; ++i) update(a[i], 1);
    long long res = 0;
    for(int i = k; i <= n; ++i) {
        res += find((k+1) >> 1) - 1;
        update(a[i-k], -1);
        if(i != n) update(a[i], 1);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    for(int i = 0; i < t; ++i) {
        int seed, mul, add, n, k;
        cin >> seed >> mul >> add >> n >> k;
        cout << "Case #" << i+1 << ": " << solve(seed, mul, add, n, k) << '\n';
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 250005;
const int base = 65536;
using namespace std;
int bit[31][base + 2];
int a[N];
int tt, t, lim;
long long res;

void Upd(int i, int v) {
    while (i <= base) {
        bit[tt][i] += v;
        i += i & (-i);
    }
}

int Get(int i) {
    int s = 0; i++;
    while (i) {
        s += bit[tt][i];
        i -= i & (-i);
    }
    return s;
}

int Find() {
    int l = 0, r = base, m, k;
    while (l <= r) {
        m = (l + r) >> 1;
        if (Get(m) >= lim) {
            k = m; r = m - 1;
        }
        else
            l = m + 1;
    }
    return k;
}

int main()
{
    scanf("%d\n", &t);
    int seed, mul, add, n, k, i, median;
    for(tt=1; tt<=t; tt++) {
        scanf("%d %d %d %d %d\n", &seed, &mul, &add, &n, &k);
        lim = (k + 1) / 2; res = 0;
        a[1] = seed % base; Upd(seed + 1, 1);
        if (k == 1) res += seed;
        for(i=2; i<=n; i++) {
            a[i] = ((long long)a[i-1] * mul + add) % base;
            Upd(a[i] + 1, 1);
            if (i >= k) {
                if (i > k)
                    Upd(a[i - k] + 1, -1);
                median = Find();
                res += median;
            }
        }
        printf("Case #%d: %lld\n", tt, res);
    }
    return 0;
}

Code mẫu của RR

{$R-,Q-}
{$inline on}
const
  FINP='';
  FOUT='';
  MAXN=250011;
  MAXK=5011;
var
  sl,seed,add,n,k,hsize1,hsize2,test,t:longint;
  mul,kq:int64;
  f1,f2:text;
  a,hpos,cs:array[1..MAXN] of longint;
  h1,h2:array[1..MAXK] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
begin
  read(f1,seed,mul,add,n,k);
  sl:=(k+1) shr 1;
end;
procedure init; inline;
var
  i:longint;
begin
  a[1]:=seed;
  for i:=2 to n do
    a[i]:=((int64(a[i-1])*mul) mod 65536+add) mod 65536;
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure down1(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize1) do
    begin
      if (j<hsize1) and (a[h1[j+1]]<a[h1[j]]) then inc(j);
      if (a[h1[j]]<a[h1[i]]) then
        begin
          swap(hpos[h1[i]],hpos[h1[j]]);
          swap(h1[i],h1[j]);
        end
      else exit;
      i:=j; j:=i shl 1;
    end;
end;
procedure up1(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (a[h1[i]]<a[h1[j]]) do
    begin
      swap(hpos[h1[i]],hpos[h1[j]]);
      swap(h1[i],h1[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push1(u:longint); inline;
begin
  inc(hsize1);
  h1[hsize1]:=u; hpos[u]:=hsize1; cs[u]:=1;
  up1(hsize1);
end;
procedure pop1(var u:longint); inline;
begin
  u:=h1[1];
  swap(h1[1],h1[hsize1]);
  hpos[h1[1]]:=1; hpos[u]:=0; cs[u]:=0;
  dec(hsize1);
  down1(1);
end;
procedure down2(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize2) do
    begin
      if (j<hsize2) and (a[h2[j+1]]>a[h2[j]]) then inc(j);
      if (a[h2[j]]>a[h2[i]]) then
        begin
          swap(hpos[h2[j]],hpos[h2[i]]);
          swap(h2[j],h2[i]);
        end
      else exit;
      i:=j; j:=i shl 1;
    end;
end;
procedure up2(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (a[h2[i]]>a[h2[j]]) do
    begin
      swap(hpos[h2[i]],hpos[h2[j]]);
      swap(h2[i],h2[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push2(u:longint); inline;
begin
  inc(hsize2);
  h2[hsize2]:=u; hpos[u]:=hsize2; cs[u]:=2;
  up2(hsize2);
end;
procedure pop2(var u:longint); inline;
begin
  u:=h2[1];
  swap(h2[1],h2[hsize2]);
  hpos[h2[1]]:=1; hpos[u]:=0; cs[u]:=0;
  dec(hsize2);
  down2(1);
end;
procedure solve;
var
  i,u:longint;
begin
  hsize1:=0; hsize2:=0;
  for i:=1 to sl do push2(i);
  for i:=sl+1 to k do
    if a[i]<a[h2[1]] then
      begin
        pop2(u);
        push1(u);
        push2(i);
      end
    else push1(i);
  kq:=a[h2[1]];
  for i:=k+1 to n do
    begin
      if cs[i-k]=1 then
        begin
          a[i-k]:=-1;
          up1(hpos[i-k]);
          pop1(u);
        end
      else
        begin
          a[i-k]:=65537;
          up2(hpos[i-k]);
          if hsize2>0 then pop2(u);
          if hsize1>0 then pop1(u);
          push2(u);
        end;
      if a[i]<a[h2[1]] then
        begin
          pop2(u);
          push1(u);
          push2(i);
        end
      else push1(i);
      inc(kq,a[h2[1]]);
    end;
end;
begin
  openF;
  read(f1,test);
  for t:=1 to test do
    begin
      inp;
      init;
      solve;
      writeln(f2,'Case #',t,': ',kq);
      if t mod 100=0 then writeln('done ',t);
    end;
  closeF;
end.

Code mẫu của hieult

#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
//#include<conio.h>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define mod 65536
#define maxn 250000

int tree[mod+10], x[maxn+10];
long long seed,mul,add,n,k;

void update(int u,int gt){
      while(u<=mod){
            tree[u]+=gt;
            if(u==0) break;
            else u+=(u&-u);
      }
}

int timkiem(int vitri){
      int u = mod,t;
      int bitMask = 1<<15;
      while(bitMask !=0 && u>=1){
           t = u - bitMask;
           if(vitri<=tree[t])  u = t;
           else vitri -= tree[t];
           bitMask >>= 1;
      }
      return u;  
}

int main()
{
      //freopen("MEDIAN.in","r",stdin);
      int test,vt,i;
      long long kq;
      scanf("%d",&test);
      for(int itest = 1;itest<=test;itest++){
           scanf("%lld %lld %lld %lld %lld",&seed,&mul,&add,&n,&k);
           memset(tree,0,sizeof(tree));
           kq = 0;
           vt = (k+1)/2;
           rep(i, n){
                if(i==0) x[i] = seed;
                else x[i] = (x[i-1]*mul+add)%mod;
                //printf("%d ",x[i]);
                update(x[i]+1,1);
                if(i==k-1) kq+=timkiem(vt)-1;
                if(i>=k){
                     update(x[i-k]+1,-1);
                     kq+=timkiem(vt)-1;
                }
           }
           printf("Case #%d: %lld\n",itest,kq);
      }
      //getch();
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define  MAX   250052
using namespace std;
const int minv=0;
const int maxv=(1<<16);
long long a[MAX];
long long res;
int t[4*maxv+77];
int n,k,c;
int seed,mul,add;
void init(void) {
    scanf("%d",&seed);
    scanf("%d",&mul);
    scanf("%d",&add);
    scanf("%d",&n);
    scanf("%d",&k);
    a[0]=seed;
    int i;
    for (i=1;i<n;i=i+1) a[i]=(a[i-1]*mul+add)%maxv;         
    memset(t,0,sizeof t);
    res=0;
}
void update(const long long &x,const int &val) {
    int i,l,m,r;    
    i=1;l=minv;r=maxv;
    while (true) {  
        t[i]+=val;
        if (l>r) return;
        if (l==r) return;
        m=(l+r)/2;
        if (x>m) {
            i=2*i+1;
            l=m+1;
        }
        else {
            i=2*i;
            r=m;
        }
    }
}
int find(int k) {
    int i,l,m,r;    
    i=1;l=minv;r=maxv;  
    while (true) {  
        if (l==r) {         
            return (r);
        }
        m=(l+r)/2;
        if (t[2*i]>=k) {
            i=2*i;
            r=m;            
        }
        else {
            k=k-t[2*i];
            i=2*i+1;
            l=m+1;
        }
    }
}
void process(void) {
    int i;  
    for (i=0;i<k;i=i+1) update(a[i],1);
    for (i=k;i<n;i=i+1) {       
        res+=find((k+1)/2);     
        update(a[i-k],-1);
        update(a[i],1);     
    }
    res+=find((k+1)/2); 
    printf("Case #%d: %lld\n",c,res);
}
int main(void) {
    int t;
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) {
        init();
        process();
    }
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

const int MAX = 65536;

int seed, mul, ad, n, k;

int R[MAX];
int S[MAX*3];

void add( int n, int l, int r, int i, int v) {
    S[n] += v;
    if(l<r) {
        int m = (l+r) / 2;
        if(i<=m) add( 2*n, l, m, i, v);
        else add( 2*n+1, m+1, r, i, v);
    }
}

int get( int n, int l, int r, int k) {
    if(l==r) return l;
    int m = (l+r)/2;
    if(S[2*n]>=k) return get( 2*n, l, m, k);
    else return get( 2*n+1, m+1, r, k - S[2*n]);
}


int main() {
    int st, t;
    scanf("%d", &st);
    for(t=1;t<=st;++t) {
        scanf("%d%d%d%d%d", &seed, &mul, &ad, &n, &k);
        memset( R, -1, sizeof(R));
        memset( S, 0, sizeof(S));
        long long begin = seed, end;
        for(int i=0;i<k;++i) {
            add( 1, 0, MAX-1, begin, 1);
            begin = (begin * mul % MAX + ad) % MAX;
        }
        end = begin;
        begin = seed;
        long long total = 0;
        for(int i=0;i<=n-k;++i) {
            if(R[begin]!=-1) {
                total += R[begin];
            }
            else {
                int tmp = get( 1, 0, MAX-1, (k+1)/2 );
                R[begin] = tmp;
                total += tmp;
                add( 1, 0, MAX-1, begin, -1);
                add( 1, 0, MAX-1, end, 1);
            }
            begin = (begin * mul % MAX + ad) % MAX;
            end = (end * mul % MAX + ad) % MAX;
        }
        printf("Case #%d: %lld\n", t, total);
    }
    return 0;
}