头像

CYMario




离线:14分钟前


最近来访(59)
用户头像
WanderOvO
用户头像
宇智波-鼬
用户头像
Arthur_5
用户头像
好温柔
用户头像
Avaritia
用户头像
Peter_5
用户头像
Seven1
用户头像
神明的救续
用户头像
Catch-22
用户头像
Asiim0v
用户头像
limie
用户头像
弈剑观星
用户头像
zhoumingxuan
用户头像
Once.
用户头像
亲爱的路人
用户头像
linxudong
用户头像
w完整z_3
用户头像
Magic_Zq
用户头像
往事随风_
用户头像
tangmmmy

活动打卡代码 AcWing 2819. 动态逆序对

CYMario
1天前
using namespace std;
typedef long long ll;
ll rd()
{
    ll k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f > 0 ? k : -k;
}
void wr(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + '0');
}
// 1D Fenwick Tree
template <typename T>
struct BIT
{
    int N;
    vector<T> data;

    BIT() = default;
    BIT(int size) { init(size); }

    void init(int size)
    {
        N = size;
        data.assign(N + 1, 0);
    }

    // data[k] += x
    void add(int k, T x)
    {
        for (++k; k <= N; k += k & -k)
            data[k] += x;
    }

    T sum(int k) const
    {
        if (k <= 0)
            return T();
        T ret = T();
        for (; k; k -= k & -k)
            ret += data[k];
        return ret;
    }

    inline T sum(int l, int r) const { return sum(r) - sum(l); }
};

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {


    using P = pair<S, S>;
    S N, M;
    vector<BIT<T>> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);
        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j) ys[j].push_back(ps[i].second);
            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
            begin(ps), end(ps), make_pair(x, S()),
            [](const P& a, const P& b) { return a.first < b.first; }) -
            begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));
        for (++i; i <= N; i += i & -i) bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();
        for (int a = id(x); a; a -= a & -a) ret += bit[a].sum(id(a, y));
        return ret;
    }

    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
        /*
        T ret = T();
        int a = id(xl), b = id(xr);
        while (a != b) {
          if (a < b) {
            ret += bit[b].sum(id(b, yl), id(b, yr));
            b -= b & -b;
          } else {
            ret -= bit[a].sum(id(a, yl), id(a, yr));
            a -= a & -a;
          }
        }
        return ret;
        */
    }
};
struct Event
{
    bool flag; // 0 : add 1 : query
    int xl, yl, xr, yr;
    ll w;
};
vector<Event> events;
struct point
{
    int x, y;
} a[maxn];
int pos[maxn];
ll inversion;
int main()
{
    FenwickRangeTree<int, int> bit;
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i)
        a[i].x = i, a[i].y = rd(), pos[a[i].y] = i, bit.add_point(a[i].x, a[i].y);

    /*
    sort(tmp, tmp + n);
    int real_n = unique(tmp, tmp + n) - tmp;
    BIT<int> tree(real_n + 1);
    */
    BIT<int> tree(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        //int x = lower_bound(tmp, tmp + real_n, a[i]) - tmp + 1;
        inversion += tree.sum(a[i].y + 1, n + 1); // left close right open
        tree.add(a[i].y, 1);
    }

    bit.build();
    for (int i = 1; i <= n; ++i)
        bit.add(a[i].x, a[i].y, 1);
    while(m--)
    {
        wr(inversion), putchar('\n');
        int y = rd(), x = pos[y];
        //printf("position: (%d, %d)", x, y);
        //printf("minus from before : %d after : %d\n", bit.sum(1, y + 1, x, n + 1), bit.sum(x + 1, 1, n + 1, y));
        inversion -= (bit.sum(1, y + 1, x, n + 1) + bit.sum(x + 1, 1, n + 1, y));
        bit.add(x, y, -1);
    }

}



CYMario
1天前

初始逆序对用树状数组可以算
离线建树结束之后,每一次要减掉的数为——在他前面比他大的个数+在他后面比他小的个数,所以使用二维数据结构实时维护即可,删除之后,再将这个点扔出去就行了。

using namespace std;
typedef long long ll;
ll rd()
{
    ll k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }
    return f > 0 ? k : -k;
}
void wr(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + '0');
}
// 1D Fenwick Tree
template <typename T>
struct BIT
{
    int N;
    vector<T> data;

    BIT() = default;
    BIT(int size) { init(size); }

