526互联

2024.1.6做题纪要

发布时间 2024-01-07 08:24:28作者: 觉清风

P4390 [BalkanOI2007] Mokia 摩基亚 / （离线）简单题

第一眼看题，emmm，跟分治有半毛钱关系啊！！！！这每次分治一次不直接复杂度爆炸？？

冷静下来后，我们发现对于一个点，对于区间产生贡献充要条件是他的 \(x\) 轴要在区间内。

所以。。。我们是不是可以离线下来对于 \(x\) 轴排一遍序，我们只有左半部分的点会对右半部分产生贡献。

而且我们可以对于一次询问的左下角和右上角拆成两个点，右上角的前缀和减去左下角的前缀和就是答案。

用之前三维偏序的方法处理 \(y\) 轴就行了。

HOI4 
#include <bits/stdc++.h>

class Ask {
public:
    int opt, x[2], y[2], a, id;
}number[200000];

int N, W, tot;
int flag[210000];
int answer[210000];

class Position1 {
public:
    int x, y, val;
}pos[210000];

class Position2 {
public:
    int x, y1, y2, id;
}temp[210000];

class Binary_indexed_tree {
    #define lowbit(x) (x & (-x))

public:
    int number[2100000];
    
    void Insert(int position, int val) {
        while (position <= W) {
            number[position] += val;
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = 0;
        while (position) {
            result += number[position];
            position -= lowbit(position);
        }
        return result;
    }
}tree;

bool cmp1(const Position1 &a, const Position1 &b) {
    return a.x < b.x;
}

bool cmp2(const Position2 &a, const Position2 &b) {
    return a.x < b.x;
}

void CDQ(int l, int r) {
    if (l == r)
        return;
    
    int mid = (l + r) >> 1;

    CDQ(l, mid);
    CDQ(mid + 1, r);

    int top1 = 0, top2 = 0;
    for (int i = l; i <= mid; ++ i) 
        if (number[i].opt == 1) 
            pos[++ top1] = {number[i].x[0], number[i].y[0], number[i].a};
        
    for (int i = mid + 1; i <= r; ++ i) {
        if (number[i].opt == 2) {
            temp[++ top2] = {number[i].x[0] - 1, number[i].y[0], number[i].y[1], number[i].id};
            temp[++ top2] = {number[i].x[1], number[i].y[0], number[i].y[1], number[i].id};
        }
    }
    std::sort(pos + 1, pos + 1 + top1, cmp1);
    std::sort(temp + 1, temp + 1 + top2, cmp2);

    int I = 1, J = 1;

    while (I <= top1 && J <= top2) {
        if (pos[I].x <= temp[J].x) {
            tree.Insert(pos[I].y, pos[I].val);
            I ++;
        }
        else {
            int ID = temp[J].id;
            answer[ID] += flag[ID] * (tree.Query(temp[J].y2) - tree.Query(temp[J].y1 - 1));
            flag[ID] *= -1;
            J ++;
        }
    }
    while (J <= top2) {
        int ID = temp[J].id;
        answer[ID] += flag[ID] * (tree.Query(temp[J].y2) - tree.Query(temp[J].y1 - 1));
        flag[ID] *= -1;
        J ++;
    }

    for (int i = 1; i <= I - 1; ++ i)
        tree.Insert(pos[i].y, -pos[i].val);
}

int cnt;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    memset(flag, -1, sizeof(flag));
    std::cin >> W >> W;
    std::cin >> number[++ tot].opt;
    while (number[tot].opt != 3) {
        if (number[tot].opt == 1) {
            std::cin >> number[tot].x[0] >> number[tot].y[0] >> number[tot].a;
        }
        else {
            number[tot].id = ++ cnt;
            std::cin >> number[tot].x[0] >> number[tot].y[0] >> number[tot].x[1] >> number[tot].y[1];
        }
        std::cin >> number[++ tot].opt;
    }
    N = tot - 1;
    tot = 0;
    CDQ(1, N);
    for (int i = 1; i <= cnt; ++ i)
        std::cout << answer[i] << '\n';
    return 0;
}

