Yukino With Subinterval (The 2019 Asia Nanchang )

2019ICPC南昌网络赛I题

树状数组套主席树

题目链接: Yukino With Subinterval

自闭过程

就是主席树查询区间$[L,R]$并且值域在$[x,y]$直接内点的个数嘛? 修改的话,修改一个点会对这个点后面所有点造成影响,树状数组更新即可,时间复杂度$O(nlogn+mlog^{2}_{n})$

树套树内存真大啊!数组千万不能开小了。

#include<bits/stdc++.h>
using namespace std;
#define lowbit( x ) (x&(-x))
typedef long long ll;
const int N = 2e5 + 10;
const int M = 200000;
int a[N], tot, n, m, numx, numy;
struct tree {
    int lc, rc, cnt;
} T[N * 200];
int root[N], S[N], ux[50], uy[50];
void build(int &cur, int l, int r)
{
    cur = ++tot;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(T[cur].lc, l, mid);
    build(T[cur].rc, mid + 1, r);
}
void update(int &cur, int pre, int l, int r, int pos, int val) {
    cur = ++tot;
    T[cur] = T[pre];
    T[cur].cnt += val;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(T[cur].lc, T[pre].lc, l, mid, pos, val);
    else update(T[cur].rc, T[pre].rc, mid + 1, r, pos, val);
}
void UP(int &cur, int l, int r, int pos, int val)
{
    if (!cur) cur = ++tot;
    T[cur].cnt += val;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) UP(T[cur].lc, l, mid, pos, val);
    else UP(T[cur].rc, mid + 1, r, pos, val);
}
void add(int pos, int val) {
    int v = a[pos];
    for (; pos <= n; pos += lowbit(pos))
        UP(S[pos], 1, n, v, val);
}
int query(int l, int r, int L, int R, int x, int y) {
    if (x <= l && r <= y)
    {
        int ans = T[R].cnt - T[L].cnt;
        for (int i = 0; i < numy; i++) ans += T[uy[i]].cnt;
        for (int i = 0; i < numx; i++) ans -= T[ux[i]].cnt;
        return ans;
    }
    int  Ux[50], Uy[50];
    for (int i = 0; i < numy; i++) Uy[i] = uy[i];
    for (int i = 0; i < numx; i++) Ux[i] = ux[i];
    int mid = (l + r) >> 1;
    int sum = 0;
    if (x <= mid)
    {
        for (int i = 0; i < numy; i++) uy[i] = T[Uy[i]].lc;
        for (int i = 0; i < numx; i++) ux[i] = T[Ux[i]].lc;
        sum = query(l, mid, T[L].lc, T[R].lc, x, y);
    }
    if (y > mid)
    {
        for (int i = 0; i < numy; i++) uy[i] = T[Uy[i]].rc;
        for (int i = 0; i < numx; i++) ux[i] = T[Ux[i]].rc;
        sum += query(mid + 1, r, T[L].rc, T[R].rc, x, y);
    }
    return sum;
}

int main() {
    int op, x, y, L, R, ans,x1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[i - 1]) update(root[i], root[i - 1], 1, n, a[i], 1);
        else root[i] = root[i - 1];
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &op);
        if (op == 2) {
            scanf("%d%d%d%d", &L, &R, &x, &y);
            numx = numy = 0;
            for (int j = R; j > 0; j -= lowbit(j)) if(S[j]) uy[numy++] = S[j];
            for (int j = L - 1; j > 0; j -= lowbit(j)) if(S[j]) ux[numx++] = S[j];
            ans = query(1, n, root[L - 1], root[R], x, y);
            if (a[L] == a[L - 1] && a[L] >= x&&a[L] <= y) ans++;
            printf("%d\n", ans);
        }
        else if (op == 1) {
            scanf("%d%d",  &x, &y);
            if (a[x] == y) continue;
            x1 = 0;
            if (a[x] != a[x - 1]) add(x, -1);
            if (x < n&&a[x + 1] != a[x]) x1--;
            a[x] = y;
            if (a[x] != a[x - 1]) add(x, 1);
            if (x < n&&a[x + 1] != a[x]) x1++;
            if (x1) add(x + 1, x1);
        }
    }
    return 0;
}

刚开始写得代码,比上面那个容易理解一些

#include<bits/stdc++.h>

using namespace std;
#define lowbit( x ) (x&(-x))
typedef long long ll;
const int N = 2e5 + 10;
const int M = 200000;
int a[N], tot, n, m, q, numx, numy;
struct tree {
    int lc, rc, cnt;
} T[N * 200];
int root[N], S[N];
//int ux[50], uy[50];
void build(int &cur, int l, int r)
{
    cur = ++tot;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(T[cur].lc, l, mid);
    build(T[cur].rc, mid + 1, r);
}
void update(int &cur, int pre, int l, int r, int pos, int val) {
    cur = ++tot;
    T[cur] = T[pre];
    T[cur].cnt += val;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(T[cur].lc, T[pre].lc, l, mid, pos, val);
    else update(T[cur].rc, T[pre].rc, mid + 1, r, pos, val);
}
void UP(int &cur, int l, int r, int pos, int val)
{
    if (!cur) cur = ++tot;
    T[cur].cnt += val;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) UP(T[cur].lc, l, mid, pos, val);
    else UP(T[cur].rc,  mid + 1, r, pos, val);

}
void add(int pos, int val) {
    int v = a[pos];
    for (; pos <= n; pos += lowbit(pos))
        UP(S[pos], 1, n, v, val);
}

int query(int l, int r, int rt, int x, int y) {
    if (!rt) return 0;
    if (x <= l && r <= y) return T[rt].cnt;
    int mid = (l + r) >> 1;
    int sum = 0;
    if (x <= mid) sum = query(l, mid, T[rt].lc, x, y);
    if (y > mid) sum += query(mid + 1, r, T[rt].rc, x, y);
    return sum;
}

void read(int &x) {
    x = 0;
    char c = getchar();
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

int main() {
    int op, x, y, L, R, ans;
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    //build(root[0], 1, n);
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[i - 1]) update(root[i], root[i - 1], 1, n, a[i], 1);
        else root[i] = root[i - 1];
    }
    for (int i = 1; i <= m; i++) {
        read(op);
        if (op == 2) {
            read(L), read(R), read(x), read(y);
            //scanf("%d%d%d%d", &L, &R, &x, &y);
            ans = query(1, n, root[R], x, y) - query(1, n, root[L - 1], x, y);
            for (int j = R; j > 0; j -= lowbit(j)) ans += query(1, n, S[j], x, y);
            for (int j = L - 1; j > 0; j -= lowbit(j)) ans -= query(1, n, S[j], x, y);
            if (a[L] == a[L - 1] && a[L] >= x&&a[L] <= y) ans++;
            printf("%d\n", ans);
        }
        else if (op == 1) {
            read(x), read(y);
            if (a[x] == y) continue;
            if (a[x] != a[x - 1]) add(x, -1);
            if (x < n&&a[x + 1] != a[x]) add(x + 1, -1);
            a[x] = y;
            if (a[x] != a[x - 1]) add(x, 1);
            if (x < n&&a[x + 1] != a[x]) add(x + 1, 1);
        }
    }
    return 0;
}

Last modification:October 31st, 2019 at 04:11 pm
如果觉得我的文章对你有用,请随意赞赏

2 comments

  1. 云中君 Google Chrome 61.0.3163.100 Windows 10

    你们还有队友呢啊!团队赛被!

    1. tomaito Google Chrome 76.0.3809.132 Windows 10
      @云中君

      对的,3个人一个队伍

Leave a Comment