    void init(int size)
    {
        N = size;
        data.assign(N + 1, 0);
    }

    // data[k] += x
    void add(int k, T x)
    {
        for (++k; k <= N; k += k & -k)
            data[k] += x;
    }

    T sum(int k) const
    {
        if (k <= 0)
            return T();
        T ret = T();
        for (; k; k -= k & -k)
            ret += data[k];
        return ret;
    }

    inline T sum(int l, int r) const { return sum(r) - sum(l); }
};

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {


    using P = pair<S, S>;
    S N, M;
    vector<BIT<T>> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);
        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j) ys[j].push_back(ps[i].second);
            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
            begin(ps), end(ps), make_pair(x, S()),
            [](const P& a, const P& b) { return a.first < b.first; }) -
            begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));
        for (++i; i <= N; i += i & -i) bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();
        for (int a = id(x); a; a -= a & -a) ret += bit[a].sum(id(a, y));
        return ret;
    }

    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
        /*
        T ret = T();
        int a = id(xl), b = id(xr);
        while (a != b) {
          if (a < b) {
            ret += bit[b].sum(id(b, yl), id(b, yr));
            b -= b & -b;
          } else {
            ret -= bit[a].sum(id(a, yl), id(a, yr));
            a -= a & -a;
          }
        }
        return ret;
        */
    }
};
struct Event
{
    bool flag; // 0 : add 1 : query
    int xl, yl, xr, yr;
    ll w;
};
vector<Event> events;
struct point
{
    int x, y;
} a[maxn];
int pos[maxn];
ll inversion;
int main()
{
    FenwickRangeTree<int, int> bit;
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i)
        a[i].x = i, a[i].y = rd(), pos[a[i].y] = i, bit.add_point(a[i].x, a[i].y);

    /*
    sort(tmp, tmp + n);
    int real_n = unique(tmp, tmp + n) - tmp;
    BIT<int> tree(real_n + 1);
    */
    BIT<int> tree(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        //int x = lower_bound(tmp, tmp + real_n, a[i]) - tmp + 1;
        inversion += tree.sum(a[i].y + 1, n + 1); // left close right open
        tree.add(a[i].y, 1);
    }

    bit.build();
    for (int i = 1; i <= n; ++i)
        bit.add(a[i].x, a[i].y, 1);
    while(m--)
    {
        wr(inversion), putchar('\n');
        int y = rd(), x = pos[y];
        //printf("position: (%d, %d)", x, y);
        //printf("minus from before : %d after : %d\n", bit.sum(1, y + 1, x, n + 1), bit.sum(x + 1, 1, n + 1, y));
        inversion -= (bit.sum(1, y + 1, x, n + 1) + bit.sum(x + 1, 1, n + 1, y));
        bit.add(x, y, -1);
    }

}


活动打卡代码 AcWing 2847. 老C的任务

CYMario
1天前
// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {
    struct BIT {
        int N;
        vector<T> data;

        BIT() = default;
        BIT(int size) {
            init(size);
        }

        void init(int size) {
            N = size;
            data.assign(N + 1, 0);
        }

        // data[k] += x
        void add(int k, T x) {
            for (++k; k <= N; k += k & -k)
                data[k] += x;
        }

        T sum(int k) const {
            if (k <= 0)
                return T();

            T ret = T();

            for (; k; k -= k & -k)
                ret += data[k];

            return ret;
        }

        inline T sum(int l, int r) const {
            return sum(r) - sum(l);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BIT> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) {
        ps.push_back(make_pair(x, y));
    }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);

        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j)
                ys[j].push_back(ps[i].second);

            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
                   begin(ps), end(ps), make_pair(x, S()),
        [](const P & a, const P & b) {
            return a.first < b.first;
        }) -
        begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));

        for (++i; i <= N; i += i & -i)
            bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();

        for (int a = id(x); a; a -= a & -a)
            ret += bit[a].sum(id(a, y));

        return ret;
    }

    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
        /*
        T ret = T();
        int a = id(xl), b = id(xr);
        while (a != b) {
          if (a < b) {
            ret += bit[b].sum(id(b, yl), id(b, yr));
            b -= b & -b;
          } else {
            ret -= bit[a].sum(id(a, yl), id(a, yr));
            a -= a & -a;
          }
        }
        return ret;
        */
    }
};
struct Event {
    bool flag; // 0 : add 1 : query
    int xl, yl, xr, yr;
    ll w;
};
vector<Event> events;
int main() {
    //auto f = [](ll a, ll b) {
    //    return a + b;
    //};
    FenwickRangeTree<int, ll> bit;
    int n = rd(), q = rd();
    events.resize(n + q);

    for (int i = 0; i < n; ++i) {
        events[i].flag = 0;
        events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
        bit.add_point(events[i].xl, events[i].yl);
    }

    for (int i = n; i < n + q; ++i) {
        events[i].flag = 1;

        if (!events[i].flag) {
            events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
            bit.add_point(events[i].xl, events[i].yl);
        } else
            events[i].xl = rd(), events[i].yl = rd(), events[i].xr = rd() + 1, events[i].yr = rd() + 1;
    }

    bit.build();

    for (int i = 0; i < n + q; ++i) {
        if (!events[i].flag)
            bit.add(events[i].xl, events[i].yl, events[i].w);
        else
            wr(bit.sum(events[i].xl, events[i].yl, events[i].xr, events[i].yr)), putchar('\n');
    }
}



