头像

lzyz000




离线:1小时前


最近来访(35)
用户头像
抒怀
用户头像
冷冷月光
用户头像
艺人
用户头像
_lcy_
用户头像
2Yan2
用户头像
心里没有一点AC数
用户头像
Ethereum
用户头像
Lwind
用户头像
派大星想写代码
用户头像
Chainsure
用户头像
Phil..
用户头像
lzyz111
用户头像
LeoRiver
用户头像
PrinceS
用户头像
lzyz222
用户头像
pluto-
用户头像
xm03
用户头像
普通的壹佰
用户头像
Albert_Seven
用户头像
夏旭日

分享 666

lzyz000
6天前

无标题.png




lzyz000
14天前

线段树维护序列,每个节点上维护一个权值平衡树,权值平衡树维护线段树相应节点的所有数。

需要特别注意操作 $2$ ,需要跑二分求值,复杂度 $O(\log ^3 n)$

总复杂度 $O(m \log ^ 2 n)$

另外吐槽一句,$Luogu$ 上线段树套 $splay$ 竟然卡不过去

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e6 + 10, INF = 2e9;
int idx, w[N], n, m;

#define IN stdin->_IO_read_ptr<stdin->_IO_read_end?*stdin->_IO_read_ptr++:__uflow(stdin)
#define OUT(_ch) stdout->_IO_write_ptr<stdout->_IO_write_end?*stdout->_IO_write_ptr++=_ch:__overflow(stdout,_ch)
inline void read(int &x){
    x=0;
    char ch=IN;
    while(ch<47)ch=IN;      
    while(ch>47)x=(x<<1)+(x<<3)+(ch^48),ch=IN;
}

struct Splay {
    int s[2], p, v, size;
    void init(int _p, int _v) {
        p = _p, v = _v, size = 1;
    }
};

struct Mathods_Splay {
    Splay tr[N];
    inline void pushup(int x) {
        tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
    }
    inline void rotate(int x) {
        int y = tr[x].p, z = tr[y].p, k = tr[y].s[1] == x;
        if (z) tr[z].s[tr[z].s[1] == y] = x; tr[x].p = z;
        tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
        tr[x].s[k ^ 1] = y, tr[y].p = x;
        pushup(y), pushup(x);
    }
    inline void splay(int &root, int x, int k) {
        while (tr[x].p != k) {
            int y = tr[x].p, z = tr[y].p;
            if (z != k) rotate(((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) ? y : x);
            rotate(x);
        }
        if (!k) root = x;
    }
    inline int find(int &root, int v) {
        int u = root;
        if (!u) return -1;
        while (v != tr[u].v && tr[u].s[v > tr[u].v])
            u = tr[u].s[v > tr[u].v];
        splay(root, u, 0);
        return u;
    }
    inline void insert(int &root, int v) {
        int u = root, fa = 0;
        while (u) fa = u, u = tr[u].s[v > tr[u].v];
        u = ++ idx;
        if (fa) tr[fa].s[v > tr[fa].v] = u;
        tr[u].init(fa, v);
        splay(root, u, 0);
    }
    inline int get_rank(int &root, int v) {
        int u = root, res = 0;
        while (u) {
            if (tr[u].v < v) res += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
            else u = tr[u].s[0];
        }
//        splay(root, u, 0);
        return res;
    }
    inline void update(int &root, int x, int y) {
        int u = root;
        while (u) {
            if (tr[u].v == x) break;
            if (tr[u].v < x) u = tr[u].s[1];
            else u = tr[u].s[0];
        }
        splay(root, u, 0);
        int l = tr[u].s[0], r = tr[u].s[1];
        while (tr[l].s[1]) l = tr[l].s[1];
        while (tr[r].s[0]) r = tr[r].s[0];
        splay(root, l, 0), splay(root, r, l);
        tr[r].s[0] = 0;
        pushup(r), pushup(l);
        insert(root, y);
    }
    inline int get_pre(int &root, int v) {
        int u = root, res = -2147483647;
        while (u) {
            if (tr[u].v < v) res = max(res, tr[u].v), u = tr[u].s[1];
            else u = tr[u].s[0];
        }
//      splay(root, u, 0);
        return res;
    }
    inline int get_next(int &root, int v) {
        int u = root, res = 2147483647;
        while (u) {
            if (tr[u].v > v) res = min(res, tr[u].v), u = tr[u].s[0];
            else u = tr[u].s[1];
        }
//      splay(root, u, 0);
        return res;
    }
}s;

struct Tree {
    int l, r;
    int root;
}tr[N << 2];

inline void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    s.insert(tr[u].root, -INF), s.insert(tr[u].root, INF);
    for (register int i = l; i <= r; i ++ )
        s.insert(tr[u].root, w[i]);
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
inline int query_rank(int u, int l, int r, int v) {
    if (tr[u].l >= l && tr[u].r <= r) return s.get_rank(tr[u].root, v) - 1;
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    if (l <= mid) res += query_rank(u << 1, l, r, v);
    if (r > mid) res += query_rank(u << 1 | 1, l, r, v);
    return res;
}
inline void modify(int u, int x, int v) {
    s.update(tr[u].root, w[x], v);
    if (tr[u].l == tr[u].r) return;
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);
}
inline int query_pre(int u, int l, int r, int x) {
    if (tr[u].l >= l && tr[u].r <= r) return s.get_pre(tr[u].root, x);
    int mid = tr[u].l + tr[u].r >> 1, res = -2147483647;
    if (l <= mid) res = max(res, query_pre(u << 1, l, r, x));
    if (r > mid) res = max(res, query_pre(u << 1 | 1, l, r, x));
    return res;
}
inline int query_next(int u, int l, int r, int x) {
    if (tr[u].l >= l && tr[u].r <= r) return s.get_next(tr[u].root, x);
    int mid = tr[u].l + tr[u].r >> 1, res = 2147483647;
    if (l <= mid) res = min(res, query_next(u << 1, l, r, x));
    if (r > mid) res = min(res, query_next(u << 1 | 1, l, r, x));
    return res;
}

