关于离散化去重
查看原帖
关于离散化去重
555381
zlttcl楼主2023/11/25 14:33

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;
}


注释掉的是去重的部分。

2023/11/25 14:33
加载中...