-
Notifications
You must be signed in to change notification settings - Fork 0
/
Range_update_Range_query
137 lines (131 loc) · 3.68 KB
/
Range_update_Range_query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
#define pf printf
#define sc scanf
#define PI 2*acos(0.0)
#define fast ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define MAX 1234567899
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vSort(v) sort(all(v))
#define maxSort(v) sort(all(v),greater<int>())
#define Unique(v) v.erase(unique(all(v)),v.end())
#define sqr(x) ((x)*(x))
#define qube(x) ((x)*(x)*(x))
#define deci(n) cout<<fixed<<setprecision(n)
#define sci(n) sc("%d",&(n))
#define scii(x,y) sc("%d %d",&(x),&(y))
#define scl(x) sc("%lld",&(x))
#define scll(x,y) sc("%lld %lld",&(x),&(y))
#define vi vector<int>
#define hi pf(" HI \n")
#define pp pair<int,int>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define F first
#define S second
#define check(n,pos) (n & (1<<(pos)))
#define biton(n,pos) (n (1<<(pos)))
#define bitoff(n,pos) (n & ~(1<<(pos)))
typedef long long int lli;
typedef unsigned long long int ulli;
int dx4[] = { 0, 0, -1, 1 } ;
int dy4[] = { -1, 1, 0, 0 } ;
bool valid( int r, int c, int x, int y )
{
if( x >= 1 && x <= r && y >= 1 && y <= c ) return 1 ;
return 0 ;
}
using namespace std;
lli segtree[1000000];
lli lazy[1000000];
int input[1000000];
void construct_tree(int low,int high,int pos)
{
if(low==high)
{
segtree[pos]=input[low];
return ;
}
int mid=low+((high-low)/2);
construct_tree(low,mid,2*pos+1);
construct_tree(mid+1,high,2*pos+2);
segtree[pos]=segtree[2*pos+1]+segtree[2*pos+2];
}
void pushdown(int low,int high,int pos)
{
if(lazy[pos]!=0)
{
int mid=low+((high-low)/2);
segtree[2*pos+1]+=(mid-low+1)*lazy[pos];
lazy[2*pos+1]+=lazy[pos];
segtree[2*pos+2]+=(high-mid)*lazy[pos];
lazy[2*pos+2]+=lazy[pos];
lazy[pos]=0;
}
else
return ;
}
void lazy_tree(int st,int en,int value,int low,int high,int pos)
{
pushdown(low,high,pos);
if(en<low || st>high)
return ;
if(low>=st && high<=en)
{
segtree[pos]+=(high-low+1)*value;
lazy[pos]+=value;
return ;
}
int mid=low+((high-low)/2);
lazy_tree(st,en,value,low,mid,2*pos+1);
lazy_tree(st,en,value,mid+1,high,2*pos+2);
segtree[pos]=segtree[2*pos+1]+segtree[2*pos+2];
}
lli rangequery(int st,int en,int low,int high,int pos)
{
pushdown(low,high,pos);
if(en<low || st>high)
return 0;
if(low>=st && high<=en)
{
return segtree[pos];
}
int mid=low+((high-low)/2);
return (rangequery(st,en,low,mid,2*pos+1)+
rangequery(st,en,mid+1,high,2*pos+2));
}
int main ()
{
int t,p,x,y,r;
int n,q;
sci(t);
for(int tt=1; tt<=t; tt++)
{
mem(segtree,0);
mem(lazy,0);
mem(input,0);
scii(n,q);
construct_tree(0,n-1,0);
pf("Case %d:\n",tt);
for(int i=1; i<=q; i++)
{
sci(p);
if(p==0)
{
scii(x,y);
sci(r);
lazy_tree(x,y,r,0,n-1,0);
}
else
{
scii(x,y);
lli ppp=rangequery(x,y,0,n-1,0);
pf("%lld\n",ppp);
}
}
}
return 0;
}