2021美团杯A.数据结构

本文主要是介绍2021美团杯A.数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

补题：2021美团杯A.数据结构
比赛一开始看到不同数个数，张口主席树求区间不同数个数瞬间带歪队友，自己也在错误的道路上越走越远。
在中后期重新阅读题面发现每次询问的是全局不同数的个数，想到了最多只有\(n+1\)个数，对于每一次询问，我去计算有多少数会被删除，有多少数会被增加。无奈题刷少了，没想到统计不出现数的个数。
思路
彩蛋：学习了邓老师的代码，结果在看他代码的时候发现了一个手误情况，直接手造hack数据给了jls，成为了热心网友hack了邓老师，邓老师AK IOI，那么我hack邓老师，四舍五入就是我hack IOI（狗头保命）。然后发现我队也抽到了阳光普照奖2333333。
对于一个数\(x\)，考虑其最左出现的位置\(l_x\),最右出现的位置\(r_x\)，那么首先就确定每次询问的\(l,r\)满足\(l\leq l_x, r_x \leq r\)。然后考虑\(x-1\)的出现位置，若在\(l_x \leq pos \leq r_x\)中出现，那么\(x\)永远存在，其它情况就是会出现\(pos_t \leq l_x \leq r_x \leq pos_{t+1}\)。然后到这一步在赛中就不会维护了。
根据上面的这个不等式，我们发现当\(pos_t \leq l \leq l_x,r_x \leq r \leq pos_{t+1}\)时这个值会减去，那么只要用类似差分的思想，在\(r_x\)上设置\([pos_t+1,l_x]\)这一段\(+1\)，在\(pos_{t+1}\)上对\([pos_t+1,l_x]\)这一段\(-1\)。这样就对右边的这一块进行了维护。
在输入完查询之后，我们从第一个位置出发，对于当前需要更新的位置\(i\)，我们可以知道对于某个数我们在\([l,r]\)之间对其有一个更新，那么就把左边的这个\([l,r]\)更新到树状数组中，表示当我的右区间下标为\(i\)时，此时左区间\([l,r]\)有一个数会删除/增加。然后对于每一个询问查询一下当前右区间为\(i\)时，有多少个值在左区间不出现。
然后对于原始数组没有出现过的数字，那么直接把\(x-1\)的每一个不相交的区间更新进去即可。
代码
代码中注释掉的是邓老师的写法。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
#define x first
#define y second
const int N = 1e6 + 10, M = 13331;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
#define gcd __gcd

vector<int> v[N];
int l[N], r[N];
struct Node {
    int l, r, v;
};
vector<Node> vec[N];
int tr[N], res[N];
int n, m;
vector<PII> que[N];
int a[N];

int lowbit(int x) {
    return x & -x;
}

void add(int p, int x) {
    for(int i = p; i <= n; i += lowbit(i)) {
        tr[i] += x;
    }
}

int query(int x) {
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

void update(int l1, int r1, int l2, int r2, int val) {
    if(l1 > r1 || l2 > r2) return;
    // printf("val = %d %d %d %d %d\n", val, l1, r1, l2, r2);
    vec[l2].push_back({l1, r1, 1});
    vec[r2 + 1].push_back({l1, r1, -1});
}

void solve() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n + 1; i++) {
        v[i].push_back(0);
        l[i] = n + 1;
        r[i] = 0;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        l[a[i]] = min(l[a[i]], i);
        r[a[i]] = max(r[a[i]], i);
        v[a[i]].push_back(i);
    }
    for(int i = 0; i <= n + 1; i++) {
        v[i].push_back(n + 1);
    }

    for(int i = 1; i <= n + 1; i++) {
        // 不存在
        if(l[i] == n + 1) {
            for(int j = 0; j < v[i - 1].size() - 1; j++) {
                int l = v[i - 1][j] + 1, r = v[i - 1][j + 1] - 1;
                update(l, r, l, r, i);
            }
        }
        else {
            int L = 0, R = n + 1;
            bool flag = false;
            for(auto x : v[i - 1]) {
                if(l[i] <= x && x <= r[i]) {
                    flag = true;
                    break;
                }
                if(x < l[i]) L = max(x, L);
                if(x > r[i]) R = min(x, R);
            }
            if(flag) continue;
            update(L + 1, l[i], r[i], R - 1, i);
        }
    }

    // for(int i = 1; i <= n + 1; i++) {
    //     int l = n, r = 1;
    //     for(auto x : v[i]) {
    //         l = min(l, x);
    //         r = max(r, x);
    //     }
    //     vector<int> tmp; tmp.push_back(0);
    //     for(auto x : v[i - 1]) tmp.push_back(x);
    //     tmp.push_back(n + 1);
    //     for(int j = 0; j < tmp.size() - 1; j++) {
    //         int L = tmp[j], R = tmp[j + 1];
    //         // printf("i = %d, l = %d, r = %d, L = %d, R = %d\n", i, l, r, L, R);
    //         // printf("i = %d, %d %d %d %d\n", L + 1, min(l, R - 1), max(R, L + 1), R - 1);
    //         update(L + 1, min(l, R - 1), max(r, L + 1), R - 1, i);
    //     }
    // }
    for(int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        que[r].push_back({l, i});
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < vec[i].size(); j++) {
            int l = vec[i][j].l, r = vec[i][j].r, x = vec[i][j].v;
            // printf("l = %d, r = %d\n", l, r);
            add(l, x);
            add(r + 1, -x);
        }
        for(int j = 0; j < que[i].size(); j++) {
            int x = que[i][j].x, id = que[i][j].y;
            res[id] = n + 1 - query(x);
        }
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", res[i]);
    }
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    // int t; cin >> t; while(t--)
    solve();
    return 0;
}

这篇关于2021美团杯A.数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！