SPOJ HORRIBLE - Horrible Queries
//Next Codeforces Round #354 (Div. 2)
// Accepted
// Segment Tree (Lazy Propagation)
#include<bits/stdc++.h>
//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>
using namespace std;
#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
//#define i64 long long
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
const int high = 1 << 18;
struct info
{
LL sum, prop;
};
info tree[high];
void update(int node, int b , int e , int i , int j , LL x)
{
if(i == b and j == e)
{
tree[node].sum+=(x * (e - b + 1));
tree[node].prop+=x;
return;
}
int Left = node << 1;
int Right = Left + 1;
int mid = (b + e) >> 1;
if(j <= mid)
{
update(Left, b , mid , i, j, x);
}
else if(i > mid)
{
update(Right, mid+1, e , i , j , x);
}
else
{
update(Left, b , mid, i , mid, x);
update(Right, mid+1 , e , mid+1 , j , x);
}
tree[node].sum = tree[Left].sum + tree[Right].sum + (tree[node].prop * (e - b + 1));
}
LL query(int node, int b , int e , int i , int j , LL carry=0)
{
if(i == b and j == e)
{
return tree[node].sum + carry * (e - b + 1);
}
int Left = node << 1;
int Right = Left + 1;
int mid = (b + e) >> 1;
if(j <= mid)
{
return query(Left, b , mid, i , j , carry+tree[node].prop);
}
else if(i > mid)
{
return query(Right, mid+1 , e , i , j , carry+tree[node].prop);
}
else
{
LL p1 = query(Left, b , mid , i , mid, carry+tree[node].prop);
LL p2 = query(Right, mid+1 , e , mid+1 , j , carry+tree[node].prop);
return p1 + p2;
}
}
int main()
{
int t , n , c , type , p , q;
LL v;
sf("%d", &t);
while(t--)
{
memset(tree, 0, sizeof(tree));
sf("%d %d", &n , &c);
while(c--)
{
sf("%d", &type);
if(type)
{
sf("%d %d", &p, &q);
pf("%lld\n", query(1 , 0, n-1, p-1, q-1, 0));
}
else
{
sf("%d %d %lld", &p, &q, &v);
update(1, 0, n-1, p-1, q-1, v);
}
}
}
return 0;
}
// Accepted
// Segment Tree (Lazy Propagation)
#include<bits/stdc++.h>
//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>
using namespace std;
#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
//#define i64 long long
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
const int high = 1 << 18;
struct info
{
LL sum, prop;
};
info tree[high];
void update(int node, int b , int e , int i , int j , LL x)
{
if(i == b and j == e)
{
tree[node].sum+=(x * (e - b + 1));
tree[node].prop+=x;
return;
}
int Left = node << 1;
int Right = Left + 1;
int mid = (b + e) >> 1;
if(j <= mid)
{
update(Left, b , mid , i, j, x);
}
else if(i > mid)
{
update(Right, mid+1, e , i , j , x);
}
else
{
update(Left, b , mid, i , mid, x);
update(Right, mid+1 , e , mid+1 , j , x);
}
tree[node].sum = tree[Left].sum + tree[Right].sum + (tree[node].prop * (e - b + 1));
}
LL query(int node, int b , int e , int i , int j , LL carry=0)
{
if(i == b and j == e)
{
return tree[node].sum + carry * (e - b + 1);
}
int Left = node << 1;
int Right = Left + 1;
int mid = (b + e) >> 1;
if(j <= mid)
{
return query(Left, b , mid, i , j , carry+tree[node].prop);
}
else if(i > mid)
{
return query(Right, mid+1 , e , i , j , carry+tree[node].prop);
}
else
{
LL p1 = query(Left, b , mid , i , mid, carry+tree[node].prop);
LL p2 = query(Right, mid+1 , e , mid+1 , j , carry+tree[node].prop);
return p1 + p2;
}
}
int main()
{
int t , n , c , type , p , q;
LL v;
sf("%d", &t);
while(t--)
{
memset(tree, 0, sizeof(tree));
sf("%d %d", &n , &c);
while(c--)
{
sf("%d", &type);
if(type)
{
sf("%d %d", &p, &q);
pf("%lld\n", query(1 , 0, n-1, p-1, q-1, 0));
}
else
{
sf("%d %d %lld", &p, &q, &v);
update(1, 0, n-1, p-1, q-1, v);
}
}
}
return 0;
}
Comments
Post a Comment