Untitled
unknown
plain_text
a year ago
3.3 kB
19
Indexable
class UserSolution {
int K, T;
int a[][] = new int[500][500];
int aMax[] = new int[500];
int aMin[] = new int[500];
int aSum[] = new int[500];
public void init(int N, int mSubscriber[]) {
for (K = 2; K * K <= N; K++)
;
T = N % K > 0 ? N / K + 1 : N / K;
for (int i = 0; i < T; i++) {
aMax[i] = -1;
aMin[i] = (int) 1e9;
aSum[i] = 0;
}
for (int i = 0; i < N; i++) {
int iT = i / K;
int iK = i % K;
a[iT][iK] = mSubscriber[i];
aSum[iT] += mSubscriber[i];
aMax[iT] = Math.max(aMax[iT], mSubscriber[i]);
aMin[iT] = Math.min(aMin[iT], mSubscriber[i]);
}
return;
}
int update(int i, int num) {
int iT = i / K;
int iK = i % K;
a[iT][iK] += num;
aSum[iT] += num;
aMax[iT] = -1;
aMin[iT] = (int) 1e9;
for (int j = 0; j < K; j++) {
aMax[iT] = Math.max(aMax[iT], a[iT][j]);
aMin[iT] = Math.min(aMin[iT], a[iT][j]);
}
return a[iT][iK];
}
public int subscribe(int mId, int mNum) {
return update(mId - 1, mNum);
}
public int unsubscribe(int mId, int mNum) {
return update(mId - 1, -mNum);
}
public int count(int sId, int eId) {
int x = sId - 1;
int y = eId - 1;
int sum = 0;
int itx = x / K;
int ity = y / K;
int ikx = x % K;
int iky = y % K;
for (int i = ikx; i < K; i++) {
sum += a[itx][i];
}
for (int i = itx + 1; i < ity; i++) {
sum += aSum[i];
}
for (int i = 0; i <= iky; i++) {
sum += a[ity][i];
}
return sum;
}
public int calculate(int sId, int eId) {
int x = sId - 1;
int y = eId - 1;
int max = -1;
int min = (int) 1e9;
int itx = x / K;
int ity = y / K;
int ikx = x % K;
int iky = y % K;
for (int i = ikx; i < K; i++) {
max = Math.max(max, a[itx][i]);
min = Math.min(min, a[itx][i]);
}
for (int i = itx + 1; i < ity; i++) {
max = Math.max(max, aMax[i]);
min = Math.min(min, aMin[i]);
}
for (int i = 0; i <= iky; i++) {
max = Math.max(max, a[ity][i]);
min = Math.min(min, a[ity][i]);
}
return max - min;
}
}Editor is loading...
Leave a Comment