#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
#define SQN (333)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
struct BUC {
ll Y[MAXN][30];
ll sum[MAXN/SQN+5][30];
int sumidx[MAXN/SQN+5];
int getIdx(int X) { return (X-1)/SQN + 1; }
int getSidx(int idx) { return (idx-1)*SQN + 1; }
int getEidx(int idx) { return idx*SQN; }
void rotY(int X, int cnt = 1) {
if(!cnt) return; if(30 < cnt) cnt = 30;
for(int i = cnt; i < 30; i++) Y[X][i-cnt] = Y[X][i];
for(int i = 30-cnt; i < 30; i++) Y[X][i] = 0;
}
void updBuc(int idx) {
const int S = getSidx(idx), E = getEidx(idx);
for(int i = S; i <= E; i++) rotY(i, sumidx[idx]);
sumidx[idx] = 0; fill(sum[idx], sum[idx]+30, 0);
for(int i = S; i <= E; i++) for(int j = 0; j < 30; j++)
sum[idx][j] += Y[i][j];
}
void update(int S, int E) {
const int Sidx = getIdx(S), Eidx = getIdx(E);
if(Sidx == Eidx) {
for(int i = S; i <= E; i++) rotY(i);
updBuc(Sidx);
} else {
for(int i = Sidx+1; i < Eidx; i++) sumidx[i]++;
for(int i = getEidx(Sidx); S <= i; i--) rotY(i);
for(int i = getSidx(Eidx); i <= E; i++) rotY(i);
updBuc(Sidx); updBuc(Eidx);
}
}
void __insert(int X, int R, int K) {
for(int i = 0; i < 30; R /= K, i++) Y[X][i] = R;
}
void insert(int X, int R, int K) {
updBuc(getIdx(X));
__insert(X, R, K);
updBuc(getIdx(X));
}
void __updateall(int N) {
for(int i = getIdx(N); i; i--) updBuc(i);
}
ll getSum(int S, int E) {
const int Sidx = getIdx(S), Eidx = getIdx(E);
ll ret = 0;
if(Sidx == Eidx) {
updBuc(Sidx);
for(int i = S; i <= E; i++) ret += Y[i][0];
} else {
updBuc(Sidx); updBuc(Eidx);
for(int i = Sidx+1; i < Eidx; i++) ret += sum[i][sumidx[i]];
for(int i = getEidx(Sidx); S <= i; i--) ret += Y[i][0];
for(int i = getSidx(Eidx); i <= E; i++) ret += Y[i][0];
}
return ret;
}
};
struct BIT {
ll d[MAXN], v[MAXN];
void _upd(int i, ll r) { for(; i < MAXN; i += rb(i)) d[i] += r; }
void upd(int i, int r) { _upd(i, (ll)r-v[i]); v[i] = r; }
ll get(int i) {
ll r = 0; for(; i; i -= rb(i)) r += d[i];
return r;
}
ll get(int s, int e) { return get(e) - get(s-1); }
};
BUC BT;
BIT ST;
int N, Q, K;
int main() {
scanf("%d%d%d", &N, &Q, &K);
for(int i = 1, c; i <= N; i++) {
scanf("%d", &c);
if(1 == K) ST.upd(i, c);
else BT.__insert(i, c, K);
}
if(1 != K) BT.__updateall(N);
for(int type, a, b; Q--;) {
scanf("%d%d%d", &type, &a, &b);
if(1 == type) {
if(1 == K) ST.upd(a, b);
else BT.insert(a, b, K);
} else if(2 == type) {
if(1 != K) BT.update(a, b);
} else {
printf("%lld\n", (1 == K) ? ST.get(a, b) : BT.getSum(a, b));
}
}
return 0;
}
Compilation message
In file included from /usr/include/c++/5/unordered_map:35:0,
from sterilizing.cpp:13:
/usr/include/c++/5/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
#error This file requires compiler and library support \
^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:109:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &Q, &K);
^
sterilizing.cpp:111:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c);
^
sterilizing.cpp:117:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &type, &a, &b);
^