CYMario
1天前

没啥好说的,有了个比较好的板子之后,简单暴力做加点、建树、查询即可。

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {
    struct BIT {
        int N;
        vector<T> data;

        BIT() = default;
        BIT(int size) {
            init(size);
        }

        void init(int size) {
            N = size;
            data.assign(N + 1, 0);
        }

        // data[k] += x
        void add(int k, T x) {
            for (++k; k <= N; k += k & -k)
                data[k] += x;
        }

        T sum(int k) const {
            if (k <= 0)
                return T();

            T ret = T();

            for (; k; k -= k & -k)
                ret += data[k];

            return ret;
        }

        inline T sum(int l, int r) const {
            return sum(r) - sum(l);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BIT> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) {
        ps.push_back(make_pair(x, y));
    }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);

        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j)
                ys[j].push_back(ps[i].second);

            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
                   begin(ps), end(ps), make_pair(x, S()),
        [](const P & a, const P & b) {
            return a.first < b.first;
        }) -
        begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));

        for (++i; i <= N; i += i & -i)
            bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();

        for (int a = id(x); a; a -= a & -a)
            ret += bit[a].sum(id(a, y));

        return ret;
    }

    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
        /*
        T ret = T();
        int a = id(xl), b = id(xr);
        while (a != b) {
          if (a < b) {
            ret += bit[b].sum(id(b, yl), id(b, yr));
            b -= b & -b;
          } else {
            ret -= bit[a].sum(id(a, yl), id(a, yr));
            a -= a & -a;
          }
        }
        return ret;
        */
    }
};
struct Event {
    bool flag; // 0 : add 1 : query
    int xl, yl, xr, yr;
    ll w;
};
vector<Event> events;
int main() {
    //auto f = [](ll a, ll b) {
    //    return a + b;
    //};
    FenwickRangeTree<int, ll> bit;
    int n = rd(), q = rd();
    events.resize(n + q);

    for (int i = 0; i < n; ++i) {
        events[i].flag = 0;
        events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
        bit.add_point(events[i].xl, events[i].yl);
    }

    for (int i = n; i < n + q; ++i) {
        events[i].flag = 1;

        if (!events[i].flag) {
            events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
            bit.add_point(events[i].xl, events[i].yl);
        } else
            events[i].xl = rd(), events[i].yl = rd(), events[i].xr = rd() + 1, events[i].yr = rd() + 1;
    }

    bit.build();

    for (int i = 0; i < n + q; ++i) {
        if (!events[i].flag)
            bit.add(events[i].xl, events[i].yl, events[i].w);
        else
            wr(bit.sum(events[i].xl, events[i].yl, events[i].xr, events[i].yr)), putchar('\n');
    }
}



CYMario
1天前
#include <stdio.h>
#include <string.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define full 114514
#define single 1
#define maxn 1010
#define maxv 200010
#define maxq 200010

char eof_flag;
char rd(int *s)
{
    if (eof_flag)
        return 0;

    int k = 0, f = 1;
    char c = getchar();

    while (c != '-' && (c < '0' || c > '9'))
    {
        if (c == EOF)
        {
            eof_flag = 1;
            return 0;
        }

        c = getchar();
    }

    f = (c == '-') ? -1 : 1;
    k = (c == '-') ? 0 : (c ^ 48);
    c = getchar();

    while (c >= '0' && c <= '9')
        k = (k << 1) + (k << 3) + (c ^ 48), c = getchar();

    if (c == EOF)
        eof_flag = 1;

    (*s) = f > 0 ? k : -k;
    return 1;
}

