求助卡常

Register_int @ 2023-11-21 20:12:19

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 4e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

struct node {
    int l, r; ll v;
    bool operator < (const node &rhs) const { return r == rhs.r ? l > rhs.l : r < rhs.r; }
} a[MAXN];

struct segt {
    int l, r; ll add, val;
} t[MAXM << 2];

inline 
void pushup(int p) {
    t[p].val = max(t[p << 1].val, t[p << 1 | 1].val);
}

inline 
void upd(int p, ll x) {
    t[p].add += x, t[p].val += x;
}

inline 
void pushdown(int p) {
    if (!t[p].add) return ;
    upd(p << 1, t[p].add), upd(p << 1 | 1, t[p].add), t[p].add = 0;
}

inline 
void build(int l, int r, int p) {
    t[p].l = l, t[p].r = r, t[p].add = t[p].val = 0;
    if (l == r) return ; int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

inline 
void modify(int k, ll x, int p) {
    if (t[p].l == t[p].r) return upd(p, x - t[p].val);
    pushdown(p); int mid = t[p].l + t[p].r >> 1;
    modify(k, x, p << 1 | k > mid), pushup(p);
}

inline 
void add(int l, int r, ll x, int p) {
    if (l <= t[p].l && t[p].r <= r) return upd(p, x);
    pushdown(p); int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) add(l, r, x, p << 1);
    if (r > mid) add(l, r, x, p << 1 | 1); pushup(p);
}

inline 
ll query(int l, int r, int p) {
    if (l <= t[p].l && t[p].r <= r) return t[p].val;
    pushdown(p); int mid = t[p].l + t[p].r >> 1; ll ans = -inf;
    if (l <= mid) ans = max(ans, query(l, r, p << 1));
    if (r > mid) ans = max(ans, query(l, r, p << 1 | 1)); return ans;
}

int b[MAXM], tot;

int c, T, n, m, p, k; ll x, d, ans;

int main() {
    freopen("run6.in", "r", stdin);
    for (scanf("%d%d", &c, &T); T--;) {
        scanf("%d%d%d%lld", &n, &m, &p, &d), tot = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%lld", &a[i].r, &a[i].l, &a[i].v);
            a[i].l = a[i].r - a[i].l + 1;
            b[++tot] = a[i].l, b[++tot] = a[i].r;
            b[++tot] = a[i].l - 1, b[++tot] = a[i].r + 1;
        }
        sort(b + 1, b + tot + 1), tot = unique(b + 1, b + tot + 1) - b - 1;
        for (int i = 1; i <= m; i++) {
            a[i].l = lower_bound(b + 1, b + tot + 1, a[i].l) - b;
            a[i].r = lower_bound(b + 1, b + tot + 1, a[i].r) - b;
        }
        sort(a + 1, a + m + 1), build(0, tot, 1);
        for (int i = 1, j = 1, k = 0; i <= tot; i++) {
            for (; b[i] - b[k] > p; k++);
            x = query(max(k - 1, 0), i - 1, 1);
            add(k, i - 1, -d * (b[i] - b[i - 1]), 1), modify(i, x, 1);
            if (k > 0) modify(k - 1, 0, 1);
            for (; j <= m && a[j].r < i; j++);
            for (; a[j].r == i; j++) add(k, a[j].l - 1, a[j].v, 1);
        }
        printf("%lld\n", query(0, tot, 1));
    }
}

by lsj2009 @ 2023-11-21 20:14:45

@Register_int 应该能做到 3m？我是只加了 l-1,r-k 和 r，是没有问题的。

