Cutting Bamboos

小灰灰 2023-08-17 16:26 102阅读 0赞

可持久线段树

[https://ac.nowcoder.com/acm/problem/52172][https_ac.nowcoder.com_acm_problem_52172]

#include<iostream>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<map>
    #include<vector>
    #include<math.h>
    #include<queue>
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    #define fod(i,a,b) for(int i=a;i>=b;i--)
    #define me0(a) memset(a,0,sizeof(a))
    #define me1(a) memset(a,-1,sizeof(a))
    using namespace std;
     
    const int maxn = 4e6 + 100;
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
     
    void read(LL& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
     
    LL n, q, a[maxn], b[maxn], sz, tot, root[maxn];
    LL ls[maxn], rs[maxn], rt[maxn], val[maxn];
    LL s[maxn];//s表示总和
    LL sum[maxn];
     
    void build(LL& o, int L, int R) {
        o = ++tot;
        val[o] = 0; s[o] = 0;
        if (L == R) return;
        int m = (L + R) >> 1;
        build(ls[o], L, m);
        build(rs[o], m + 1, R);
    }
     
    void update(LL& o, int L, int R, int last, int p) {
        //last 指的是上一个root的结点编号
        o = ++tot;
        ls[o] = ls[last];//
        rs[o] = rs[last];
        s[o] = s[last] + p;
        val[o] = val[last] + 1;//表示当前结点的重量增加1
        if (L == R) return;
        int m = (L + R) >> 1;
        if (p <= m) update(ls[o], L, m, ls[last], p);//根据p值判断插入左子树还是右子树中
        else update(rs[o], m + 1, R, rs[last], p);
    }
     
    int query(int ss, int tt, int L, int R, int k) {
        //区间起点、终点，查询的第k小
        if (L == R) return L;
        int m = (L + R) >> 1;
        int cnt = val[ls[tt]] - val[ls[ss]];//结点的左子树相减，表示这个期间左子树上增加了多少个新的值，然后常规操作
        if (k <= cnt) return query(ls[ss], ls[tt], L, m, k);//说明第k小在当前m的左边
        else return query(rs[ss], rs[tt], m + 1, R, k - cnt);
     
    }
     
    LL query2(int ss, int tt, int L, int R, int k) {
        //查询前k小的和
        if (L == R)  {
            return (LL)k * L;
        }
        int m = (L + R) >> 1;
     
        int cnt = val[ls[tt]] - val[ls[ss]];
        if (k > cnt) {
            return s[ls[tt]] - s[ls[ss]] + query2(rs[ss], rs[tt], m + 1, R, k - cnt);
        }
        else {
            return query2(ls[ss], ls[tt], L, m, k);
        }
     
    }
     
    void work() {
        LL ql, qr, x, y;
        read(ql); read(qr); read(x); read(y);
        double dpart = double(sum[qr] - sum[ql - 1]) / y * x;//切掉部分的长度和
        LL L = 0, R = qr - ql + 1, m = 0, res = 0;
        LL num = qr - ql + 1;//总共num根竹子
        LL Kth = a[ql], Ksum = 0, K = 0;
        while (L <= R) {
            m = (L + R) >> 1;
            Kth = query(root[ql - 1], root[qr], 1, sz, m);//找到m小,表示切到了第m小
            Ksum = query2(root[ql - 1], root[qr], 1, sz, m);//前m小
            Ksum = sum[qr] - sum[ql - 1] - Ksum - (num - m) * Kth;//切掉的部分
     
            if ((double)Ksum - 0.00000001 >= dpart) {
                res = Kth;
                K = m;
                L = m + 1;
            }
            else {
                R = m - 1;
            }
        }
        double ans = Kth + ((double)Ksum - dpart) / (num - K);
        printf("%.9lf\n", ans);
         
    }
     
    int main() {
        //freopen("in.txt", "r", stdin);
        read(n); read(q);
        fo(i, 1, n) read(a[i]), sum[i] = sum[i - 1] + a[i], sz = max(sz, a[i]);//这里a[i]是连续的，不连续的需要另外做处理
        tot = 0;
        build(root[0], 1, sz);//首先建立一个空树
     
        fo(i, 1, n) update(root[i], 1, sz, root[i - 1], a[i]);//按输入顺序依次插入到相应的结点中去，并更改途中结点的信息（此时该结点有多少个子节点）
     
        while (q--) work();
        return 0;
    }

[https://cloud.tencent.com/developer/article/1421786][https_cloud.tencent.com_developer_article_1421786]

转载于:https://www.cnblogs.com/Aiahtwo/p/11364160.html

[https_ac.nowcoder.com_acm_problem_52172]: https://ac.nowcoder.com/acm/problem/52172
[https_cloud.tencent.com_developer_article_1421786]: https://cloud.tencent.com/developer/article/1421786