void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + 48);
}

int n, V; // V : size of pack
int cost, value, cnt;
int dp[maxv];
int deq[maxq];  // deque of index
int deqv[maxq]; // deque of value

void buildDP_01Pack(int cost, int value)
{
    for (int v = V; v >= cost; --v)
        dp[v] = max(dp[v], dp[v - cost] + value);
}

void buildDP_FullPack(int cost, int value)
{
    for (int v = cost; v <= V; ++v)
        dp[v] = max(dp[v], dp[v - cost] + value);
}

void buildDP_MultiPack(int cost, int value, int count)
{
    for (int a = 0; a < cost; ++a)
    {
        int s = 0, t = 0; // init deque
        for (int j = 0; j * cost + a <= V; j++)
        {
            int val = dp[j * cost + a] - j * value;
            while (s < t && deqv[t - 1] <= val)
                t--;                     // pop_back
            deq[t] = j, deqv[t++] = val; // push_back
            dp[j * cost + a] = deqv[s] + j * value;
            if (deq[s] == j - count)
                ++s; // pop_front
        }
    }
}

void buildDP_CombinedPack(int cost, int value, int count)
{
    if (count == single)
        buildDP_01Pack(cost, value);
    else if (count == full)
        buildDP_FullPack(cost, value);
    else
        buildDP_MultiPack(cost, value, count);
}

int main()
{
    while (rd(&n) && rd(&V))
    {
        memset(dp, 0, (V + 1) * sizeof(dp[0]));
        while (n--)
        {
            rd(&cost), rd(&value), rd(&cnt);
            buildDP_CombinedPack(cost, value, cnt);
        }
        wr(dp[V]), putchar('\n');
    }
}


活动打卡代码 AcWing 1310. 数三角形

CYMario
1天前
#include <stdio.h>
typedef long long ll;
ll gcd(ll a, ll b) {
    //特判
    if (a < 0)
        a = -a;

    if (b < 0)
        b = -b;

    if (a == 0)
        return b;

    if (b == 0)
        return a;

    int r = 0;//a和b的2^r形式的公因子

    while (!((a & 1) || (b & 1))) {
        //a和b都是偶数的时候
        a >>= 1;
        b >>= 1;
        r++;
    }

    ll ret = 0;

    while (1) {//首次到这里时,至少一奇
        while (!(a & 1))
            a >>= 1;//剔除a中的因子2

        while (!(b & 1))
            b >>= 1;//剔除b中的因子2

        if (a > b)
            a = a - b;
        else
            b = b - a;//简化为gcd(max(a,b)-min(a,b),min(a,b)) 可以证明这步的正确性

        if (0 == a) {
            ret = b << r;    //最后这步倒是和欧几里得做法类似
            break;
        }

        if (0 == b) {
            ret = a << r;
            break;
        }
    }

    return ret;
}
ll solve(ll n, ll m) {
    ll ret = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ret += (n - i + 1) * (m - j + 1) * (6 * i * j - 2 * gcd(i, j));

    return ret;
}
ll n, m;
int main() {
    scanf("%lld%lld", &n, &m);
    printf("%lld\n", solve(n, m));
}


活动打卡代码 AcWing 255. 第K小数

