結果
| 問題 | No.5012 Better Mo's Algorithm is Needed!! (Execute) |
| ユーザー |
 conlacda
|
| 提出日時 | 2024-07-11 23:40:23 |
| 言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,897 bytes |
| コンパイル時間 | 4,917 ms |
| コンパイル使用メモリ | 308,548 KB |
| 実行使用メモリ | 14,268 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-07-11 23:41:42 |
| 合計ジャッジ時間 | 78,061 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | WA | - |
| testcase_64 | TLE | - |
| testcase_65 | TLE | - |
| testcase_66 | TLE | - |
| testcase_67 | TLE | - |
| testcase_68 | TLE | - |
| testcase_69 | TLE | - |
| testcase_70 | TLE | - |
| testcase_71 | TLE | - |
| testcase_72 | TLE | - |
| testcase_73 | TLE | - |
| testcase_74 | TLE | - |
| testcase_75 | TLE | - |
| testcase_76 | TLE | - |
| testcase_77 | TLE | - |
| testcase_78 | TLE | - |
| testcase_79 | TLE | - |
| testcase_80 | TLE | - |
| testcase_81 | TLE | - |
| testcase_82 | TLE | - |
| testcase_83 | TLE | - |
| testcase_84 | TLE | - |
| testcase_85 | TLE | - |
| testcase_86 | TLE | - |
| testcase_87 | TLE | - |
| testcase_88 | TLE | - |
| testcase_89 | TLE | - |
| testcase_90 | TLE | - |
| testcase_91 | TLE | - |
| testcase_92 | TLE | - |
| testcase_93 | TLE | - |
| testcase_94 | TLE | - |
| testcase_95 | TLE | - |
| testcase_96 | TLE | - |
| testcase_97 | TLE | - |
| testcase_98 | TLE | - |
| testcase_99 | TLE | - |
ソースコード
// https://judge.yosupo.jp/problem/static_range_inversions_query
#pragma GCC optimize("O3") // optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
typedef long long ll; // double long double
const ll mod = 1000000007; // 998244353 1000000009 1000000007 // đừng dùng ull
#define int long long // __int128
const int INF = std::numeric_limits<int>::max(); // INT32_MAX DBL_MAX
using namespace std;
#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#endif
template<typename T = int>
struct Compress {
vector<T> rcv; // recover - giá trị mảng ban đầu đã sort và xóa unique
vector<T> cpr; // compressed - giá trị đã nén của mảng a
Compress() {}
Compress(vector<T>& a) { build(a);}
void build(vector<T>& a) {
rcv = a;
sort(rcv.begin(), rcv.end());
rcv.resize(unique(rcv.begin(), rcv.end()) - rcv.begin());
cpr.resize(a.size());
for (int i = 0; i < (int) cpr.size(); ++i)
cpr[i] = lower_bound(rcv.begin(), rcv.end(), a[i]) - rcv.begin(); // O(logN) thay cho map
}
T compressed_val(T originalVal) { // giá trị ban đầu sang giá trị đã compress
T i = lower_bound(rcv.begin(), rcv.end(), originalVal) - rcv.begin();
if (rcv[i] != originalVal) return -1;
return i;
}
T operator[] (int index) {
return cpr[index];
}
T original_val(T compressedVal) {
return rcv[compressedVal];
}
};
// Range query, point update
template <typename T = int>
struct FenwickTree {
private:
vector<T> bit; // binary indexed tree
T n;
public:
FenwickTree(){}
void build(T n) { this->n = n; bit.assign(n, 0); }
void build(vector<T> a) { build(a.size()); for (int i = 0; i < (int) a.size(); i++) add(i, a[i]); }
FenwickTree(vector<T> a) { build(a); }
T sum(T r) {
if (r==-1) return 0;
T ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
return ret;
}
T sum(T l, T r) {
if (!(0 <= l && l <= r && r < n)) return 0;
// assert(0 <= l && l <= r && r < n);
return sum(r) - sum(l-1);
}
void add(T idx, T delta) {
assert(0 <= idx && idx < n);
for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
}
void set(T idx, T val) {
T diff = val - sum(idx, idx);
add(idx, diff);
}
vector<T> original(){ // Return original value of input vector
vector<T> a;
for (T i=0;i<this->n;i++) a.push_back(sum(i,i));
return a;
}
int sum_from(int idx) {
return sum(idx, n-1);
}
// Tìm ra index x nhỏ nhất để sum(start_index, x) >= K
// nếu không có x nào thỏa mãn -> return n-1
int firstIndexWithSumFromK(int start_index, int K) {
int l = start_index, r = n-1;
while (l < r) {
int mid = (l + r) / 2;
if (sum(start_index, mid) >= K) r = mid;
else l = mid + 1;
}
return l;
}
};
inline int64_t hilbertOrder(int x, int y, int pow = 21, int rotate = 0) { // 2**pow là số lượng query sẽ xử lý
if (pow == 0) return 0;
int hpow = 1 << (pow-1);
int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
seg = (seg + rotate) & 3;
const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
int nrot = (rotate + rotateDelta[seg]) & 3;
int64_t subSquareSize = int64_t(1) << (2*pow - 2);
int64_t ans = seg * subSquareSize;
int64_t add = hilbertOrder(nx, ny, pow-1, nrot);
ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
return ans;
}
struct Query {
int l, r, index;
ll ord = -1;
friend bool operator<(Query& a, Query& b) {
return a.ord < b.ord;
}
};
struct Mo {
private:
vector<int> a; // mảng đầu vào
public:
FenwickTree<int> fw;
vector<int> ans;
int cur_result = 0; // giá trị hiện tại, đối với những bài giá trị tuyến tính khi add, remove thì dùng, ko thì tính trực tiếp từ mảng data
Mo(vector<int>& a) {
this->a = a;
fw = FenwickTree(vector<int>(a.size(), 0));
}
void addLeft(int index) {
cur_result += fw.sum(0, a[index] - 1);
fw.add(a[index], 1);
}
void addRight(int index) {
cur_result += fw.sum_from(a[index] + 1);
fw.add(a[index], 1);
}
void removeLeft(int index) {
cur_result -= fw.sum(0, a[index] - 1);
fw.add(a[index], -1);
}
void removeRight(int index) {
cur_result -= fw.sum_from(a[index] + 1);
fw.add(a[index], -1);
}
ll getResult() {
return this->cur_result;
}
vector<int> solve(vector<Query>& queries) {
for (auto& q: queries) q.ord = hilbertOrder(q.l, q.r);
sort(queries.begin(), queries.end());
ans.resize(queries.size());
ll left = 0, right = -1;
for (auto query: queries) {
while (left > query.l) left--, addLeft(left);
while (right < query.r) right++, addRight(right);
while (left < query.l) removeLeft(left), left++;
while (right > query.r) removeRight(right), right--;
ans[query.index] = getResult();
}
return ans;
}
};
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cout << std::fixed << setprecision(15);
#ifdef DEBUG
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, q;
cin >> n >> q;
vector<int> a(n);
for (auto&v: a) cin >> v;
Compress com(a);
a = com.cpr;
Mo mo(a);
vector<Query> queries;
for (int i=0;i<q;i++) {
int u, v;
cin >> u >> v;
u--; v--;
queries.push_back({u, v, i});
}
mo.solve(queries);
for (auto v: mo.ans) cout << v << '\n';
// dbg(mo.ans);
cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s✅\n";
}
/*
Bài này dùng Mo
Khi này data (cửa số dữ liệu) sẽ duy trì 1 set.
Bài toán khi này trở thành thêm 1 phần tử vào trái thì có bao nhiêu phần tử phải nhỏ hơn nó
và thêm vào phải thì trái bao nhiêu phần tử lớn hơn nó
Thoạt nhìn thì có thể sử dụng set để thêm 1 phần tử rồi theo order
rồi dùng binary search tìm ra được có bao nhiêu số lớn/nhỏ hơn nó
=> thực ra thì ko có cách nào cả với set kể cả policy based set
Tại đây sử dụng fenwicktree.
* Compress mảng thành dạng index
* Dựng fenwicktree với mảng full 0
* thêm phần tử thì tăng index đó lên 1
* đếm số lượng phần tử nhỏ hơn hay lớn hơn thì đơn giản là lấy sum vì khi này a[index] chính là index trên fw
=> cửa sổ dữ liệu được maintain bằng cách sử dụng fw
*/