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>
#include <cstdio>
#define delta 100010
using namespace std;

int f[200200];

int main()
{
    int n,k,x=delta,s=0;
    long long re=0;
    cin >> n >> k;
    while (x<=n+delta) f[x]++, x+=x&-x;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if (x>=k) s++;
        else s--;
        x=s+delta;
        while (x) re+=f[x], x-=x&-x;
        x=s+delta;
        while (x<=n+delta) f[x]++, x+=x&-x;
    }
    cout << re << endl;
}

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 1e5;
int sum[N+1], bit[N+1], a[N], n, x, m;

void enter() {
    cin >> n >> x;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] = a[i] >= x ? 1 : -1;
    }
}

void generate() {
    sum[0] = 0;
    for(int i = 0; i < n; ++i)
        sum[i+1] = sum[i] + a[i];
    m = n + 1;
    sort(sum, sum + m);
    m = unique(sum, sum + m) - sum;
}

int get(int idx) {
    int res = 0;
    for(int x = idx; x >= 0; x -= ~x & (x + 1))
        res += bit[x];
    return res;
}

void update(int idx, int v) {
    for(int x = idx; x < m; x += ~x & (x + 1))
        bit[x] += v;
}

void solve() {
    update(lower_bound(sum, sum + m, 0) - sum, 1);
    int s = 0;
    long long res = 0;
    for(int i = 0; i < n; ++i) {
        s += a[i];
        int v = lower_bound(sum, sum + m, s) - sum;
        res += get(v);
        update(v, 1);
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    generate();
    solve();
    return 0;
}

Code mẫu của ladpro98

program KMEDIAN;
uses    math;
const   maxn=2*trunc(1e5)+5;
        lb=trunc(1e5)+5;
        fi='';
var     bit:array[1..maxn] of longint;
        a,s,n,k,i,t,lim:longint;
        res:int64;
        inp:text;

procedure update(i:longint);
begin
        while i<=lim do begin
                inc(bit[i]);
                i:=i+i and (-i);
        end;
end;

function get(i:longint):longint;
var     sum:longint;
begin
        sum:=0;
        while i>0 do begin
                inc(sum,bit[i]);
                i:=i-i and (-i);
        end;
        exit(sum);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,n,k);
        s:=n+1;lim:=s+n;
        update(s);
        for i:=1 to n do begin
                readln(inp,a);
                if a>=k then inc(s);
                if a<k then dec(s);
                inc(res,get(s));
                update(s);
        end;
        write(res);
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

int n, x, bit[200111];

#define _(x) ((x) & (-(x)))

void update(int u) {
    while (u <= 200000) {
        bit[u]++;
        u += _(u);
    }
}

int get(int u) {
    int res = 0;
    while (u) {
        res += bit[u];
        u -= _(u);
    }
    return res;
}

int main() {
    while (scanf("%d%d", &n, &x) == 2) {
        memset(bit, 0, sizeof bit);
        int s = 100000, u;
        update(100000);
        long long res = 0;
        FOR(i,1,n) {
            scanf("%d", &u);
            if (u >= x) ++s;
            else --s;
            res += get(s);
            update(s);
        }
        cout << res << endl;
    }
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 100111
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int x,t,so,a[100111],MIN;
long long kq = 0,f[100011] = {0};

void update(int u){
     while(u<=100000){
          f[u]++;
          u+=u&-u; 
     }
}

long long tinh(int u){
     long long r = 0;
     while(u>0){
          r+=f[u];
          u-=u&-u;

     }
     return r;
}

int main(){
    // freopen("I.10","r",stdin);
    // freopen("KMEDIAN.out","w",stdout);
     int n,k;
     cin>>n>>k;
     so = 0;
     a[0] = 0;
     MIN = 0; 
     for(int i = 1;i<=n;i++){   
         scanf("%d",&x);
         if(x>=k) so++;
         a[i] = so*2-i;
         MIN = min(MIN,a[i]);
     }
     for(int i = 0;i<=n;i++){
         a[i] = a[i]-MIN+1;
         kq+=tinh(a[i]);
         update(a[i]);
     }   
     cout<<kq;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define maxn 100010
using namespace std;

int n,x;
pair<int,int> s[maxn];
int tx[maxn];

int main() {
//    freopen("median.in","r",stdin);
//    freopen("median.out","w",stdout);
    scanf("%d %d", &n, &x);
    s[1] = make_pair(0,1);
    for (int i = 2; i <= n + 1; i++) {
        scanf("%d", &s[i].first);
        if (s[i].first >= x) s[i].first = 1; else s[i].first = -1;
        s[i].first += s[i - 1].first;
        s[i].second = i;
    }
    sort(s + 1,s + n + 2);
    long long ret = 0;
    for (int i = 1; i <= n + 1; i++) {
        int u = s[i].second;
        for (int v = u; v; v -= (v & -v)) ret += tx[v];
        for (int v = u; v <= n + 1; v += (v & -v)) tx[v]++;
    }
    cout << ret << endl;
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
int s[MAX];
int t[MAX];
int c[MAX];
int n;
vector<int> val;
void init(void) {
    int v,x;
    scanf("%d",&n);
    scanf("%d",&x);
    val.push_back(0);
    FOR(i,1,n) {
        scanf("%d",&v);
        s[i]=s[i-1]+(v>=x)-(v<x);
        val.push_back(s[i]);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    REP(i,n+1) c[i]=lower_bound(val.begin(),val.end(),s[i])-val.begin()+1;
}
void update(int x) {
    while (1<=x && x<=n+7) {
        t[x]++;
        x+=x&(-x);
    }
}
int count(int x) {
    int ret=0;
    while (1<=x && x<=n+7) {
        ret+=t[x];
        x=x&(x-1);
    }
    return (ret);
}
void process(void) {
    long long res=0LL;
    FOR(i,0,n) {
        res+=count(c[i]);
        update(c[i]);
    }
    printf("%lld",res);
}
int main(void) {
    init();
    process();
    return 0;
}