CYMario
1天前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010
using namespace std;
typedef long long ll;
inline void write(int x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
    putchar(x % 10 + 48);
}
inline int read() {
    int k = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + c - 48;
        c = getchar();
    }
    return k * f;
}
int n, m;
int a[maxn], b[maxn];//原有数组和离散化排序后的数组
int root[maxn];
int l, r, k;
struct P_SegmentTree_KthElement {
    struct Node {
        int lchild, rchild;
        int value_sum;
    }nodes[maxn * 30];
    int _size;
    P_SegmentTree_KthElement() {
        _size = 0;
        memset(nodes, 0, sizeof(nodes));
    }
    inline void build(int& root, int l, int r) {
        root = ++_size;
        if (l == r) { nodes[root].value_sum = 0; return; }
        int m = (l + r) >> 1;
        build(nodes[root].lchild, l, m);
        build(nodes[root].rchild, m + 1, r);
    }
    //对应的修改点
    inline int update(int preVer, int l, int r, int x) {
        int rootVer = ++_size;
        nodes[rootVer].lchild = nodes[preVer].lchild;
        nodes[rootVer].rchild = nodes[preVer].rchild;
        nodes[rootVer].value_sum = nodes[preVer].value_sum + 1;
        int m = (l + r) >> 1;
        if (l < r) {
            if (x <= m)nodes[rootVer].lchild = update(nodes[preVer].lchild, l, m, x);
            else nodes[rootVer].rchild = update(nodes[preVer].rchild, m + 1, r, x);
        }
        return rootVer;
    }
    inline int query(int ver1, int ver2, int l, int r, int k) {
        if (l >= r)return l;
        int x = nodes[nodes[ver2].lchild].value_sum - nodes[nodes[ver1].lchild].value_sum;
        int m = (l + r) >> 1;
        if (x >= k)return query(nodes[ver1].lchild, nodes[ver2].lchild, l, m, k);
        else return query(nodes[ver1].rchild, nodes[ver2].rchild, m + 1, r, k - x);
    }
};
P_SegmentTree_KthElement tree;
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int realn = unique(b + 1, b + n + 1) - b - 1;
    tree.build(root[0], 1, realn);
    for (int i = 1; i <= n; ++i) {
        int t = lower_bound(b + 1, b + 1 + realn, a[i]) - b;
        root[i] = tree.update(root[i - 1], 1, realn, t);
        //逐一元素找到离散数组中的对应位置,按这个位置来建树
    }
    while (m--) {
        l = read(), r = read(), k = read();
        write(b[tree.query(root[l - 1], root[r], 1, realn, k)]);
        putchar('\n');
    }
}



CYMario
1天前

分块做法

树套树空间被卡了,日后再更

#include <stdio.h>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
const int INF1 = 100000000, INF2 = 2147483647;

int rd() {
    int k = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }

    return f > 0 ? k : -k;
}
void wr(int x) {
    if (x < 0)
        putchar('-'), x = -x;

    if (x > 9)
        wr(x / 10);

    putchar(x % 10 + '0');
}

// Data Structure from nzy

namespace Block {
const int N = 50005;
const int block_len = 1000;
int d[N], sd[N], pos[N], l[(N / block_len) + 5], r[(N / block_len) + 5], n, m;

void init(int _n) {
    n = _n;

    for (int i = 1; i <= n; ++i)
        sd[i] = d[i] = rd();

    m = (n + block_len - 1) / block_len;

    for (int i = 1; i <= m; i++) {
        l[i] = block_len * (i - 1) + 1;
        r[i] = block_len * i;
    }

    r[m] = n;

    for (int i = 1; i <= m; i++) {
        for (int j = l[i]; j <= r[i]; j++)
            pos[j] = i;

        sort(sd + l[i], sd + r[i] + 1);
    }
}

void modify(int p, int val) {
    for (int i = l[pos[p]]; i <= r[pos[p]]; i++) {
        if (sd[i] == d[p]) {
            sd[i] = val;
            break;
        }
    }

    sort(sd + l[pos[p]], sd + r[pos[p]] + 1);
    d[p] = val;
}
int get_rank_by_num(int left, int right, int val) {
    int cnt = 0;

    for (int i = pos[left]; i <= pos[right]; i++) {
        if (left <= l[i] && r[i] <= right)
            cnt += lower_bound(sd + l[i], sd + r[i] + 1, val) - (sd + l[i]);
        else {
            for (int j = max(l[i], left); j <= min(r[i], right); j++)
                if (d[j] < val)
                    cnt++;
        }
    }

    return cnt + 1;
}

int get_prev(int left, int right, int c) {
    int res = -INF2;

    for (int i = pos[left]; i <= pos[right]; i++) {
        if (left <= l[i] && r[i] <= right) {
            int p = lower_bound(sd + l[i], sd + r[i] + 1, c) - sd - 1;

            if (left <= p && p <= right && sd[p] < c)
                res = max(res, sd[p]);
        } else {
            for (int j = max(l[i], left); j <= min(r[i], right); j++)
                if (d[j] < c)
                    res = max(res, d[j]);
        }
    }

    return res;
}
int get_next(int left, int right, int c) {
    int res = INF2;

    for (int i = pos[left]; i <= pos[right]; i++) {
        if (left <= l[i] && r[i] <= right) {
            int p = upper_bound(sd + l[i], sd + r[i] + 1, c) - sd;

            if (left <= p && p <= right && sd[p] > c)
                res = min(res, sd[p]);
        } else {
            for (int j = max(l[i], left); j <= min(r[i], right); j++)
                if (d[j] > c)
                    res = min(res, d[j]);
        }
    }

    return res;
}

int get_num_by_rank(int left, int right, int rk) {
    int lo = 0, hi = INF1;

    while (lo < hi) {
        int mid = (lo + hi) >> 1;

        if (get_rank_by_num(left, right, mid) <= rk)
            lo = mid + 1;
        else
            hi = mid;
    }

    return get_prev(left, right, lo);
}
}
int n, m;
int op, l, r, pos, val, rk;
int main() {
    n = rd(), m = rd();
    Block::init(n);

    while (m--) {
        op = rd();

        switch (op) {
        /*
        case 1:
            l = rd(), r = rd(), val = rd();
            wr(Block::get_rank_by_num(l, r, val)), putchar('\n');
            break;

        case 2:
            l = rd(), r = rd(), rk = rd();
            wr(Block::get_num_by_rank(l, r, rk)), putchar('\n');
            break;
        */
        case 1:
            pos = rd(), val = rd();
            Block::modify(pos, val);
            break;

        case 2:
            l = rd(), r = rd(), val = rd();
            wr(Block::get_prev(l, r, val)), putchar('\n');
            break;
        /*
        case 5:
            l = rd(), r = rd(), val = rd();
            wr(Block::get_next(l, r, val)), putchar('\n');
            break;
        */
        default:
            break;
        }
    }
}


