Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : DCP-523: Everything equal 2
Source : DevSkill
Category : Data Structure
Algorithm : Merge Sort Tree
Verdict : Time Limit Exceeded
- #include "bits/stdc++.h"
-
- using namespace std;
-
- #define ll long long int
- #define inf 1e18
-
- static const int maxn = 5e4 + 5;
-
- struct MergeSortTree
- {
- #define vll vector <ll>
- #define eb emplace_back
- #define sz(v) (int)v.size()
-
- vll v;
- vll stree;
-
- inline void assignLeaf(ll val)
- {
- v.eb(val);
- }
- inline void marge(const MergeSortTree &lft, const MergeSortTree &rgt)
- {
- int lenLeft = sz(lft.v);
- int lenRight = sz(rgt.v);
- int idLeft = 0;
- int idRight = 0;
- while (idLeft < lenLeft && idRight < lenRight)
- {
- ll numLeft = lft.v[idLeft];
- ll numRight = rgt.v[idRight];
- if (numLeft < numRight)
- {
- v.eb(numLeft);
- ++idLeft;
- }
- else
- {
- v.eb(numRight);
- ++idRight;
- }
- }
- while (idLeft < lenLeft)
- {
- v.eb(lft.v[idLeft]);
- ++idLeft;
- }
- while (idRight < lenRight)
- {
- v.eb(rgt.v[idRight]);
- ++idRight;
- }
- }
- inline void reSize()
- {
- int len = sz(v);
- stree.resize(len+1);
- }
- inline void build()
- {
- int len = sz(v);
- stree[0] = v[0];
- for (int i = 1; i < len; i++) stree[i] = stree[i-1] + v[i];
- }
- inline ll getSum(int i, int j)
- {
- if (i > j) return 0;
- ll sum = stree[j];
- if (i > 0) sum -= stree[i-1];
- return sum;
- }
- inline int getPos(ll val)
- {
- int lo = 0;
- int hi = sz(v)-1;
- int ans = -1;
- while (lo <= hi)
- {
- int mid = lo + (hi - lo) / 2;
-
- if (v[mid] <= val)
- {
- ans = mid;
- lo = mid + 1;
- }
- else
- {
- hi = mid - 1;
- }
- }
- return ans;
- }
- inline ll sum(ll val)
- {
- int len = sz(v);
- if (len == 1)
- {
- return abs(val - v[0]);
- }
- int pos = getPos(val);
- if (pos < 0) return inf;
- ll presum = getSum(0, pos);
- ll aftsum = getSum(pos+1, len-1);
- ll need = (aftsum - (len-1-pos) * val);
- need += ((pos+1) * val - presum);
- return need;
- }
- } Tree[maxn << 2];
-
- ll arr[maxn];
- int n, q;
-
- inline void build(int node, int a, int b)
- {
- if (a == b)
- {
- Tree[node].assignLeaf(arr[a]);
- return;
- }
- int lft = node << 1;
- int rgt = lft | 1;
- int mid = (a + b) >> 1;
- build(lft, a, mid);
- build(rgt, mid+1, b);
- Tree[node].marge(Tree[lft], Tree[rgt]);
- Tree[node].reSize();
- Tree[node].build();
- }
-
- inline ll query(int node, int a, int b, int i, int j, ll val)
- {
- if (a == i && b == j)
- {
-
- return Tree[node].sum(val);
- }
- int lft = node << 1;
- int rgt = lft | 1;
- int mid = (a + b) >> 1;
- ll res = 0;
- if (j <= mid)
- {
- res += query(lft, a, mid, i, j, val);
- }
- else if (i > mid)
- {
- res += query(rgt, mid+1, b, i, j, val);
- }
- else
- {
- res += query(lft, a, mid, i, mid, val);
- res += query(rgt, mid+1, b, mid+1, j, val);
- }
- return res;
- }
-
- inline ll TernarySearch(int l, int r)
- {
- ll lo = 1;
- ll hi = 1e9;
- ll mini = hi;
- ll ans = hi;
- while (1)
- {
- if (hi - lo <= 2)
- {
- ll need = query(1, 1, n, l, r, lo);
- if (need < mini) mini = need, ans = lo;
- need = query(1, 1, n, l, r, lo+1);
- if (need < mini) mini = need, ans = lo + 1;
- need = query(1, 1, n, l, r, hi);
- if (need < mini) mini = need, ans = hi;
- break;
- }
- ll mid1 = lo + (hi - lo) / 3;
- ll mid2 = hi - (hi - lo) / 3;
- ll needMid1 = query(1, 1, n, l, r, mid1);
- ll needMid2 = query(1, 1, n, l, r, mid2);
- if (needMid1 < needMid2)
- {
- if (needMid1 < mini) mini = needMid1, ans = mid1;
- hi = mid2;
- }
- else
- {
- if (needMid2 < mini) mini = needMid2, ans = mid2;
- lo = mid1;
- }
- }
-
- return mini;
- }
-
- int main()
- {
-
-
- int tc;
- scanf("%d", &tc);
- for (int tcase = 1; tcase <= tc; tcase++)
- {
- scanf("%d %d", &n, &q);
- for (int i = 1; i <= n; i++) scanf("%d", arr+i);
- build(1, 1, n);
- while (q--)
- {
- int l, r;
- scanf("%d %d", &l, &r);
- if (l == r)
- {
- puts("0");
- continue;
- }
- ll need = TernarySearch(l, r);
- printf("%lld\n", need);
- }
- for (int i = 0; i < (maxn << 2); i++)
- {
- Tree[i].v.clear();
- Tree[i].stree.clear();
- }
- }
- }
