Блог пользователя non--stop

Автор non--stop, история, 4 года назад, По-английски
#include<bits/stdc++.h>
using namespace std;
 
#define f              first
#define s              second
#define int             long long int
#define pb              push_back
 
// #define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define vvi             vector<vi>
#define vb              vector<bool>
#define vvb             vector<vb>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
typedef long long ll;
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define MAXN			(int)1e+5
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct data {
	int sum;
};
int n, a[MAXN];
data t[4 * MAXN];
data lazy[4 * MAXN];
data combine(data l, data r) {
	data res;
	res.sum = l.sum + r.sum;
	return res;
}
 
data make_data(int val) {
	data res;
	res.sum = val;
	return res;
}
void push(int v, int tl, int tr)
{
	t[v * 2] = combine(t[v * 2], make_data((tr - tl + 1) / 2 * lazy[v].sum));
	t[v * 2 + 1] = combine(t[v * 2 + 1], make_data((tr - tl + 1) / 2 * lazy[v].sum));
	lazy[v * 2] = combine(lazy[v * 2], lazy[v]);
	lazy[v * 2 + 1] = combine(lazy[v * 2 + 1], lazy[v]);
	lazy[v] = make_data(0);
}
// range update a[l...r]
void update(int v, int tl, int tr, int l, int r, int addend)
{
	if (l > r)	return;
	if (l == tl && tr == r) {
		t[v] = combine(t[v], make_data(addend * (tr - tl + 1)));
		if (tl != tr)	lazy[v] = combine(lazy[v], make_data(addend));
	} else {
		push(v, tl, tr);
		int tm = (tl + tr) / 2;
		update(v * 2, tl, tm, l, min(r, tm), addend);
		update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
		t[v] = combine(t[v * 2], t[v * 2 + 1]);
	}
}
// range query a[l...r]
data query(int v, int tl, int tr, int l, int r) {
	if (l > r)	return make_data(0);
	if (l == tl && r == tr)	return t[v];
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	return combine(query(v * 2, tl, tm, l, min(r, tm)),
	               query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
int32_t main()
{
	int test;	cin >> test;
	while (test--)
	{
		cin >> n;
		int q;	cin >> q;
		while (q--)
		{
			int op, l, r;	cin >> op >> l >> r;
			if (op == 0)
			{
				int addend;	cin >> addend;
				update(1, 0, n - 1, l - 1, r - 1, addend);
			}
			else if (op == 1)
			cout << query(1, 0, n - 1, l - 1, r - 1).sum << "\n";
		}
	}
	return 0;
} 

it's giving wrong answer on submitting in spoj but working fine in sublime text 3.

  • Проголосовать: нравится
  • -37
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

MAXN is 10^5

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://cp-algorithms.com/data_structures/fenwick.html You can use Range Updates Range Queries to solve this problem. Or You can use Lazy Propagation for adding on segments from https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-10