int main()
{
    read(n), read(m);
    int minn = INF, maxn = -INF;
    for (register int i = 1; i <= n; i ++ ) {
        read(w[i]);
        minn = min(minn, w[i]), maxn = max(maxn, w[i]);
    }
    build(1, 1, n);

    int op, l, r, k;
    while (m -- ) {
        read(op), read(l), read(r);
        if (op == 1) {
            read(k);
            printf("%d\n", query_rank(1, l, r, k) + 1);
        }
        if (op == 2) {
            read(k);
            int L = minn, R = maxn;
            while (L < R) {
                int mid = L + R + 1 >> 1;
                if (query_rank(1, l, r, mid) + 1 <= k) L = mid;
                else R = mid - 1;
            }
            printf("%d\n", R);
        }
        if (op == 3) {
            minn = min(minn, r), maxn = max(maxn, r);
            modify(1, l, r);
            w[l] = r;
        }
        if (op == 4) {
            read(k);
            printf("%d\n", query_pre(1, l, r, k) == -INF ? -2147483647 : query_pre(1, l, r, k));
        }
        if (op == 5) {
            read(k);
            printf("%d\n", query_next(1, l, r, k) == INF ? 2147483647 : query_next(1, l, r, k));
        }
    }

    return 0;
}


活动打卡代码 AcWing 3124. BSGS

lzyz000
23天前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long LL;
int p, a, n;
unordered_map<LL, LL> Map;

LL qpow(LL a, LL b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }   
    return res % p;
}

int main()
{
    while (scanf("%d%d%d", &a, &p, &n), a && p && n)
    {
        Map.clear();
        int len = sqrt(p) + 1;

        LL now = a, tmp;
        for (int i = 1; i <= len; i ++ , now = (now * a) % p)
            Map[(1ll * n * now) % p] = i;

        tmp = now = qpow(a, len);
        bool have_ans = false;
        for (int i = 1; i <= len; i ++ , now = (now * tmp) % p)
        {
            if (Map.count(now) == 0) continue;
            printf("%lld\n", i * len - Map[1ll * qpow(a, i * len)]);
            have_ans = true;
            break;
        }

        if (have_ans) continue;
        puts("No Solution");
    }
    return 0;
}


