0pts 全RE求助
查看原帖
0pts 全RE求助
917407
hitori__楼主2024/6/7 10:07

下载的第一个pts自己测都能对,交上去全RE

#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
typedef long long ll;
typedef uint64_t ull;
typedef double db;
const int N = 1e5+5;
ll mod = 1e9 + 7;

ll n, m;
ll a[N];

struct node{
	ll l, r;
	ll sum;
	pair<ll, ll> lazy;  //k, d
} tr[N << 2];

void pushup(int p)
{
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}

//返回长度为n,首项a1,公差为d的和
ll getSum(ll n, ll a1, ll d)
{
	return a1*n + (((n-1) * n * d) >> 1);
}

void pushdown(int p)
{
	ll k = tr[p].lazy.first;
	ll d = tr[p].lazy.second;
	if(!k && !d) return;

	tr[p].lazy = {0, 0};

	ll ln =tr[lc].r-tr[lc].l+1;
	ll rn =tr[rc].r-tr[rc].l+1;
	
	tr[lc].sum += getSum(ln, k, d);
	tr[rc].sum += getSum(rn, (k+(tr[rc].l-tr[lc].l)*d), d);

	tr[lc].lazy.first += k;
	tr[lc].lazy.second += d;
	tr[rc].lazy.first += (k+(tr[rc].l-tr[lc].l)*d);
	tr[rc].lazy.second += d;
}

void build(int p, int l, int r)
{
	tr[p] = {l, r, a[l], {0, 0}};
	
	if(l == r) return ;

	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m+1, r);
	pushup(p);
}

void update(int p, int l, int r, ll k, int d)
{
	if(l<=tr[p].l && tr[p].r<=r){
		ll a1 = k + (tr[p].l - l) * d;
		tr[p].sum += getSum(tr[p].r-tr[p].l+1, a1, d);
		tr[p].lazy.first += a1;
		tr[p].lazy.second += d;
		return;
	}

	pushdown(p);

	int m = tr[p].l + tr[p].r >> 1;
	if(m >= l) update(lc, l, r, k, d);
	if(m < r) update(rc, l, r, k, d);
	pushup(p);
}

ll Q(int p, int l)
{
	if(tr[p].l==tr[p].r && tr[p].l==l){
		return tr[p].sum;
	}

	pushdown(p);

	int m = tr[p].l + tr[p].r >> 1;
	if(m >= l) Q(lc, l);
	else Q(rc, l);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i];

	build(1, 1, n);

	while(m--){
		int opt; cin >> opt;
		if(opt == 1){
			int l, r, K, D;
			cin >> l >> r >> K >> D;
			update(1, l, r, K, D);
		}else{
			int p; cin >> p;
			cout << Q(1, p) << endl;
		}
	}
	

    return 0;
}

2024/6/7 10:07
加载中...