結果

問題 No.1394 Changing Problems
ユーザー LayCurseLayCurse
提出日時 2021-02-12 23:02:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 20,632 bytes
コンパイル時間 4,508 ms
コンパイル使用メモリ 224,468 KB
実行使用メモリ 24,960 KB
最終ジャッジ日時 2024-07-20 00:26:48
合計ジャッジ時間 25,124 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 650 ms
24,832 KB
testcase_06 WA -
testcase_07 AC 2 ms
5,376 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 14 ms
5,376 KB
testcase_11 AC 15 ms
5,376 KB
testcase_12 AC 15 ms
5,376 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 1,000 ms
24,832 KB
testcase_17 AC 994 ms
24,960 KB
testcase_18 AC 1,007 ms
24,960 KB
testcase_19 AC 1,011 ms
24,832 KB
testcase_20 AC 999 ms
24,832 KB
testcase_21 AC 986 ms
24,704 KB
testcase_22 AC 1,000 ms
24,832 KB
testcase_23 AC 1,013 ms
24,832 KB
testcase_24 AC 996 ms
24,832 KB
testcase_25 AC 981 ms
24,832 KB
testcase_26 AC 445 ms
23,296 KB
testcase_27 AC 439 ms
23,296 KB
testcase_28 AC 442 ms
23,424 KB
testcase_29 AC 531 ms
24,320 KB
testcase_30 AC 527 ms
24,448 KB
testcase_31 AC 537 ms
24,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void*wmem;
char memarr[314572800];
template<class S, class T> inline S min_L(S a,T b){
return a<=b?a:b;
}
template<class S, class T> inline S max_L(S a,T b){
return a>=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
walloc1d(arr, x2-x1, mem);
(*arr) -= x1;
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline int rd_int(void){
int x;
rd(x);
return x;
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
template<class T, class S> T inline fDiv(T a, S b){
T m;
if(b < 0){
a = -a;
b = -b;
}
m = a % b;
if(m == 0){
return a / b;
}
if(m < 0){
m += b;
}
return (a - m) / b;
}
template<class S, class T> inline S moddw_L(S a, const T b){
a %= b;
if(a < 0){
a += b;
}
return a;
}
template<class S, class T> inline S chmin(S &a, T b){
if(a>b){
a=b;
}
return a;
}
template<class T> struct segtree{
int N;
int logN;
T*sum;
T*mn;
int*mnind;
T*fixval;
char*fixed;
T*addval;
void malloc(int maxN, int once = 0){
int i;
for(i=1;i<maxN;i*=2){
;
}
sum = new T[2*i];
mn = new T[2*i];
mnind = new int[2*i];
fixval = new T[i];
addval = new T[i];
fixed = new char[i];
if(once){
setN(maxN);
}
}
void walloc(int maxN, int once = 0, void **mem = &wmem){
int i;
for(i=1;i<maxN;i*=2){
;
}
walloc1d(&sum, 2*i, mem);
walloc1d(&mn, 2*i, mem);
walloc1d(&mnind, 2*i, mem);
walloc1d(&fixval, i, mem);
walloc1d(&addval, i, mem);
walloc1d(&fixed, i, mem);
if(once){
setN(maxN);
}
}
void free(void){
delete [] sum;
delete [] mn;
delete [] mnind;
delete [] fixval;
delete [] addval;
delete [] fixed;
}
T& operator[](int i){
return sum[N+i];
}
void setN(int n, int zerofill = 1, int dobuild = 1){
int i;
for(i=1,logN=0;i<n;i*=2,logN++){
;
}
N = i;
if(zerofill){
for(i=(0);i<(N);i++){
sum[N+i] = 0;
}
}
if(dobuild){
build();
}
}
void build(void){
int i;
for(i=(0);i<(N);i++){
mn[N+i] = sum[N+i];
mnind[N+i] = i;
}
for(i=N-1;i;i--){
sum[i] = sum[2*i] + sum[2*i+1];
if(mn[2*i] <= mn[2*i+1]){
mn[i] = mn[2*i];
mnind[i] = mnind[2*i];
}
else{
mn[i] = mn[2*i+1];
mnind[i] = mnind[2*i+1];
}
}
int XNa8avth = N;
for(i=(1);i<(XNa8avth);i++){
fixed[i] = 0;
}
int sMcf5Tpe = N;
for(i=(1);i<(sMcf5Tpe);i++){
addval[i] = 0;
}
}
inline void push_one(int a, int sz, int st){
if(fixed[a]){
if(sz > 1){
fixed[a*2] = fixed[a*2+1] = 1;
fixval[a*2] = fixval[a*2+1] = fixval[a];
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
else{
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
fixed[a] = 0;
addval[a] = 0;
return;
}
if(addval[a] != 0){
if(sz > 1){
if(fixed[a*2]){
fixval[a*2] += addval[a];
}
else{
addval[a*2] += addval[a];
}
if(fixed[a*2+1]){
fixval[a*2+1] += addval[a];
}
else{
addval[a*2+1] += addval[a];
}
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
else{
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
addval[a] = 0;
return;
}
}
inline void push(int a){
int i;
int aa = a - N;
int nd;
int sz;
int st;
for(i=logN;i;i--){
nd = a>>i;
sz = 1<<(i-1);
st = 2 * sz * (aa>>i);
push_one(nd, sz, st);
}
}
inline void build(int a){
int sz = 1;
int st = a - N;
while(a > 1){
if(a%2){
st += sz;
}
a /= 2;
sz *= 2;
if(fixed[a]){
sum[a] = sz * fixval[a];
mn[a] = fixval[a];
}
else{
sum[a] = sum[a*2] + sum[a*2+1];
if(mn[a*2] <= mn[a*2+1]){
mn[a] = mn[a*2];
mnind[a] = mnind[a*2];
}
else{
mn[a] = mn[a*2+1];
mnind[a] = mnind[a*2+1];
}
if(addval[a] != 0){
mn[a] += addval[a];
sum[a] += sz * addval[a];
}
}
}
}
inline void change(int a, int b, T val){
int sz = 1;
int aa;
int bb;
int st_a = a;
int st_b = b;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] = mn[a] = val;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
sum[b] = mn[b] = val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
fixed[a]=1;
fixval[a]=val;
sum[a] = sz * val;
mn[a] = val;
mnind[a] = st_a;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
fixed[b]=1;
fixval[b]=val;
sum[b] = sz * val;
mn[b] = val;
mnind[b] = st_b;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline void add(int a, int b, T val){
int sz = 1;
int aa;
int bb;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] += val;
mn[a] += val;
a++;
}
if(b%2){
b--;
sum[b] += val;
mn[b] += val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
if(fixed[a]){
fixval[a] += val;
}
else{
addval[a] += val;
}
sum[a] += sz * val;
mn[a] += val;
a++;
}
if(b%2){
b--;
if(fixed[b]){
fixval[b] += val;
}
else{
addval[b] += val;
}
sum[b] += sz * val;
mn[b] += val;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline pair<T,int> getMin(int a, int b){
pair<T,int> res;
pair<T,int> tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, make_pair(mn[a], mnind[a]));
}
else{
res = make_pair(mn[a], mnind[a]);
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(make_pair(mn[b], mnind[b]), tmp);
}
else{
tmp = make_pair(mn[b], mnind[b]);
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline T getMinVal(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, mn[a]);
}
else{
res = mn[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(mn[b], tmp);
}
else{
tmp = mn[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline int getMinInd(int a, int b){
return getMin(a,b).second;
}
inline T getSum(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res = res + sum[a];
}
else{
res = sum[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp = sum[b] + tmp;
}
else{
tmp = sum[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res = res + tmp;
return res;
}
return res;
}
}
;
template<class SVAL, class SFUN> struct segtree_rh{
int N;
int logN;
int trueN;
SVAL*val;
SFUN*fun;
char*dofun;
void malloc(int maxN, int once = 0);
void walloc(int maxN, int once = 0, void **mem = &wmem);
void free(void);
SVAL& operator[](int i);
void setN(int n, int zerofill = 1, int dobuild = 1);
void build(void);
inline void push_one(int a);
inline void push(int a);
inline void build(int a);
inline void change(int a, int b, SFUN f);
inline SVAL get(int a, int b);
template<bool (*f)(SVAL)> int max_right(int a, int mx);
template<bool (*f)(SVAL)> int max_right(int a);
template<bool (*f)(SVAL)> int min_left(int b, int mn);
template<bool (*f)(SVAL)> int min_left(int b);
}
;
long long segtree_rh_apply(long long f, long long a){
return a+f;
}
long long segtree_rh_merge(long long a, long long b){
return min_L(a, b);
}
long long segtree_rh_compose(long long f, long long g){
return f+g;
}
long long val;
bool f(long long a){
return a >= val;
}
int N;
int A[200000];
int Q;
int IND;
int X;
long long ds;
segtree<long long> ms;
segtree_rh<long long,long long> mms;
int main(){
int i, jZyWAPpY;
wmem = memarr;
rd(N);
{
int KL2GvlyY;
for(KL2GvlyY=(0);KL2GvlyY<(N);KL2GvlyY++){
rd(A[KL2GvlyY]);
}
}
if(N==1){
int cTE1_r3A;
int RZTsC2BF = rd_int();
for(cTE1_r3A=(0);cTE1_r3A<(RZTsC2BF);cTE1_r3A++){
rd(IND);
rd(X);
wt_L(X+1);
wt_L('\n');
}
return 0;
}
ms.walloc(N, 1);
mms.walloc(N);
mms.setN(N);
for(i=(0);i<(mms.N);i++){
mms[i] = 0;
}
mms.build();
for(i=(0);i<(N);i++){
A[i] = -(A[i] - (N-2));
}
for(i=(0);i<(N);i++){
ds += fDiv(A[i], N-1);
ms.add(0, N-1-((moddw_L(A[i],(N-1)))), 1);
mms.change(0, N-1-((moddw_L(A[i],(N-1)))), 1);
}
for(i=(0);i<(N);i++){
ms.add(i,i+1,-(N-i));
}
for(i=(0);i<(N);i++){
mms.change(i,i+1,-(N-i));
}
rd(Q);
for(jZyWAPpY=(0);jZyWAPpY<(Q);jZyWAPpY++){
long long res = 4611686016279904256LL;
long long tmp;
pair<long long,int> p;
rd(IND);IND += (-1);
rd(X);
ds -= fDiv(A[IND], N-1);
ms.add(0, N-1-((moddw_L(A[IND],(N-1)))), -1);
mms.change(0, N-1-((moddw_L(A[IND],(N-1)))), -1);
A[IND] = -(X - (N-2));
ds += fDiv(A[IND], N-1);
ms.add(0, N-1-((moddw_L(A[IND],(N-1)))), 1);
mms.change(0, N-1-((moddw_L(A[IND],(N-1)))), 1);
p = ms.getMin(0,N-1);
tmp = ds - p.first;
if(tmp > 0){
val = ds;
p.second = mms.max_right<f>(0);
}
chmin(res, p.second +max_L(-tmp, 0)* (N-1));
wt_L(res);
wt_L('\n');
}
return 0;
}
template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::malloc(int maxN, int once /*= 0*/){
int i;
for(i=1;i<maxN;i*=2){
;
}
val = new SVAL[2*i];
fun = new SFUN[i];
dofun = new char[i];
if(once){
setN(maxN);
}
}
template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::walloc(int maxN, int once /*= 0*/, void **mem /*= &wmem*/){
int i;
for(i=1;i<maxN;i*=2){
;
}
walloc1d(&val, 2*i, mem);
walloc1d(&fun, i, mem);
walloc1d(&dofun, i, mem);
if(once){
setN(maxN);
}
}
template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::free(void){
delete [] val;
delete [] fun;
}
template<class SVAL, class SFUN> SVAL& segtree_rh<SVAL, SFUN>::operator[](int i){
return val[N+i];
}
template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::setN(int n, int zerofill /*= 1*/, int dobuild /*= 1*/){
int i;
for(i=1,logN=0;i<n;i*=2,logN++){
;
}
trueN = n;
N = i;
if(dobuild){
build();
}
}
template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::build(void){
int i;
for(i=N-1;i;i--){
val[i] = segtree_rh_merge(val[2*i], val[2*i+1]);
}
int tDCakidn = N;
for(i=(1);i<(tDCakidn);i++){
dofun[i] = 0;
}
}
template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::push_one(int a){
if(dofun[a]){
if(2*a < N){
if(dofun[2*a]){
fun[2*a] = segtree_rh_compose(fun[a], fun[2*a]);
}
else{
fun[2*a] = fun[a];
dofun[2*a] = 1;
}
}
val[2*a] = segtree_rh_apply(fun[a], val[2*a]);
if(2*a+1 < N){
if(dofun[2*a+1]){
fun[2*a+1] = segtree_rh_compose(fun[a], fun[2*a+1]);
}
else{
fun[2*a+1] = fun[a];
dofun[2*a+1] = 1;
}
}
val[2*a+1] = segtree_rh_apply(fun[a], val[2*a+1]);
dofun[a] = 0;
}
}
template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::push(int a){
int i;
for(i=logN;i;i--){
push_one(a>>i);
}
}
template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::build(int a){
while(a > 1){
a /= 2;
val[a] = segtree_rh_merge(val[2*a], val[2*a+1]);
if(dofun[a]){
val[a] = segtree_rh_apply(fun[a], val[a]);
}
}
}
template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::change(int a, int b, SFUN f){
int aa;
int bb;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
val[a] = segtree_rh_apply(f, val[a]);
a++;
}
if(b%2){
b--;
val[b] = segtree_rh_apply(f, val[b]);
}
a /= 2;
b /= 2;
while(a < b){
if(a%2){
val[a] = segtree_rh_apply(f, val[a]);
if(dofun[a]){
fun[a] = segtree_rh_compose(f, fun[a]);
}
else{
fun[a] = f;
dofun[a] = 1;
}
a++;
}
if(b%2){
b--;
val[b] = segtree_rh_apply(f, val[b]);
if(dofun[b]){
fun[b] = segtree_rh_compose(f, fun[b]);
}
else{
fun[b] = f;
dofun[b] = 1;
}
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
template<class SVAL, class SFUN> inline SVAL segtree_rh<SVAL, SFUN>::get(int a, int b){
SVAL res;
SVAL tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res = segtree_rh_merge(res, val[a]);
}
else{
res = val[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp = segtree_rh_merge(val[b], tmp);
}
else{
tmp = val[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
return segtree_rh_merge(res, tmp);
}
return res;
}
template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::max_right(int a, int mx){
int fg = 0;
int ta = a;
int sz = 1;
SVAL cur;
SVAL tmp;
if(a>=mx){
return mx;
}
a += N;
push(a);
for(;;){
while(a%2==0){
a /= 2;
sz *= 2;
}
if(ta + sz <= mx){
if(fg==0){
tmp = val[a];
}
else{
tmp = segtree_rh_merge(cur, val[a]);
}
}
if(ta + sz > mx || !f(tmp)){
while(a < N){
push_one(a);
a *= 2;
sz /= 2;
if(ta + sz <= mx){
if(fg==0){
tmp = val[a];
}
else{
tmp = segtree_rh_merge(cur, val[a]);
}
}
if(ta + sz <= mx && f(tmp)){
fg = 1;
cur = tmp;
a++;
ta += sz;
}
}
return a - N;
}
fg = 1;
cur = tmp;
if((a & (a+1)) == 0){
break;
}
a++;
ta += sz;
}
return mx;
}
template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::max_right(int a){
return max_right<f>(a, trueN);
}
template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::min_left(int b, int mn){
int fg = 0;
int tb = b;
int sz = 1;
SVAL cur;
SVAL tmp;
if(b <= mn){
return mn;
}
b += N;
push(b-1);
for(;;){
while(b%2==0){
b /= 2;
sz *= 2;
}
if(tb - sz >= mn){
if(fg==0){
tmp = val[b-1];
}
else{
tmp = segtree_rh_merge(val[b-1], cur);
}
}
if(tb - sz < mn || !f(tmp)){
while(b-1 < N){
push_one(b-1);
b *= 2;
sz /= 2;
if(tb - sz >= mn){
if(fg==0){
tmp = val[b-1];
}
else{
tmp = segtree_rh_merge(val[b-1], cur);
}
}
if(tb - sz >= mn && f(tmp)){
fg = 1;
cur = tmp;
b--;
tb -= sz;
}
}
return b - N;
}
fg = 1;
cur = tmp;
b--;
tb -= sz;
if(tb <= mn){
break;
}
}
return mn;
}
template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::min_left(int b){
return min_left<f>(b, 0);
}
// cLay version 20210103-1 [bug fixed 2]
// --- original code ---
// //working_memory=300m
//
// ll segtree_rh_apply(ll f, ll a){ return a+f; }
// ll segtree_rh_merge(ll a, ll b){ return min(a, b); }
// ll segtree_rh_compose(ll f, ll g){ return f+g; }
//
// ll val;
// bool f(ll a){
// return a >= val;
// }
//
// int N, A[2d5], Q, IND, X;
// ll ds;
// segtree<ll> ms;
// segtree_rh<ll,ll> mms;
// {
// rd(N,A(N));
//
// if(N==1){
// REP(rd_int()){
// rd(IND,X);
// wt(X+1);
// }
// return 0;
// }
//
// ms.walloc(N, 1);
// mms.walloc(N);
// mms.setN(N);
// rep(i,mms.N) mms[i] = 0;
// mms.build();
//
// rep(i,N) A[i] = -(A[i] - (N-2));
// rep(i,N){
// ds += fDiv(A[i], N-1);
// ms.add(0, N-1-(A[i]%%(N-1)), 1);
// mms.change(0, N-1-(A[i]%%(N-1)), 1);
// }
// rep(i,N) ms.add(i,i+1,-(N-i));
// rep(i,N) mms.change(i,i+1,-(N-i));
//
// rd(Q);
// rep(Q){
// ll res = ll_inf, tmp;
// pair<ll,int> p;
// rd(IND--, X);
//
// ds -= fDiv(A[IND], N-1);
// ms.add(0, N-1-(A[IND]%%(N-1)), -1);
// mms.change(0, N-1-(A[IND]%%(N-1)), -1);
// A[IND] = -(X - (N-2));
// ds += fDiv(A[IND], N-1);
// ms.add(0, N-1-(A[IND]%%(N-1)), 1);
// mms.change(0, N-1-(A[IND]%%(N-1)), 1);
//
// p = ms.getMin(0,N-1);
// tmp = ds - p.first;
// if(tmp > 0){
// val = ds;
// p.second = mms.max_right<f>(0);
// }
// res <?= p.second + max(-tmp, 0) * (N-1);
// wt(res);
// }
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0