活动打卡代码 AcWing 276. I-区域

lzyz000
2个月前
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 16;
int n, m, k, w[N][N];
int f[N][N * N][N][N][2][2];

struct State
{
    int i, j, l, r, x, y;
}g[N][N * N][N][N][2][2];

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);

    memset(f, -0x3f, sizeof f);

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= k; j ++ )
            for (int l = 1; l <= m; l ++ )
                for (int r = l; r <= m; r ++ )
                {
                    if (j < r - l + 1) continue;

                    // 左扩张,右扩张
                    {
                        auto &vf = f[i][j][l][r][1][0];
                        auto &vg = g[i][j][l][r][1][0];

                        if (j == r - l + 1) vf = 0;

                        for (int p = l; p <= r; p ++ )
                            for (int q = p; q <= r; q ++ )
                            {
                                int val = f[i - 1][j - (r - l + 1)][p][q][1][0];
                                if (vf < val)
                                {
                                    vf = val;
                                    vg = {i - 1, j - (r - l + 1), p, q, 1, 0};
                                }
                            }

                        for (int u = l; u <= r; u ++ )
                            vf += w[i][u];
                    }

                    // 左扩张,右收缩
                    {
                        auto &vf = f[i][j][l][r][1][1];
                        auto &vg = g[i][j][l][r][1][1];

                        for (int p = l; p <= r; p ++ )
                            for (int q = r; q <= m; q ++ )
                                for (int y = 0; y <= 1; y ++ )
                                {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][1][y];
                                    if (vf < val)
                                    {
                                        vf = val;
                                        vg = {i - 1, j - (r - l + 1), p, q, 1, y};
                                    }
                                }

                        for (int u = l; u <= r; u ++ )
                            vf += w[i][u];
                    }

                    // 左收缩,右扩张
                    {
                        auto &vf = f[i][j][l][r][0][0];
                        auto &vg = g[i][j][l][r][0][0];

                        for (int p = 1; p <= l; p ++ )
                            for (int q = l; q <= r; q ++ )
                                for (int x = 0; x <= 1; x ++ )
                                {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][x][0];
                                    if (vf < val)
                                    {
                                        vf = val;
                                        vg = {i - 1, j - (r - l + 1), p, q, x, 0};
                                    }
                                }

                        for (int u = l; u <= r; u ++ )
                            vf += w[i][u];
                    }

                    {
                        auto &vf = f[i][j][l][r][0][1];
                        auto &vg = g[i][j][l][r][0][1];

                        for (int p = 1; p <= l; p ++ )
                            for (int q = r; q <= m; q ++ )
                                for (int x = 0; x <= 1; x ++ )
                                    for (int y = 0; y <= 1; y ++ )
                                    {
                                        int val = f[i - 1][j - (r - l + 1)][p][q][x][y];
                                        if (vf < val)
                                        {
                                            vf = val;
                                            vg = {i - 1, j - (r - l + 1), p, q, x, y};
                                        }
                                    }

                        for (int u = l; u <= r; u ++ )
                            vf += w[i][u];
                    }
                }

    int res = 0;
    State state;

    for (int i = 1; i <= n; i ++ )
        for (int l = 1; l <= m; l ++ )
            for (int r = 1; r <= m; r ++ )
                for (int x = 0; x <= 1; x ++ )
                    for (int y = 0; y <= 1; y ++ )
                    {
                        int val = f[i][k][l][r][x][y];
                        if (res < val)
                        {
                            res = val;
                            state = {i, k, l, r, x, y};
                        }
                    }

    printf("Oil : %d\n", res);

    while (state.j)
    {
        for (int i = state.l; i <= state.r; i ++ ) printf("%d %d\n", state.i, i);
        state = g[state.i][state.j][state.l][state.r][state.x][state.y];
    }

    return 0;
}



lzyz000
3个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 50010, M = (N + 125003) << 1, INF = 2147483647;