活动打卡代码 AcWing 2815. 三维偏序

CYMario
2天前

1. cdq做法

//一维排序二维cdq三维bittree
#include<cstdio>
#include<ctime>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 200005;
struct ori
{
    int a, b, c;
    ori(int x = 0, int y = 0, int z = 0)
    {
        a = x;
        b = y;
        c = z;
    }
    bool operator < (const ori& o) const
    {
        if (a==o.a)
        {
            if (b==o.b)
            {
                return c<o.c;
            }
            return b<o.b;
        }
        return a<o.a;
    }
    bool operator == (const ori& o) const
    {
        return a==o.a&&b==o.b&&c==o.c;
    }
}ele[MAXN];
int n, m, k;
struct node
{
    int a, b, c, sz, ans;
    node(int u = 0, int v = 0, int w = 0, int x = 0, int y = 0)
    {
        a = u, b = v, c = w, sz = x, ans = y;
    }
}o[MAXN], e[MAXN];
int p, q, tot, ans[MAXN];
int bit[MAXN];
void Add(int x, int val)
{
    while (x <= k)
    {
        bit[x] += val;
        x += x & -x;
    }
}
int Query(int x)
{
    int ret = 0;
    while (x)
    {
        ret += bit[x];
        x -= x & -x;
    }
    return ret;
}
void cdq(int L, int R)
{
    if (L >= R) return;
    int Mid = L + R >> 1;

    cdq(L, Mid);
    cdq(Mid + 1, R);

    p = L, q = Mid + 1, tot = L;
    while (p <= Mid && q <= R)
    {
        if (o[p].b <= o[q].b)
        {
            Add(o[p].c, o[p].sz);
            e[tot++] = o[p++];
        }
        else
        {
            o[q].ans += Query(o[q].c);
            e[tot++] = o[q++];
        }
    }
    while (q <= R)
    {
        o[q].ans += Query(o[q].c);
        e[tot++] = o[q++];
    }
    for (int i = L; i < p; ++i) Add(o[i].c, -o[i].sz);
    while (p <= Mid) e[tot++] = o[p++];
    for (int i = L; i <= R; ++i) o[i] = e[i];
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int aa, bb, cc, i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &aa, &bb, &cc);
        ele[i] = ori(aa, bb, cc);
    }
    sort(ele+1, ele+1+n);
    for (int i = 1; i <= n; ++i)
    {
        if (ele[i] == ele[i-1] && i > 1)
        {
            ++o[m].sz;
            continue;
        }
        o[++m] = node(ele[i].a, ele[i].b, ele[i].c, 1);
    }
    cdq(1, m);
    for (int i = 1; i <= m; ++i) ans[o[i].ans+o[i].sz-1] += o[i].sz;
    for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
    return 0;
}