by lsj2009 @ 2023-11-21 20:15:23

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=3e5+5;
namespace IO {
    char Is[(1<<21)+10],Os[(1<<21)+10];
    int Ipt,Opt;
    inline char gc() {
        if(Ipt==1<<21)
            Ipt=0;
        if(!Ipt)
            Is[fread(Is,1,1<<21,stdin)]=0;
        return Is[Ipt++];
    }
    inline void flush() {
        fwrite(Os,1,Opt,stdout);
        Opt=0;
    }
    inline void pc(char x) {
        if(Opt==1<<21)
            flush();
        Os[Opt++]=x;
    }
    inline int read() {
        int x=0;
        char ch=gc();
        while(ch<'0'||ch>'9')
            ch=gc();
        while(ch<='9'&&ch>='0')
            x=x*10+ch-'0',ch=gc();
        return x;
    }
}
using IO::read;
struct SGT {
    struct node {
        int l,r,val,tag;
    }; node tree[N<<2];
    #define ls(k) (k<<1)
    #define rs(k) (k<<1|1)
    inline void push_up(int k) {
        tree[k].val=max(tree[ls(k)].val,tree[rs(k)].val);
    }
    void build(int k,int l,int r) {
        tree[k]={l,r,0ll,0ll};
        if(l==r)
            return;
        int mid=(l+r)>>1;
        build(ls(k),l,mid);
        build(rs(k),mid+1,r);
        push_up(k);
    }
    inline void upd(int k,int val) {
        tree[k].val+=val; tree[k].tag+=val;
    }
    inline void push_down(int k) {
        int &t=tree[k].tag;
        if(t) {
            upd(ls(k),t); upd(rs(k),t);
            t=0;
        }
    }
    void update(int k,int ql,int qr,int val) {
        if(ql<=tree[k].l&&tree[k].r<=qr) {
            upd(k,val);
            return;
        }
        push_down(k);
        if(ql<=tree[ls(k)].r)
            update(ls(k),ql,qr,val);
        if(qr>=tree[rs(k)].l)
            update(rs(k),ql,qr,val);
        push_up(k);
    }
    int query(int k,int ql,int qr) {
        if(ql<=tree[k].l&&tree[k].r<=qr)
            return tree[k].val;
        push_down(k);
        int res=-INFLL;
        if(ql<=tree[ls(k)].r)
            chkmax(res,query(ls(k),ql,qr));
        if(qr>=tree[rs(k)].l)
            chkmax(res,query(rs(k),ql,qr));
        return res;
    }
}; SGT T;
int t[N],len;
inline int get_id(int x) {
    return lower_bound(t+1,t+len+1,x)-t;
}
struct seg {
    int l,r,val;
    bool operator < (const seg &tmp) const {
        return r<tmp.r;
    }
}; seg a[N];
inline void solve() {
    int n=read(),m=read(),k=read(),d=read();
    len=0;
    rep(i,1,m) {
        int r=read(),x=read(),val=read();
        a[i]={r-x,r,val};
        t[++len]=a[i].l;
        t[++len]=a[i].r;
        t[++len]=a[i].r-k;
    }
    sort(t+1,t+len+1);
    len=unique(t+1,t+len+1)-t-1;
    T.build(1,0,len-1);
    rep(i,1,m) {
        a[i].l=get_id(a[i].l); 
        a[i].r=get_id(a[i].r);
    }
    sort(a+1,a+m+1);
    int res=0,p=1;
    rep(i,1,len) {
        T.update(1,0,i-1,-d*(t[i]-t[i-1]));
        while(p<=m&&a[p].r==i)
            T.update(1,0,a[p].l,a[p].val),++p;
        chkmax(res,T.query(1,get_id(t[i]-k),i-1));
        if(i+1<len)
            T.update(1,i+1,i+1,res); 
    }
    printf("%lld\n",res);
}
//pretest at 12:44 , used time = 3.8s
signed main() {
//  freopen("run.in","r",stdin);
//  freopen("run.out","w",stdout);
    int _=read(),testcase=read();
    while(testcase--)
        solve();
    return 0;
}

by ottora @ 2023-11-21 20:19:22

可以做到 2m 的。转移只会在 l 开跑，在 r + 1 停止

by Register_int @ 2023-11-21 20:23:33

