莫名全 WA 求调
查看原帖
莫名全 WA 求调
224978
optimize_2楼主2021/7/7 17:14
#include<bits/stdc++.h>
typedef long long ll;
#define MAXN 500010
using namespace std;

ll n, m;
ll l, r, s, e;
ll a[MAXN];

ll val[MAXN * 4], tag[MAXN * 4];
inline ll ls(ll x) {return x*2;}
inline ll rs(ll x) {return x*2 + 1;}

void pushdown(ll x, ll l, ll r) {
    ll lazy = tag[x],
        mid = (l+r) >> 1;
    tag[x] = 0;
    tag[ls(x)] += lazy;
    tag[ls(x)] += lazy;
    val[ls(x)] += lazy * (mid-l+1);
    val[rs(x)] += lazy * (r-mid);
}

void pushup(ll x, ll l, ll r) {
    val[x] = val[ls(x)] + val[rs(x)];
}

void modify(ll x, ll nl, ll nr, ll l, ll r, ll k) {
    if (l <= nl && nr <= r) {
        tag[x] += k;
        val[x] += k*(nr-nl+1);
        return;
    }
    pushdown(x, nl, nr);
    ll mid = (nl+nr) >> 1;
    if (l <= mid) modify(ls(x), nl, mid, l, r, k);
    if (mid+1 <= r) modify(rs(x), mid+1, nr, l, r, k);
    pushup(x, nl, nr);
}

ll query(ll x, ll nl, ll nr, ll l, ll r) {
    pushdown(x, nl, nr);
    if (l <= nl && nr <= r) {
        return val[x];
    }
    ll mid = (nl+nr) >> 1,
        ret = 0;
    if (l <= mid && nl<=r) ret += query(ls(x), nl, mid, l, r);
    if (mid+1 <= r && l <= nr) ret += query(rs(x), mid+1, nr, l, r);
    return ret;
}

template <typename T> void read(T &x){ ll f=1;x=0;char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-f; for (; isdigit(c);c=getchar()) x=x*10+c-'0'; x*=f;
}

int main() {
    read(n);
    read(m);
    for (ll i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= m; i++) {
        int opt;
        read(opt);
        if (opt == 1) {
            read(l);
            read(r);
            read(s);
            read(e);
            if (l != r) modify(1, 1, n, l+1, r, e);
            modify(1, 1, n, l, l, s);
            if (r != n) {
                //cout << l << " " << r <<" " << s << " " << e << endl;
                modify(1, 1, n, r+1, r+1, -(s + e*(r-l)));
            }
        } else {
            read(l);
            cout << a[l] + query(1, 1, n, 1, l) << endl;
        }
        /*
        read(l);
        read(r);
        read(s);
        read(e);
        int delta = (e-s) / (r-l);
        modify(1, 1, n, l, r, delta);
        */
    }
}

int 和 long long 都试过了youl

2021/7/7 17:14
加载中...