P4169 [Violet] 天使玩偶/SJY摆棋子

把绝对值拆成 \(4\) 部分，对于每一个询问都有左上，左下，右上，右下的点来维护。

好麻烦啊。。cdq都这么麻烦吗QAQ。

EU4 
#include <bits/stdc++.h>

const int end = 1e6 + 10;

int N, M, cnt;
int answer[501000];

class Position {
public:
    int x, y, opt, id;
}ask[1010000], pos[1010000];

class Binary_Inexed_Tree {
    #define lowbit(x) (x & (-x))

public:
    int min[2010000];
    Binary_Inexed_Tree() {
        for (int i = 1; i <= 2 * end + 10; ++ i)
            min[i] = 1e9;
    }
    void clear(int position) {
        position += end + 10;
        while (position <= 2 * end + 10) {
            if (min[position] == 1e9)
                return;
            min[position] = 1e9;
            position += lowbit(position);
        }
    }
    void Insert(int position, int val) {
        position += end + 10;
        while (position <= 2 * end + 10) {
            if (min[position] <= val)
                return;
            min[position] = std::min(min[position], val);
            position += lowbit(position);
        }
    }
    int Query(int position) {
        int result = 1e9;
        position += end + 10;

        while (position) {
            result = std::min(result, min[position]);
            position -= lowbit(position);
        }
        return result;
    }

    #undef lowbit(x)
}leftUp, leftDown;

bool cmp(const Position &a, const Position &b) {
    return a.x < b.x;
}

void CDQ(int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) >> 1;
    int I = l, J = mid + 1;
    int beginToNow, endToNow, x, y, id;

    CDQ(l, mid);
    CDQ(mid + 1, r);

    while (I <= mid && J <= r) {
        if (pos[I].opt == 2) {
            I ++;
            continue;
        }
        if (pos[J].opt == 1) {
            J ++;
            continue;
        }
        if (pos[I].x <= pos[J].x) {
            beginToNow = pos[I].y;
            endToNow = end - pos[I].y + 1;
            x = pos[I].x, y = pos[I].y;
            
            leftUp.Insert(endToNow, -x + y);
            leftDown.Insert(beginToNow, -x - y);
            I ++;
        }
        else {
            beginToNow = pos[J].y;
            endToNow = end - pos[J].y + 1;
            x = pos[J].x, y = pos[J].y, id = pos[J].id;

            int temp = leftUp.Query(endToNow);
            if (temp != 1000000000ll) 
                answer[id] = std::min(answer[id], x - y + temp);
            temp = leftDown.Query(beginToNow);
            if (temp != 1000000000ll) 
                answer[id] = std::min(answer[id], x + y + temp);
            J ++;
        }
    }

    while (J <= r) {
        if (pos[J].opt == 1) {
            J ++;
            continue;
        }
        beginToNow = pos[J].y;
        endToNow = end - pos[J].y + 1;
        x = pos[J].x, y = pos[J].y, id = pos[J].id;
            
        int temp = leftUp.Query(endToNow);
        if (temp != 1000000000ll) 
            answer[id] = std::min(answer[id], x - y + temp);
        temp = leftDown.Query(beginToNow);
        if (temp != 1000000000ll) 
            answer[id] = std::min(answer[id], x + y + temp);
        J ++;
    }
    for (int i = l; i <= I; ++ i) {
        leftUp.clear(end - pos[i].y + 1);
        leftDown.clear(pos[i].y);
    }

    std::inplace_merge(pos + l, pos + mid + 1, pos + r + 1, cmp);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> ask[i].x >> ask[i].y;
        ask[i].opt = 1;
    }
    for (int i = N + 1; i <= N + M; ++ i) {
        std::cin >> ask[i].opt;
        std::cin >> ask[i].x >> ask[i].y;
        if (ask[i].opt == 2) {
            ask[i].id = ++ cnt;
            answer[cnt] = 1e9;
        }
    }
    for (int i = 1; i <= N + M; ++ i) {
        pos[i].x = ask[i].x;
        pos[i].y = ask[i].y;
        pos[i].opt = ask[i].opt;
        pos[i].id = ask[i].id;
    }
    CDQ(1, N + M);
    for (int i = 1; i <= N + M; ++ i) {
        pos[i].x = end - ask[i].x;
        pos[i].y = end - ask[i].y;
        pos[i].opt = ask[i].opt;
        pos[i].id = ask[i].id;
    }
    CDQ(1, N + M);
    for (int i = 1; i <= cnt; ++ i) {
        std::cout << answer[i] << '\n';
    }
    return 0;
}
/*
2 3 
1 1 
2 3 
2 1 2 
1 3 3 
2 4 2
*/