@debgxh 可以教教怎么改嘛，我改了半天答案总是小一点……

by _int_main_ @ 2023-11-21 20:25:08

@Register_int 状态怎么定义的

by _•́へ•́╬_ @ 2023-11-21 20:25:14

https://codeforces.com/gym/104803/submission/233330408

by ottora @ 2023-11-21 20:26:06

#include <bits/stdc++.h>
using namespace std;
#define LO(A, x) (lower_bound(A.begin(), A.end(), x) - A.begin())
#define UP(A, x) (upper_bound(A.begin(), A.end(), x) - A.begin())
constexpr int MAXN = 100005;
int _, T, n, m, K, D; int64_t Ans;
struct Seg{int l, r, v; bool operator < (const Seg &x) const {return r < x.r;}} A[MAXN];
struct SegTree{
    SegTree *ls, *rs; int64_t val, tag;
    SegTree(int l, int r): ls(nullptr), rs(nullptr), val(0), tag(0){
        if(r - l > 1){
            int mid = (l + r) >> 1;
            ls = new SegTree(l, mid);
            rs = new SegTree(mid, r);
        }
    }
    ~SegTree(){
        if(ls != nullptr) delete ls;
        if(rs != nullptr) delete rs;
    }
    void push_down(){ls->tag += tag, rs->tag += tag, tag = 0;}
    void push_up(){val = max(ls->val + ls->tag, rs->val + rs->tag);}
    void add(int l_, int r_, int64_t v, int l, int r){
        if(l_ >= r || r_ <= l) return;
        if(l_ <= l && r_ >= r){tag += v; return;}
        int mid = (l + r) >> 1; push_down();
        ls->add(l_, r_, v, l, mid);
        rs->add(l_, r_, v, mid, r);
        push_up();
    }
    void update(int id, int64_t v, int l, int r){
        if(r - l == 1){val = max(val, v); return;}
        int mid = (l + r) >> 1; push_down();
        if(id < mid) ls->update(id, v, l, mid);
        else         rs->update(id, v, mid, r);
        push_up();
    }
    int64_t get(int l_, int r_, int l, int r){
        if(l_ >= r || r_ <= l) return 0;
        if(l_ <= l && r_ >= r) return val + tag;
        int mid = (l + r) >> 1; push_down(); int64_t res = max(
            ls->get(l_, r_, l, mid),
            rs->get(l_, r_, mid, r)
        ); push_up(); return res;
    }
};
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    for(cin >> _ >> T; T--;){
        cin >> n >> m >> K >> D, Ans = 0; vector<int> V;
        for(int i = 1; i <= m; i++){
            int len; cin >> A[i].r >> len >> A[i].v;
            V.push_back(A[i].l = ++A[i].r - len);
            V.push_back(A[i].r);
        }
        sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end());
        sort(A + 1, A + m + 1), n = V.size(); SegTree T(0, n);
        for(int i = 0; i < n; i++) T.add(i, i + 1, (int64_t)V[i] * D, 0, n);
        for(int i = 0, j = 1; i < n; i++){
            for(; j <= m && A[j].r <= V[i]; j++) T.add(0, UP(V, A[j].l), A[j].v, 0, n);
            int64_t x = T.get(LO(V, V[i] - K), i, 0, n) - (int64_t)V[i] * D;
            if(Ans = max(Ans, x), i + 1 < n) T.update(i + 1, Ans, 0, n);
        }
        cout << Ans << '\n';
    }
    // cerr << (double)clock() / CLOCKS_PER_SEC << endl;
    return 0;
}

by _int_main_ @ 2023-11-21 20:30:11

@Register_int 如果是f_i表示第i天休息应该加l-1和r+1

by Register_int @ 2023-11-21 20:35:31

@_intmain 试过了，不加 r 会只对四个点。

by Register_int @ 2023-11-21 20:37:14

@_intmain dp_{i,j} 跑前 i 天，上一次不跑是第 j 天。