HYdroKomide @ 2021-11-26 19:25:51
大部分树状数组写法的题解貌似都没有判重,导致错误,希望管理撤下。
@StudyingFather
by HYdroKomide @ 2021-11-26 19:26:16
@StudyingFather 望撤下
by StillEmpty @ 2021-11-26 19:44:17
你搞错了啊
by StillEmpty @ 2021-11-26 19:50:18
我来口述一遍:
by StillEmpty @ 2021-11-26 19:51:16
观察bucket的询问和修改特性,发现可以用线段树/树状数组维护
by StillEmpty @ 2021-11-26 19:52:34
@Kevin_FOS
by HYdroKomide @ 2021-11-26 19:54:18
@Kobayashi 但也确实许多题解都有错误
by StillEmpty @ 2021-11-26 19:59:05
@Kevin_FOS 我给你看一眼我的代码(省去了线段树部分,就是给你看一眼逻辑,你说有什么问题)
#include <bits/stdc++.h>
#define MAXN 500000
using namespace std;
int n, tar;
unsigned long long sum = 0;
int ranking[MAXN+1];
pair<int, int> a[MAXN+1];
int cnt[MAXN*4+1], l[MAXN*4+1], r[MAXN*4+1];
void init(int k, int lp, int rp) {
...
}
int query(int k) { // return the cnt of bucket(tar, maxa]
...
}
void update(int k) {
...
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].first;
a[i].second = i;
}
sort(a+1, a+n+1);
for(int i = 1, j = 0; i <= n; i++) {
if(a[i].first != a[i-1].first) {
j++;
}
ranking[a[i].second] = j;
}
init(1, 1, n);
for(int i = 1; i <= n; i++) {
tar = ranking[i];
sum += query(1);
update(1);
}
cout << sum << endl;
return 0;
}
by StillEmpty @ 2021-11-26 20:00:45
@Kobayashi 注:2.
和3.
的i是两个东西
by HYdroKomide @ 2021-11-26 20:04:30
@Kobayashi 我的意思是看见了题解区里不少的题解都没有加上去重,就错了。
by StillEmpty @ 2021-11-26 20:06:18
@Kevin_FOS 你是说离散化?