Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define mp make_pair
- #define fs first
- #define sc second
- #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
- using namespace std;
- typedef long long ll;
- const int t_sz = 270000;
- const int K = 360;
- const int maxn = 128100;
- ll sum_x[maxn];
- int a[maxn];
- int b[maxn];
- int A[maxn];
- int B[maxn];
- map<int, int> ma, mb;
- vector<pair<pair<int, int>, int> > q[maxn / K + 10];
- ll sum[t_sz];
- int cnt[t_sz];
- int ans[100100];
- bool cmp(const pair<pair<int, int>, int> &a,
- const pair<pair<int, int>, int> &b) {
- return a.fs.sc < b.fs.sc;
- }
- void upd(int v, int l, int r, int i, int val, int Al) {
- if (l == r - 1) {
- cnt[v] += val;
- sum[v] += Al * val;
- return;
- }
- int m = (l + r) / 2;
- if (i < m) {
- upd(v * 2, l, m, i, val, Al);
- } else {
- upd(v * 2 + 1, m, r, i, val, Al);
- }
- sum[v] = sum[v * 2] + sum[v * 2 + 1];
- cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
- }
- int get_sum(int v, int l, int r, int k) {
- if (l == r - 1) {
- int cur = min(cnt[v], k);
- return cur * (sum[v] / cnt[v]);
- }
- int m = (l + r) / 2;
- if (k == cnt[2 * v + 1]) {
- return sum[2 * v + 1];
- } else if (k < cnt[2 * v + 1]) {
- return get_sum(2 * v + 1, m, r, k);
- } else {
- return sum[2 * v + 1] + get_sum(2 * v, l, m, k - cnt[2 * v + 1]);
- }
- }
- int main() {
- int n;
- cin >> n;
- forn (i, n) {
- cin >> a[i];
- }
- forn (i, n) {
- cin >> b[i];
- }
- forn (i, n) {
- int x = min(a[i], b[i]);
- a[i] -= x;
- b[i] -= x;
- sum_x[i + 1] = sum_x[i] + x;
- }
- forn (i, n) {
- A[i] = a[i];
- }
- sort(A, A + n);
- forn (i, n) {
- ma[A[i]] = i;
- }
- forn (i, n) {
- B[i] = b[i];
- }
- sort(B, B + n);
- forn (i, n) {
- mb[B[i]] = i;
- }
- forn (i, n) {
- a[i] = ma[a[i]];
- b[i] = mb[b[i]];
- }
- int m;
- cin >> m;
- forn (i, m) {
- int l, r;
- cin >> l >> r;
- --l;
- ans[i] += (sum_x[r] - sum_x[l]) * 2;
- q[l / K].pb(mp(mp(l, r), i));
- }
- forn (i, maxn / K + 1) {
- sort(q[i].begin(), q[i].end(), cmp);
- }
- forn (i, maxn / K + 1) {
- forn (j, t_sz) {
- cnt[j] = sum[j] = 0;
- }
- int l = K * i, r = l;
- forn (j, q[i].size()) {
- int nl = q[i][j].fs.fs, nr = q[i][j].fs.sc;
- while (l < nl) {
- upd(1, 0, n, a[l], -1, A[a[l]]);
- ++l;
- }
- while (l > nl) {
- --l;
- upd(1, 0, n, a[l], 1, A[a[l]]);
- }
- while (r < nr) {
- upd(1, 0, n, a[r], 1, A[a[r]]);
- ++r;
- }
- while (r > nr) {
- --r;
- upd(1, 0, n, a[r], -1, A[a[r]]);
- }
- ans[q[i][j].sc] += get_sum(1, 0, n, 2 * (r - l) / 3);
- ans[q[i][j].sc] += get_sum(1, 0, n, (r - l) / 3);
- }
- }
- forn (i, maxn / K + 1) {
- forn (j, t_sz) {
- cnt[j] = sum[j] = 0;
- }
- int l = K * i, r = l;
- forn (j, q[i].size()) {
- int nl = q[i][j].fs.fs, nr = q[i][j].fs.sc;
- while (l < nl) {
- upd(1, 0, n, b[l], -1, B[b[l]]);
- ++l;
- }
- while (l > nl) {
- --l;
- upd(1, 0, n, b[l], 1, B[b[l]]);
- }
- while (r < nr) {
- upd(1, 0, n, b[r], 1, B[b[r]]);
- ++r;
- }
- while (r > nr) {
- --r;
- upd(1, 0, n, b[r], -1, B[b[r]]);
- }
- ans[q[i][j].sc] += get_sum(1, 0, n, 2 * (r - l) / 3);
- ans[q[i][j].sc] += get_sum(1, 0, n, (r - l) / 3);
- }
- }
- forn (i, m) {
- cout << (ans[i] / 2);
- if (ans[i] % 2) {
- cout << ".5";
- }
- cout << endl;
- }
- }
Add Comment
Please, Sign In to add comment