后面一半WA求条

yupeishan2012 @ 2024-10-11 19:28:47

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

long long n;
long long a[100005],b[100005],c[100005];
long long ans;

inline void read(register long long &a){
    a = 0;
    char c;
    while((c = getchar()) < 48);
    do a = (a << 3) + (a << 1) + (c ^ 48);
    while((c  = getchar()) > 47);
}

void write(register long long v){
    if(v < 10) putchar(v|48);
    else write(v / 10),putchar(v % 10 | 48);
}

long long cmp(long long j,long long k){
    if(a[j] == a[k]) return j > k;
    return a[j] > a[k];
}

long long lowbit(int k){
    return k & -k;
}

void x(long long k){
    while(k <= n){
        b[k] ++;
        k += lowbit(k);
    }
    return ;
}

long long sum;

long long y(int k){
    sum = 0;
    while(k >= 1){
        sum += b[k];
        k -= lowbit(k);
    }
    return sum;
}

int main(){
    read(n);
    for(long long i = 1; i <= n; i++){
        read(a[i]);
        c[i] = i;
    }
    sort(c + 1,c + 1 + n,cmp);
    for(long long i = 1; i <= n; i++){
        x(c[i]);
        ans += y(c[i] - 1);
    }
    write(ans);
    return 0;
}

by ggpw_XNW @ 2024-10-11 20:05:25

@yupeishan2012 你数组果然开小了23333333333333333333333333333333333

by yupeishan2012 @ 2024-10-11 20:05:45

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

long long n;
long long b[100005];
long long ans;

struct node{
    long long num;
    long long value;
    long long gl;
}a[100005];

inline void read(register long long &a){
    a = 0;
    char c;
    while((c = getchar()) < 48);
    do a = (a << 3) + (a << 1) + (c ^ 48);
    while((c  = getchar()) > 47);
}

void write(register long long v){
    if(v < 10) putchar(v|48);
    else write(v / 10),putchar(v % 10 | 48);
}

long long cmp(node j,node k){
    if(j.value == k.value) return j.num > k.num;
    return j.value > k.value;
}

long long lowbit(int k){
    return k & -k;
}

void x(long long k){
    while(k <= n){
        a[k].gl ++;
        k += lowbit(k);
    }
    return ;
}

long long sum;

long long y(int k){
    sum = 0;
    while(k >= 1){
        sum += b[k];
        k -= lowbit(k);
    }
    return sum;
}

int main(){
    read(n);
    for(long long i = 1; i <= n; i++){
        read(a[i].value);
        a[i].num = i;
    }
    sort(a + 1,a + 1 + n,cmp);
    for(long long i = 1; i <= n; i++){
        x(a[i].num);
        ans += y(a[i].num - 1);
    }
    write(ans);
    return 0;
}

by ggpw_XNW @ 2024-10-11 20:05:54

@yupeishan2012 把数组开大点就A了

by yupeishan2012 @ 2024-10-11 20:06:38

@User1025109 不是我样例输出0

by ggpw_XNW @ 2024-10-11 20:06:41

@yupeishan2012 AC记录

by yupeishan2012 @ 2024-10-11 20:07:16

@User1025109 我代码？

by ggpw_XNW @ 2024-10-11 20:07:23

@yupeishan2012 用原来的代码，数组开到500005

by ggpw_XNW @ 2024-10-11 20:08:31

@yupeishan2012 是的

by yupeishan2012 @ 2024-10-11 20:09:06

那为什么不是re是wa

by ggpw_XNW @ 2024-10-11 20:10:02

@yupeishan2012 自己看数据范围，5\times10^5