#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 400000;
const int MAXM = 7;
int i, j, n, m, nn;
ll a[MAXN];
ll g[MAXN][MAXM];
ll idx[MAXN], f[MAXN];
int getIdx(int v){
return
min(v, MAXM - 1);
}
void push(int l, int r, int o){
if
(!f[o])
return
;
idx[o] = getIdx(idx[o] + f[o]);
if
(l != r){
idx[2 * o] = getIdx(idx[2 * o] + f[o]);
idx[2 * o + 1] = getIdx(idx[2 * o + 1] + f[o]);
f[2 * o] += f[o];
f[2 * o + 1] += f[o];
}
f[o] = 0;
}
void updatePoint(int l, int r, int o){
if
(l == r)
return
;
g[o][idx[o]] = g[2 * o][idx[2 * o]] + g[2 * o + 1][idx[2 * o + 1]];
return
;
int x, y, z;
for
(int w = 0; w < MAXM; w++){
x = getIdx(idx[o] + w);
y = getIdx(idx[2 * o] + w);
z = getIdx(idx[2 * o + 1] + w);
g[o][x] = g[2 * o][y] + g[2 * o + 1][z];
}
}
void update(int l, int r, int v, int u, int o){
if
(l > u || r < v)
return
;
if
(l >= v && r <= u){
f[o]++;
push(l, r, o);
return
;
}
push(l, r, o);
update(l, (l + r) / 2, v, u, 2 * o);
update((l + r) / 2 + 1, r, v, u, 2 * o + 1);
updatePoint(l, r, o);
}
ll find(int l, int r, int v, int u, int o){
push(l, r, o);
if
(l > u || r < v)
return
0;
if
(l >= v && r <= u)
return
g[o][idx[o]];
return
find(l, (l + r) / 2, v, u, 2 * o) +
find((l + r) / 2 + 1, r, v, u, 2 * o + 1);
}
int get(ll v){
ll l, r, x;
l = 1;
r = min(v, 1000000001LL);
while
(l < r - 1){
x = (l + r) / 2;
if
(x * x <= v)
l = x;
else
r = x;
}
return
x;
}
int main(){
int x, y, z;
int testCase = 0;
while
(scanf(
"%d"
,&n) == 1){
testCase ++;
if
(testCase != 1)
printf(
"\n"
);
printf(
"Case #%d:\n"
, testCase);
for
(i = 0; i < n; i++)
scanf(
"%I64d"
, &a[i]);
for
(nn = 1; nn < n; nn *= 2);
for
(i = 0; i < n; i++){
g[nn + i][0] = a[i];
for
(j = 1; j < MAXM; j++)
g[nn + i][j] = get(g[nn + i][j - 1]);
}
for
(i = n; i < nn; i++)
for
(j = 0; j < MAXM; j++)
g[nn + i][j] = 0;
for
(i = nn - 1; i >= 1; i--)
for
(j = 0; j < MAXM; j++)
g[i][j]= g[2 * i][j] + g[2 * i + 1][j];
for
(i = 0; i < 2 * nn; i++)
idx[i] = f[i] = 0;
scanf(
"%d"
, &m);
for
(i = 0; i < m; i++){
scanf(
"%d %d %d"
,&x, &y, &z);
if
(y > z) swap(y,z);
if
(x == 1)
printf(
"%I64d\n"
, find(1, nn, y, z, 1));
else
update(1, nn, y, z, 1);
}
}
return
0;
}
The type of a vector (i.e. T in vector<T>) needs to support copy. The
standard does not allow copy of arrays.
i.e.
int a[2];
int b[2];
b=a; // not allowed.
Dixtosa ![]() Eშისაიდან მოვიდა 3**13?ისე 4 * 52 * 3**13 = 331M+ ...
|
Quick ![]() Upsolving ჩაირთო...
|
saba_tavdgiridze ![]() აღარ მინდა.:)...
|
saba_tavdgiridze ![]() B ამოცანის 17 ტესტს ვერ მიმანიშნებთ?...
|
tornike5 ![]() ვაპირებდი იგივე მეკითხა მარა მეგონა უეჭველი იქნება...
|
giorgi123 ![]() მადლობა.შარშან ფინალში ამოცანების ყურებით ვიფარგლე...
|
Elle ![]() შარშან ფინალს codeblocks-ით წერდით?დავაყენეთ codeb...
|
D ზე არ მიფიქრია ჯერ.