RT,本题手动去重会挂成30pts 。
为什么
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N = 1e5 + 10;
ll n, a[N], c[N], tree[N << 2], ans;
inline ll read(){
ll x = 0, m = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') m = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * m;
}
inline void write(ll x){
if(x < 0){
putchar('-');
write(-x);
return;
}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
inline int lowbit(int x){
return x & -x;
}
inline void add(int x, int k){
for(; x <= n; x += lowbit(x)) tree[x] += k;
}
inline int query(int x){
ll anss = 0;
for(int i = x; i >= 1; i -= lowbit(i)) anss += tree[i];
return anss;
}
struct Code{
int sum, id;
}b[N];
inline bool cmp(Code x, Code y){
return x.sum < y.sum || (x.sum == y.sum && x.id < y.id);
}
signed main(){
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read();
for(int i = 1; i <= n; ++ i){
a[i] = read();
b[i].sum = a[i], b[i].id = i;
}
sort(b + 1, b + 1 + n, cmp);
b[0].sum = -1;
int sum = 0;
for(int i = 1; i <= n; ++ i){
// if(b[i].sum != b[i - 1].sum) ++ sum;
a[b[i].id] = (++ sum);
}
ans = 1;
for(int i = 1; i <= n; ++ i){
add(a[i], 1);
ans = max(ans, (i - query(i)) * 1ll);
}
write(ans);
return 0;
}
注释掉的是去重的部分。