int h[N], ne[M], e[M], f[M], idx = 1, tot;
int d[N], cur[N], S, T, s, t, n, m, A[N];

void add(int a, int b, int c)
{
    e[ ++ idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx;
}

bool bfs()
{
    queue<int> q;
    memset(d, -1, sizeof d);
    d[S] = 0, q.push(S), cur[S] = h[S];

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q.push(ver);
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;

    int flow = 0;
    for (int i = cur[u]; i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(limit - flow, f[i]));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while (bfs()) while (flow = find(S, INF)) res += flow;
    return res;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);

    S = 0, T = n + 1;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, d - c), add(b, a, 0);
        A[a] -= c, A[b] += c;
    }

    for (int i = 1; i <= n; i ++ )
        if (A[i] > 0)
            add(S, i, A[i]), add(i, S, 0),
            tot += A[i];
        else if (A[i] < 0)
            add(i, T, -A[i]), add(T, i, 0);

    add(t, s, INF), add(s, t, 0);

    if (dinic() < tot) return puts("No Solution"), 0;

    int res = f[idx];
    S = t, T = s;
    f[idx] = f[idx - 1] = 0;

    return printf("%d\n", res - dinic()), 0;
}



lzyz000
3个月前

求助辛普森积分!!蒟蒻调了两个小时了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 110;
const double eps = 1e-6;
int n;
PDD q[N];

struct Triangle
{
    PDD p[4];
}tr[N];

double f(double x)
{
    int cnt = 0;
    bool have_intersection = false;

    for (int i = 0; i < n; i ++ )
    {
        for (int az = 0; az < 3; az ++ )
        {
            int j = az;
            int k = (j + 1) % 3; // 当前线段是 tr[j] - tr[k]
            if (tr[i].p[k].x < tr[i].p[j].x) swap(j, k);
            if (x >= tr[i].p[j].x && x <= tr[i].p[k].x) // 判断不经过线段的情况
            {
                have_intersection = true; 
                double x1 = tr[i].p[j].x, y1 = tr[i].p[j].y;
                double x2 = tr[i].p[k].x, y2 = tr[i].p[k].y;

                double k1 = (y2 - y1) / (x2 - x1);
                double b = y1 - k1 * x1;
                // 得到表达式 y = k1 * x + b
                // 得到交点坐标 x0, y0 
                double x0 = x, y0 = k1 * x0 + b;
                if (q[cnt].x == 0) q[cnt].x = y0;
                else q[cnt].y = y0;
            }
        }
        if (have_intersection) cnt ++ , have_intersection = false;
    }

    if (!cnt) return 0;
    for (int i = 0; i < cnt; i ++ )
        if (q[i].x > q[i].y)
            swap(q[i].x, q[i].y);

    sort(q, q + cnt);

    double res = 0, st = q[0].x, ed = q[0].y;
    for (int i = 1; i < cnt; i ++ )
        if (q[i].x <= ed) ed = max(ed, q[i].y);
        else
        {
            res += ed - st;
            st = q[i].x, ed = q[i].y;
        }

    res += ed - st;
    return res;
}

double simpson(double l, double r)
{
    auto mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}

double query(double l, double r, double s)
{
    auto mid = (l + r) / 2;
    auto left = simpson(l, mid), right = simpson(mid, r);
    if (fabs(s - left - right) < eps) return left + right;
    return query(l, mid, left) + query(mid, r, right);
}

int main()
{
    scanf("%d", &n);

    double l = 1e8, r = -1e8;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%lf%lf", &tr[i].p[0].x, &tr[i].p[0].y);
        scanf("%lf%lf", &tr[i].p[1].x, &tr[i].p[1].y);
        scanf("%lf%lf", &tr[i].p[2].x, &tr[i].p[2].y);

        for (int j = 0; j < 3; j ++ )
            l = min(l, tr[i].p[j].x),
            r = max(r, tr[i].p[j].x);
    }

    printf("%.2lf", query(l, r, simpson(l, r)));

    return 0;
}


活动打卡代码 AcWing 3069. 圆的面积并