2.2D动态树状数组做法

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <vector>
using namespace std;
int rd() {
    int k = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar();
    }

    return f > 0 ? k : -k;
}
void wr(int x) {
    if (x < 0)
        putchar('-'), x = -x;

    if (x > 9)
        wr(x / 10);

    putchar(x % 10 + '0');
}
// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type

template <typename S, typename T>
struct FenwickRangeTree {
    struct BIT {
        int N;
        vector<T> data;

        BIT() = default;
        BIT(int size) {
            init(size);
        }

        void init(int size) {
            N = size;
            data.assign(N + 1, 0);
        }

        // data[k] += x
        void add(int k, T x) {
            for (++k; k <= N; k += k & -k)
                data[k] += x;
        }

        T sum(int k) const {
            if (k <= 0)
                return T();

            T ret = T();

            for (; k; k -= k & -k)
                ret += data[k];

            return ret;
        }

        inline T sum(int l, int r) const {
            return sum(r) - sum(l);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BIT> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) {
        ps.push_back(make_pair(x, y));
    }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);

        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j)
                ys[j].push_back(ps[i].second);

            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
                   begin(ps), end(ps), make_pair(x, S()),
        [](const P & a, const P & b) {
            return a.first < b.first;
        }) -
        begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));

        for (++i; i <= N; i += i & -i)
            bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();

        for (int a = id(x); a; a -= a & -a)
            ret += bit[a].sum(id(a, y));

        return ret;
    }
    // x : [xl, xr)  y : [yl, yr)
    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
    }
};
struct item {
    int a, b, c;
    bool operator == (const item &o) const {
        return a == o.a && b == o.b && c == o.c;
    }
    bool operator <(const item &o) const {
        if (a != o.a)
            return a < o.a;
        else if (b != o.b)
            return b < o.b;
        else
            return c < o.c;
    }
} a[100010];
FenwickRangeTree<int, int> bit;
int ans[100010], cnt[100010];//cnt 记录和当前自己属性值完全一样的个数
int main() {
    int n = rd(), k = rd();

    for (int i = 0; i < n; ++i)
        a[i].a = rd(), a[i].b = rd(), a[i].c = rd();

    sort(a, a + n);

    //bit.add_point(a[0].b, a[0].c);
    for (int i = 0; i < n; ++i) {
        if (i != (n - 1) && a[i] == a[i + 1])
            continue;
        else
            bit.add_point(a[i].b, a[i].c);
    }

    bit.build();

    for (int i = 0; i < n; ++i) {
        if (i != (n - 1) && a[i] == a[i + 1])
            cnt[i + 1] = cnt[i] + 1;
        else {
            int tmp = bit.sum(0, 0, a[i].b + 1, a[i].c + 1) + cnt[i];
            ans[tmp] += cnt[i] + 1;
            bit.add(a[i].b, a[i].c, cnt[i] + 1);
        }
    }

    for (int i = 0; i < n; ++i)
        wr(ans[i]), putchar('\n');
}



CYMario
2天前

二维动态树状数组做法(性质–半离线预处理)

三维偏序的问题, 为什么都是cdq分治的题解,没有2D数据结构查询的做法呢? 作为一个没脑子不会推cdq的人,感觉还是应该补充一个这种更易懂的做法。

首先我们可以想到,对于我们常见的kd-树,单次查询为 $O(\sqrt n)$,在本题只有1s的时限内,必然是跑不动的。所以我们需要回到二维更常用的树套树上。

思路介绍–如何使用在线的2D查询解决本题

在介绍数据结构的优化之前,我们先说一下这种题拿树套树等二维数据结构要怎么做吧。

我们要找到所有满足条件的 $a_j \le a_i, b_j\le b_i, c_j \le c_i$,那么第一个维度 $a$ 我们可以直接从小到大进行排序。

接下来我们按照 $a$ 维度从小到大进行遍历,每次在二维空间中,查询与自己不完全相同的,满足 $(b_j\le b_i, c_j\le c_i)$ 的个数 $g(i)$(由于 $a$ 维度已经从小到大排序,所以必然是成立的),与自己三维完全相同的个数为 $h(i)$ ,那么 $f(i) = g(i) + h(i)$ ,此时答案为 $f(i)$ 的个数要多 $h(i) + 1$ 个。

这样我们便可以得到所有的答案。排序为 $O(n\log n)$, 查询总时间为 $O(n\log^2 n)$。

数据结构介绍–如何选取合适的数据结构