[CQOI2011] 动态逆序对

这个还是比较好想的，我们可以处理出来每次删除点 \(i\) 时，前面还剩下的数有多少个数比 \(i\) 位置的数大，后面还剩下的数有多少个比 \(i\) 位置的小。

这样我们就能求出每次删除减少的逆序对了，然后就知道答案了。

Skyline 
#include <bits/stdc++.h>

int N, M;
int answer[51000];

class Ask {
public:
    int tim, pos, val;
}ask[51000], transfer[51000];

class Binary_indexed_Tree {
    #define lowbit(x) (x & (-x))

public: 
    int number[110000];

    void Add(int position, int val) {
        while (position <= N) {
            number[position] += val;
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = 0;

        while (position) {
            result += number[position];
            position -= lowbit(position);
        }
        return result;
    }

    void clear(int position) {
        while (position <= N) {
            number[position] = 0;
            position += lowbit(position);
        }
    }
}tree;

int barrel[110000];

bool cmp(const Ask &a, const Ask &b) {
    return a.pos < b.pos;
}

void CDQ(int l, int r) {
    if (l == r)
        return;
    
    int mid = (l + r) >> 1;
    int I = l, J = mid + 1;
    
    CDQ(l, mid);
    CDQ(mid + 1, r);

    while (I <= mid && J <= r) {
        if (ask[I].pos <= ask[J].pos) {
            tree.Add(ask[I].val, 1);
            I ++;
        }
        else {
            answer[ask[J].tim] -= tree.Query(N) - tree.Query(ask[J].val);
            J ++;
        }
    }
    while (J <= r) {
        answer[ask[J].tim] -= tree.Query(N) - tree.Query(ask[J].val);
        J ++;
    }
    for (int i = l; i <= I - 1; ++ i)
        tree.clear(ask[i].val);
    std::inplace_merge(ask + l, ask + mid + 1, ask + r + 1, cmp);
}

int temp[110000], val[110000];
long long sum = 0;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> val[i];
        barrel[val[i]] = i;
        tree.Add(val[i], 1);
        temp[i] += tree.Query(N) - tree.Query(val[i]);
        sum += temp[i];
    }
    for (int i = 1; i <= N; ++ i)
        tree.clear(i);
    for (int i = N; i >= 1; -- i) {
        temp[i] += tree.Query(val[i]);
        tree.Add(val[i], 1);
    }
    for (int i = 1; i <= N; ++ i)
        tree.clear(i);
    for (int i = 1; i <= M; ++ i) {
        std::cin >> transfer[i].val;
        transfer[i].tim = i;
        transfer[i].pos = barrel[transfer[i].val];
        answer[i] = temp[transfer[i].pos];
        ask[i] = transfer[i];
    }
    CDQ(1, M);
    for (int i = 1; i <= M; ++ i) {
        ask[i] = transfer[i];
        ask[i].pos = N - transfer[i].pos + 1;
        ask[i].val = N - ask[i].val + 1;
    }
    CDQ(1, M);
    for (int i = 1; i <= M; ++ i) {
        sum -= answer[i - 1];
        std::cout << sum << '\n';
    }
    return 0;
}