lzyz000
3个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 1010;
const double eps = 1e-8;

struct Circle
{
    PDD p;
    double r;
}c[N];

int n;
PDD q[N];

PDD get(int i, double x) // 第i个圆与直线x的交点
{
    double d = fabs(c[i].p.x - x);
    double l = sqrt(c[i].r * c[i].r - d * d);
    return {c[i].p.y - l, c[i].p.y + l};
}

double f(double x)
{
    int cnt = 0;

    for (int i = 0; i < n; i ++ )
        if (fabs(c[i].p.x - x) <= c[i].r)
            q[cnt ++ ] = get(i, x);

    if (!cnt) return 0;
    sort(q, q + cnt);

    double res = 0;
    double st = q[0].x, ed = q[0].y;

    for (int i = 1; i < cnt; i ++ )
        if (q[i].x <= ed) ed = max(ed, q[i].y);
        else
        {
            res += ed - st;
            st = q[i].x, ed = q[i].y;
        }

    res += ed - st;

    return res;
}

double simpson(double l, double r)
{
    auto mid = (l + r) / 2;
    return (r - l) * (f(l) + f(r) + 4 * f(mid)) / 6;
}

double query(double l, double r, double s)
{
    auto mid = (l + r) / 2;
    auto left = simpson(l, mid), right = simpson(mid, r);
    if (fabs(s - left - right) < eps) return left + right;
    return query(l, mid, left) + query(mid, r, right);
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
        scanf("%lf%lf%lf", &c[i].p.x, &c[i].p.y, &c[i].r);

    if (n == 1)
        return printf("%.3lf", acos(-1) * c[0].r * c[0].r), 0;

    double l = -2000, r = 2000;
    printf("%.3lf\n", query(l, r, simpson(l, r)));

    return 0;
}



lzyz000
3个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-12;

double f(double x)
{
    return sin(x) / x;
}

double simpson(double l, double r)
{
    auto mid = (l + r) / 2;
    return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6;
}

double query(double l, double r, double s)
{
    auto mid = (l + r) / 2;
    auto left = simpson(l, mid), right = simpson(mid, r);
    if (fabs(left + right - s) < eps) return left + right;
    return query(l, mid, left) + query(mid, r, right);
}

int main()
{
    double l, r;
    scanf("%lf%lf", &l, &r);
    printf("%lf", query(l, r, simpson(l, r)));

    return 0;
}


活动打卡代码 AcWing 3068. 扫描线

lzyz000
5个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

const int N = 1010;
typedef pair<int, int> PII;
typedef long long LL;

PII q[N];
PII l[N], r[N];
int n;
vector<int> xs;

LL get_area(int a, int b)
{
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        if (l[i].x <= a && r[i].x >= b)
            q[cnt ++ ] = {l[i].y, r[i].y};

    if (!cnt) return 0;
    sort(q, q + cnt);

    LL res = 0;
    int st = q[0].x, ed = q[0].y;

    for (int i = 1; i < cnt; i ++ )
        if (q[i].x <= ed) ed = max(ed, q[i].y);
        else
        {
            res += ed - st;
            st = q[i].x, ed = q[i].y;
        }

    res += ed - st;

    return res * (b - a);
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
        scanf("%d%d%d%d", &l[i].x, &l[i].y, &r[i].x, &r[i].y), xs.push_back(l[i].x), xs.push_back(r[i].x);

    sort(xs.begin(), xs.end());

    LL res = 0;
    for (int i = 0; i < xs.size() - 1; i ++ )
        if (xs[i] != xs[i + 1])
            res += get_area(xs[i], xs[i + 1]);

    printf("%lld\n", res);

    return 0;
} 



lzyz000
5个月前

一道裸的计算几何问题。

直接用欧几里得距离解就行了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

PDD a, b;
int T;

double operator - (PDD a, PDD b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;

    return sqrt(dx * dx + dy * dy);
}

int main()
{
    scanf("%d", &T);

    while (T -- )
    {
        scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y);

        printf("%.2lf\n", a - b);
    }

    return 0;
}