HDU 4866 Shooting(持久化线段树)

时间：2023-03-08 17:02:22
view code//第二道持久化线段树，照着别人的代码慢慢敲,还是有点不理解

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define lson l,m,ls[rt]

#define rson m+1,r,rs[rt]

const int N = 200020;

const int M = N*40;

int T[M], ls[M], rs[M], sum[M], id[N];

ll val[M];

int n, m, X, P, tot;

struct seg

{

    int p, h, id;

    seg() {}

    seg(int p, int h, int id):p(p),h(h),id(id) {}

    bool operator < (const seg &o) const{

        return p<o.p || (p==o.p&&h>o.h);

    }

}e[N];

int ecnt;

struct node

{

    int h, id;

    node(int h=0, int id=0):h(h),id(id) {}

    bool operator < (const node &o) const

    {

        return h<o.h;

    }

}sto[N];

void build(int l, int r, int& rt)

{

    rt = ++tot;

    sum[rt] = val[rt]=0;

    if(l==r) return ;

    int m = (l+r)>>1;

    build(lson);

    build(rson);

}

void update(int p, int c, ll v, int last, int l, int r, int &rt)

{

    rt = ++tot;

    ls[rt] = ls[last], rs[rt] = rs[last];

     sum[rt]=sum[last]+c, val[rt] = val[last]+v;

    if(r==l) return ;

    int m = (l+r)>>1;

    if(p<=m) update(p, c, v, ls[last], lson);

    else update(p, c, v, rs[last], rson);

}

ll query(int k, int l, int r, int rt)

{

    if(k==0) return 0;

    if(l==r) return val[rt];

    int m = (l+r)>>1;

    ll ans =  0;

    if(sum[ls[rt]]>k) ans = query(k, lson);

    else ans = val[ls[rt]] + query(k-sum[ls[rt]], rson);

    return ans;

}

int find(int key) //找到最后一个小于key||(等于key&&高度大于0) 位置

{

    int l = 1, r = ecnt, ans=0;

    while(l<=r)

    {

        int m = (l+r)>>1;

        if(e[m].p<key || (e[m].p==key&&e[m].h>=0))

            ans = m, l = m+1;

        else r = m-1;

    }

//    int l=1,r=ecnt+1, ans;

//    while (l<r)

//    {

//        int mid=(l+r)>>1;

//        if (e[mid].p<key || (e[mid].p==key && e[mid].h>=0)){

//            ans=mid;

//            l=mid+1;

//        }

//        else{

//            r=mid;

//        }

//    }

    return ans;

}

void show()

{

    for(int i=1; i<ecnt; i++)

    {

        printf("e[%d] = {%d, %d, %d}\n", i, e[i].p, e[i].h, id[e[i].id]);

    }

}

int main()

{

//    freopen("in.txt", "r", stdin);

    while(scanf("%d%d%d%d", &n, &m, &X, &P)>0)

    {

        ecnt = 0, tot = 0;

        int l, r, w;

        for(int i=1; i<=n; i++)

        {

            scanf("%d%d%d", &l, &r, &w);

            e[++ecnt] = seg(l, w, i);

            e[++ecnt] = seg(r, -w, i);

            sto[i] = node(w, i);

        }

        sort(e+1, e+ecnt+1);

        sort(sto+1, sto+n+1);

        for(int i=1; i<=n; i++) id[sto[i].id]=i;

//        show();

        build(1, n, T[0]);

        for(int i=1; i<=ecnt; i++)

        {

            update(id[e[i].id], (e[i].h>=0?1:-1), e[i].h, T[i-1], 1, n, T[i]);

        }

        ll pre=1;

        int pos, a, b, c;

        while(m--)

        {

            scanf("%d%d%d%d", &pos, &a, &b, &c);

            ll k = (ll)(a*pre+b)%c;

            int p =find(pos);

//            printf("pos = %d, p = %d, k = %I64d\n", pos, p, k);

//            printf("sum[%d] = %I64d\n", p, val[T[p]]);

            ll ans = query(k, 1, n, T[p]);

            if(pre>P) ans *=2;

            pre = ans;

            printf("%I64d\n", ans);

        }

    }

    return 0;

}
view code#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define lson l,m,ls[rt]

#define rson m+1,r,rs[rt]

const int N = 200020;

const int M = N*40;

int T[M], ls[M], rs[M], sum[M], id[N];

ll val[M];

int n, m, X, P, tot;

struct seg

{

    int p, h, id;

    seg() {}

    seg(int p, int h, int id):p(p),h(h),id(id) {}

    bool operator < (const seg &o) const{

        return p<o.p || (p==o.p&&h>o.h);

    }

}e[N];

int ecnt;

struct node

{

    int h, id;

    node(int h=0, int id=0):h(h),id(id) {}

    bool operator < (const node &o) const

    {

        return h<o.h;

    }

}sto[N];

void build(int l, int r, int& rt)

{

    rt = ++tot;

    sum[rt] = val[rt]=0;

    if(l==r) return ;

    int m = (l+r)>>1;

    build(lson);

    build(rson);

}

void update(int p, int c, ll v, int last, int l, int r, int &rt)

{

    rt = ++tot;

    ls[rt] = ls[last], rs[rt] = rs[last];

     sum[rt]=sum[last]+c, val[rt] = val[last]+v;

    if(r==l) return ;

    int m = (l+r)>>1;

    if(p<=m) update(p, c, v, ls[last], lson);

    else update(p, c, v, rs[last], rson);

}

ll query(int k, int l, int r, int rt)

{

    if(k==0) return 0;

    if(l==r) return val[rt];

    int m = (l+r)>>1;

    ll ans =  0;

    if(sum[ls[rt]]>k) ans = query(k, lson);

    else ans = val[ls[rt]] + query(k-sum[ls[rt]], rson);

    return ans;

}

int find(int key)

{

    int l = 1, r = ecnt, ans=0;

    while(l<=r)

    {

        int m = (l+r)>>1;

        if(e[m].p<=key)

            ans=m, l = m+1;

        else r = m-1;

    }

    return ans;

}

int gettype(int x)//negative or not

{

    return x>=0?1:-1;

}

int main()

{

    while(scanf("%d%d%d%d", &n, &m, &X, &P)>0)

    {

        ecnt = 0, tot = 0;

        int l, r, w;

        for(int i=1; i<=n; i++)

        {

            scanf("%d%d%d", &l, &r, &w);

            e[++ecnt] = seg(l, w, i);

            e[++ecnt] = seg(r+1, -w, i);

            sto[i] = node(w, i);

        }

        sort(e+1, e+ecnt+1);

        sort(sto+1, sto+n+1);

        for(int i=1; i<=n; i++) id[sto[i].id]=i;

        build(1, n, T[0]);

        for(int i=1; i<=ecnt; i++)

        {

            update(id[e[i].id], gettype(e[i].h), e[i].h, T[i-1], 1, n, T[i]);

        }

        ll pre=1;

        int pos, a, b, c;

        while(m--)

        {

            scanf("%d%d%d%d", &pos, &a, &b, &c);

            ll k = (ll)(a*pre+b)%c;

            int p =find(pos);

            ll ans = query(k, 1, n, T[p]);

            if(pre>P) ans *=2;

            pre = ans;

            printf("%I64d\n", ans);

        }

    }

    return 0;

}

相关文章