wa
  • 板块P2804 神秘数字
  • 楼主jJHZ
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/2 15:47
  • 上次更新2025/2/2 21:40:28
查看原帖
wa
1023228
jJHZ楼主2025/2/2 15:47
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define TLE  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long

using namespace std;
int a[1000000];
int ranks[100000], tree[500010];
int n, m;
struct jhz{
    int num, val;
}sum[1000000];
bool cmp(jhz a,jhz b){
    if(a.val==b.val){
        return a.num < b.num;
    }
    return a.val < b.val;
}
inline void insert(int p, int d)
{
    for (; p <= n; p += p & -p)
        tree[p] += d;
}
inline int query(int p)
{
    int sum = 0;
    for (; p; p -= p & -p)
        sum += tree[p];
    return sum;
}
int tre1e(){
    sort(sum, sum + n + 1, cmp);
    for (int i = 1; i <= n;i++){
        ranks[sum[i].num] = i;
    }
    int ans;
    for (int i = 1; i <= n; i++)
    {
        insert(ranks[i], 1);
        ans += query(ranks[i]);
    }
    return ans;
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n;i++){
        cin >> a[i];
        a[i] -= m;
        sum[i].val = sum[i - 1].val + a[i];
        sum[i].num = i;
    }
    cout<<tre1e();

    return 0;
}

2025/2/2 15:47
加载中...