Untitled
unknown
plain_text
a month ago
3.3 kB
3
Indexable
Never
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; } }
Leave a Comment