其中插入、查询全部操作强制在线的操作可以见我之前的一篇题解,但是这种强制在线,会导致空间与时间的常数巨大,虽然量纲没错,但是绝对过不去。

所以我们可以采用更折中的一种做法,即在事先知道哪些位置需要插入点之后,对所有点进行离散化,在统一建好的树上,再逐一加入点权,以及进行查询。这样可以大量的减少时间和空间的开销。

再考虑到本题的点权之间是进行加法求和,树状数组可以表示前缀加和,且拥有比线段树更优的常数,所以我们可以考虑采用 二维动态树状数组,先模拟一次运算过程(不进行实际运算)加点,所有点加入之后统一建树,再遍历一次进行实际的计算,加入点权,二维区间查询即可。

实际上这种做法在优化开满之后,时间与空间都只是略逊于cdq做法而已,就算是极致的毒瘤也没法为了只允许cdq分治过而不让该做法通过。

通过代码

去掉了头文件和快读快写,关键是理解二维数据结构的应用方法,以及本题的算法流程,希望各位可以自己实现一遍~

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type

template <typename S, typename T>
struct FenwickRangeTree {
    struct BIT {
        int N;
        vector<T> data;

        BIT() = default;
        BIT(int size) {
            init(size);
        }

        void init(int size) {
            N = size;
            data.assign(N + 1, 0);
        }

        // data[k] += x
        void add(int k, T x) {
            for (++k; k <= N; k += k & -k)
                data[k] += x;
        }

        T sum(int k) const {
            if (k <= 0)
                return T();

            T ret = T();

            for (; k; k -= k & -k)
                ret += data[k];

            return ret;
        }

        inline T sum(int l, int r) const {
            return sum(r) - sum(l);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BIT> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) {
        ps.push_back(make_pair(x, y));
    }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);

        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j)
                ys[j].push_back(ps[i].second);

            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
                   begin(ps), end(ps), make_pair(x, S()),
        [](const P & a, const P & b) {
            return a.first < b.first;
        }) -
        begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));

        for (++i; i <= N; i += i & -i)
            bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();

        for (int a = id(x); a; a -= a & -a)
            ret += bit[a].sum(id(a, y));

        return ret;
    }
    // x : [xl, xr)  y : [yl, yr)
    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
    }
};
struct item {
    int a, b, c;
    bool operator == (const item &o) const {
        return a == o.a && b == o.b && c == o.c;
    }
    bool operator <(const item &o) const {
        if (a != o.a)
            return a < o.a;
        else if (b != o.b)
            return b < o.b;
        else
            return c < o.c;
    }
} a[100010];
FenwickRangeTree<int, int> bit;
int ans[100010], cnt[100010];// cnt 记录和当前自己属性值完全一样的个数(除自身之外)
int main() {
    int n = rd(), k = rd();

    for (int i = 0; i < n; ++i)
        a[i].a = rd(), a[i].b = rd(), a[i].c = rd();

    sort(a, a + n);// 按照 a 维度 从小到大排序

    //第一遍过程 : 仅是模拟验算,只把该加的点加进去
    for (int i = 0; i < n; ++i) {
        if (i != (n - 1) && a[i] == a[i + 1])
            continue;
        else
            bit.add_point(a[i].b, a[i].c);
    }
    //得到所有点之后,二维动态树状数组统一建树,这也就是所谓的半离线方法(预处理离线,而非全程离线)
    bit.build();

    for (int i = 0; i < n; ++i) {
        // 如果和后一个相同,则该点不做计算,并将自己的重复个数传递给后面
        if (i != (n - 1) && a[i] == a[i + 1])
            cnt[i + 1] = cnt[i] + 1;
        else {
            // 查询与自己不一样且满足条件的 g(i) 与和自己完全一样的 h(i) 对应的f(i)=g(i)+h(i)
            int tmp = bit.sum(0, 0, a[i].b + 1, a[i].c + 1) + cnt[i];
            // 对答案 f(i) 个数的贡献为 h(i) + 1
            ans[tmp] += cnt[i] + 1;
            // 这部分计算完毕之后,所有 h(i)+1 个重合的点加进树中,将 h(i)+1视为对该点的点权贡献
            bit.add(a[i].b, a[i].c, cnt[i] + 1);
        }
    }

    for (int i = 0; i < n; ++i)
        wr(ans[i]), putchar('\n');
}