### [problem:1316A]↵
↵
**Author:** [user:gaurav172,2020-03-04] ↵
**Development:** [user:gaurav172,2020-03-04], [user:ishita_3110,2020-03-04], [user:night_fury208,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316A]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
int main()↵
{↵
ll test;↵
cin>>test;↵
while(test--)↵
{↵
ll n,m;↵
cin>>n>>m;↵
ll s=0;↵
for(ll i=1;i<=n;i++)↵
{↵
ll x;↵
cin>>x;↵
s=s+x;↵
}↵
cout<<min(s,m)<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316B]↵
↵
**Author:** [user:preet_t,2020-03-04] ↵
**Development:** [user:preet_t,2020-03-04], [user:shaanknight,2020-03-04], [user:night_fury208,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316B]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
string modified(string& s, int n, int k) {↵
string result_prefix = s.substr(k - 1, n - k + 1);↵
string result_suffix = s.substr(0, k - 1);↵
if (n % 2 == k % 2)↵
reverse(result_suffix.begin(), result_suffix.end());↵
return result_prefix + result_suffix;↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
string s, best_s, temp;↵
int t, n, best_k;↵
cin >> t;↵
while (t--) {↵
cin >> n >> s;↵
best_s = modified(s, n, 1);↵
best_k = 1;↵
for (int k = 2; k <= n; ++k) {↵
temp = modified(s, n, k);↵
if (temp < best_s) {↵
best_s = temp;↵
best_k = k;↵
}↵
}↵
cout << best_s << '\n' << best_k << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316C]↵
↵
**Author:** [user:naruhodou,2020-03-04] ↵
**Development:** [user:naruhodou,2020-03-04], [user:shaanknight,2020-03-04],[user:ishita_3110,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long int↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);cout.tie(0);↵
↵
ll n,i,m,x,a,p,fir,sec;↵
↵
cin >> n >> m >> p;↵
a=0;↵
for(i=0;i<n;i++)↵
{↵
cin >> x;↵
if(x%p && !a)↵
{↵
a=1;↵
fir=i;↵
}↵
}↵
a=0;↵
for(i=0;i<m;i++)↵
{↵
cin >> x;↵
if(x%p && !a)↵
{↵
a=1;↵
sec=i;↵
}↵
}↵
cout << fir+sec << endl;↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316D]↵
↵
**Author:** [user:shaanknight,2020-03-04] ↵
**Development:** [user:shaanknight,2020-03-04], [user:riz_1_,2020-03-04], [user:coder_h,2020-03-04],[user:Altitude,2020-03-04] ↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int M = (1<<10)+5;↵
char mat[M][M];↵
int x[M][M],y[M][M];↵
int n;↵
↵
bool connect(int p,int q,int r,int s,char d1,char d2)↵
{↵
if(x[r][s] == -1)↵
{↵
mat[p][q] = d1;↵
if(mat[r][s] == '\0') mat[r][s] = d2;↵
return 1;↵
}↵
else↵
return 0;↵
}↵
↵
void dfs(int p,int q,char d)↵
{↵
if(mat[p][q] != '\0') return;↵
mat[p][q] = d;↵
↵
if(x[p][q] == x[p+1][q] && y[p][q] == y[p+1][q])↵
dfs(p+1,q,'U');↵
if(x[p][q] == x[p-1][q] && y[p][q] == y[p-1][q])↵
dfs(p-1,q,'D');↵
if(x[p][q] == x[p][q+1] && y[p][q] == y[p][q+1])↵
dfs(p,q+1,'L');↵
if(x[p][q] == x[p][q-1] && y[p][q] == y[p][q-1])↵
dfs(p,q-1,'R');↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int i,j;↵
↵
cin >> n;↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
cin >> x[i][j] >> y[i][j];↵
}↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
if(x[i][j] == -1)↵
{↵
bool res = (mat[i][j] != '\0');↵
if(res == 0) res = connect(i,j,i+1,j,'D','U');↵
if(res == 0) res = connect(i,j,i,j+1,'R','L');↵
if(res == 0) res = connect(i,j,i-1,j,'U','D');↵
if(res == 0) res = connect(i,j,i,j-1,'L','R');↵
if(res == 0)↵
{↵
cout << "INVALID" << "\n";↵
return 0;↵
}↵
}↵
else if(x[i][j] == i && y[i][j] == j)↵
dfs(i,j,'X');↵
}↵
}↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
if(mat[i][j] == '\0')↵
{↵
cout << "INVALID" << "\n";↵
return 0;↵
}↵
} ↵
}↵
↵
cout << "VALID" << "\n";↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
cout << mat[i][j];↵
} ↵
cout << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316E]↵
↵
**Author:** [user:gaurav172,2020-03-04] ↵
**Development:** [user:gaurav172,2020-03-04], [user:shaanknight,2020-03-04], [user:coder_h,2020-03-04], [user:madlad,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316E]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
const ll M=1e5+5;↵
ll dp[M][(1<<7)+1],skill[M][7];↵
ll ind[M],a[M];↵
bool cmp(ll p,ll q)↵
{↵
return a[p]>a[q];↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
ll n,p,k;↵
cin>>n>>p>>k;↵
memset(dp,-1,sizeof(dp));↵
for(ll i=1;i<=n;i++)↵
cin>>a[i];↵
for(ll i=1;i<=n;i++)↵
for(ll j=0;j<p;j++)↵
cin>>skill[i][j];↵
for(ll i=1;i<=n;i++)↵
ind[i]=i;↵
sort(ind+1,ind+n+1,cmp); ↵
dp[0][0]=0;↵
for(ll i=1;i<=n;i++)↵
{↵
ll x=ind[i];↵
for(ll mask=0;mask<(1<<p);mask++)↵
{↵
ll ct=0;↵
for(ll j=0;j<p;j++)↵
if((mask&(1<<j)))↵
ct++;↵
ll z=(i-1)-ct;↵
if(z<k)↵
{↵
if(dp[i-1][mask]!=-1)↵
dp[i][mask]=dp[i-1][mask]+a[x];↵
}↵
else↵
{↵
if(dp[i-1][mask]!=-1)↵
dp[i][mask]=dp[i-1][mask];↵
}↵
for(ll j=0;j<p;j++)↵
{↵
if((mask&(1<<j)) && dp[i-1][(mask^(1<<j))]!=-1)↵
{↵
ll z=dp[i-1][(mask^(1<<j))]+skill[x][j];↵
if(z>dp[i][mask])↵
dp[i][mask]=z;↵
}↵
}↵
}↵
}↵
cout<<dp[n][(1<<p)-1]<<"\n";↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316F]↵
↵
**Author:** [user:gaurav172,2020-03-05] ↵
**Testers:** [user:gaurav172,2020-03-05], [user:shaanknight,2020-03-05]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316EF]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define ff first↵
#define ss second↵
#define pb push_back↵
#define all(a) a.begin(),a.end()↵
#define sz(a) (ll)(a.size())↵
const ll M=6e5+6;↵
const ll mod=1e9+7;↵
ll val[4*M],lt[4*M],rt[4*M];↵
int no[4*M];↵
ll pw[M],ipw[M];↵
int P[M],idx[M],qr[M],n,q;↵
vector<pair<int,int> > v;↵
ll power(ll a,ll b)↵
{↵
ll val=1;↵
while(b)↵
{↵
if(b%2)↵
val=(val*a)%mod;↵
b/=2;↵
a=(a*a)%mod;↵
}↵
return val;↵
}↵
void build(int i,int s,int e)↵
{↵
if(s==e)↵
{↵
if(v[s].ss>n)↵
return;↵
val[i]=0;↵
lt[i]=v[s].ff;↵
rt[i]=(v[s].ff*ipw[1])%mod;↵
no[i]=1;↵
return;↵
}↵
int m=(s+e)/2;↵
int lc=2*i,rc=2*i+1;↵
build(lc,s,m);↵
build(rc,m+1,e);↵
ll tp=(ipw[no[lc]]*rt[rc])%mod;↵
tp=(tp*lt[lc])%mod;↵
val[i]=(val[lc]+val[rc]+tp)%mod;↵
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;↵
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;↵
no[i]=(no[lc]+no[rc]);↵
}↵
void update(int i,int s,int e,int x,int y)↵
{↵
if(s==e)↵
{↵
if(y==-1)↵
{↵
val[i]=0;↵
lt[i]=0;↵
rt[i]=0;↵
no[i]=0;↵
}↵
else↵
{↵
val[i]=0;↵
lt[i]=v[s].ff;↵
rt[i]=(v[s].ff*ipw[1])%mod;↵
no[i]=1;↵
}↵
return;↵
}↵
int m=(s+e)/2;↵
int lc=(i<<1),rc=(lc|1);↵
if(x<=m)↵
update(lc,s,m,x,y);↵
else↵
update(rc,m+1,e,x,y);↵
ll tp=(ipw[no[lc]]*rt[rc])%mod;↵
tp=(tp*lt[lc])%mod;↵
val[i]=(val[lc]+val[rc]+tp)%mod;↵
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;↵
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;↵
no[i]=(no[lc]+no[rc]);↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
pw[0]=1;↵
ipw[0]=1;↵
ll inv=power(2,mod-2);↵
for(int i=1;i<M;i++)↵
{↵
pw[i]=(pw[i-1]*2)%mod;↵
ipw[i]=(ipw[i-1]*inv)%mod;↵
}↵
cin>>n;↵
v.pb({-1LL,-1});↵
for(int i=1;i<=n;i++)↵
{↵
cin>>P[i];↵
v.pb({P[i],i});↵
}↵
cin>>q;↵
for(int i=1;i<=q;i++)↵
{↵
cin>>idx[i]>>qr[i];↵
v.pb({qr[i],n+i});↵
}↵
sort(all(v));↵
std::vector<int> pos(n+q+1,0);↵
for(int i=1;i<sz(v);i++)↵
pos[v[i].ss]=i;↵
build(1,1,n+q);↵
cout<<val[1]<<"\n";↵
for(int i=1;i<=q;i++)↵
{↵
update(1,1,n+q,pos[idx[i]],-1);↵
pos[idx[i]]=pos[n+i];↵
update(1,1,n+q,pos[idx[i]],1);↵
cout<<val[1]<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
**Author:** [user:gaurav172,2020-03-04] ↵
**Development:** [user:gaurav172,2020-03-04], [user:ishita_3110,2020-03-04], [user:night_fury208,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316A]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
int main()↵
{↵
ll test;↵
cin>>test;↵
while(test--)↵
{↵
ll n,m;↵
cin>>n>>m;↵
ll s=0;↵
for(ll i=1;i<=n;i++)↵
{↵
ll x;↵
cin>>x;↵
s=s+x;↵
}↵
cout<<min(s,m)<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316B]↵
↵
**Author:** [user:preet_t,2020-03-04] ↵
**Development:** [user:preet_t,2020-03-04], [user:shaanknight,2020-03-04], [user:night_fury208,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316B]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
string modified(string& s, int n, int k) {↵
string result_prefix = s.substr(k - 1, n - k + 1);↵
string result_suffix = s.substr(0, k - 1);↵
if (n % 2 == k % 2)↵
reverse(result_suffix.begin(), result_suffix.end());↵
return result_prefix + result_suffix;↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
string s, best_s, temp;↵
int t, n, best_k;↵
cin >> t;↵
while (t--) {↵
cin >> n >> s;↵
best_s = modified(s, n, 1);↵
best_k = 1;↵
for (int k = 2; k <= n; ++k) {↵
temp = modified(s, n, k);↵
if (temp < best_s) {↵
best_s = temp;↵
best_k = k;↵
}↵
}↵
cout << best_s << '\n' << best_k << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316C]↵
↵
**Author:** [user:naruhodou,2020-03-04] ↵
**Development:** [user:naruhodou,2020-03-04], [user:shaanknight,2020-03-04],[user:ishita_3110,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long int↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);cout.tie(0);↵
↵
ll n,i,m,x,a,p,fir,sec;↵
↵
cin >> n >> m >> p;↵
a=0;↵
for(i=0;i<n;i++)↵
{↵
cin >> x;↵
if(x%p && !a)↵
{↵
a=1;↵
fir=i;↵
}↵
}↵
a=0;↵
for(i=0;i<m;i++)↵
{↵
cin >> x;↵
if(x%p && !a)↵
{↵
a=1;↵
sec=i;↵
}↵
}↵
cout << fir+sec << endl;↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316D]↵
↵
**Author:** [user:shaanknight,2020-03-04] ↵
**Development:** [user:shaanknight,2020-03-04], [user:riz_1_,2020-03-04], [user:coder_h,2020-03-04],[user:Altitude,2020-03-04] ↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int M = (1<<10)+5;↵
char mat[M][M];↵
int x[M][M],y[M][M];↵
int n;↵
↵
bool connect(int p,int q,int r,int s,char d1,char d2)↵
{↵
if(x[r][s] == -1)↵
{↵
mat[p][q] = d1;↵
if(mat[r][s] == '\0') mat[r][s] = d2;↵
return 1;↵
}↵
else↵
return 0;↵
}↵
↵
void dfs(int p,int q,char d)↵
{↵
if(mat[p][q] != '\0') return;↵
mat[p][q] = d;↵
↵
if(x[p][q] == x[p+1][q] && y[p][q] == y[p+1][q])↵
dfs(p+1,q,'U');↵
if(x[p][q] == x[p-1][q] && y[p][q] == y[p-1][q])↵
dfs(p-1,q,'D');↵
if(x[p][q] == x[p][q+1] && y[p][q] == y[p][q+1])↵
dfs(p,q+1,'L');↵
if(x[p][q] == x[p][q-1] && y[p][q] == y[p][q-1])↵
dfs(p,q-1,'R');↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
int i,j;↵
↵
cin >> n;↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
cin >> x[i][j] >> y[i][j];↵
}↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
if(x[i][j] == -1)↵
{↵
bool res = (mat[i][j] != '\0');↵
if(res == 0) res = connect(i,j,i+1,j,'D','U');↵
if(res == 0) res = connect(i,j,i,j+1,'R','L');↵
if(res == 0) res = connect(i,j,i-1,j,'U','D');↵
if(res == 0) res = connect(i,j,i,j-1,'L','R');↵
if(res == 0)↵
{↵
cout << "INVALID" << "\n";↵
return 0;↵
}↵
}↵
else if(x[i][j] == i && y[i][j] == j)↵
dfs(i,j,'X');↵
}↵
}↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
if(mat[i][j] == '\0')↵
{↵
cout << "INVALID" << "\n";↵
return 0;↵
}↵
} ↵
}↵
↵
cout << "VALID" << "\n";↵
↵
for(i=1;i<=n;++i)↵
{↵
for(j=1;j<=n;++j)↵
{↵
cout << mat[i][j];↵
} ↵
cout << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316E]↵
↵
**Author:** [user:gaurav172,2020-03-04] ↵
**Development:** [user:gaurav172,2020-03-04], [user:shaanknight,2020-03-04], [user:coder_h,2020-03-04], [user:madlad,2020-03-04]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316E]↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
const ll M=1e5+5;↵
ll dp[M][(1<<7)+1],skill[M][7];↵
ll ind[M],a[M];↵
bool cmp(ll p,ll q)↵
{↵
return a[p]>a[q];↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
ll n,p,k;↵
cin>>n>>p>>k;↵
memset(dp,-1,sizeof(dp));↵
for(ll i=1;i<=n;i++)↵
cin>>a[i];↵
for(ll i=1;i<=n;i++)↵
for(ll j=0;j<p;j++)↵
cin>>skill[i][j];↵
for(ll i=1;i<=n;i++)↵
ind[i]=i;↵
sort(ind+1,ind+n+1,cmp); ↵
dp[0][0]=0;↵
for(ll i=1;i<=n;i++)↵
{↵
ll x=ind[i];↵
for(ll mask=0;mask<(1<<p);mask++)↵
{↵
ll ct=0;↵
for(ll j=0;j<p;j++)↵
if((mask&(1<<j)))↵
ct++;↵
ll z=(i-1)-ct;↵
if(z<k)↵
{↵
if(dp[i-1][mask]!=-1)↵
dp[i][mask]=dp[i-1][mask]+a[x];↵
}↵
else↵
{↵
if(dp[i-1][mask]!=-1)↵
dp[i][mask]=dp[i-1][mask];↵
}↵
for(ll j=0;j<p;j++)↵
{↵
if((mask&(1<<j)) && dp[i-1][(mask^(1<<j))]!=-1)↵
{↵
ll z=dp[i-1][(mask^(1<<j))]+skill[x][j];↵
if(z>dp[i][mask])↵
dp[i][mask]=z;↵
}↵
}↵
}↵
}↵
cout<<dp[n][(1<<p)-1]<<"\n";↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
###[problem:1316F]↵
↵
**Author:** [user:gaurav172,2020-03-05] ↵
**Testers:** [user:gaurav172,2020-03-05], [user:shaanknight,2020-03-05]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1316
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define ff first↵
#define ss second↵
#define pb push_back↵
#define all(a) a.begin(),a.end()↵
#define sz(a) (ll)(a.size())↵
const ll M=6e5+6;↵
const ll mod=1e9+7;↵
ll val[4*M],lt[4*M],rt[4*M];↵
int no[4*M];↵
ll pw[M],ipw[M];↵
int P[M],idx[M],qr[M],n,q;↵
vector<pair<int,int> > v;↵
ll power(ll a,ll b)↵
{↵
ll val=1;↵
while(b)↵
{↵
if(b%2)↵
val=(val*a)%mod;↵
b/=2;↵
a=(a*a)%mod;↵
}↵
return val;↵
}↵
void build(int i,int s,int e)↵
{↵
if(s==e)↵
{↵
if(v[s].ss>n)↵
return;↵
val[i]=0;↵
lt[i]=v[s].ff;↵
rt[i]=(v[s].ff*ipw[1])%mod;↵
no[i]=1;↵
return;↵
}↵
int m=(s+e)/2;↵
int lc=2*i,rc=2*i+1;↵
build(lc,s,m);↵
build(rc,m+1,e);↵
ll tp=(ipw[no[lc]]*rt[rc])%mod;↵
tp=(tp*lt[lc])%mod;↵
val[i]=(val[lc]+val[rc]+tp)%mod;↵
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;↵
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;↵
no[i]=(no[lc]+no[rc]);↵
}↵
void update(int i,int s,int e,int x,int y)↵
{↵
if(s==e)↵
{↵
if(y==-1)↵
{↵
val[i]=0;↵
lt[i]=0;↵
rt[i]=0;↵
no[i]=0;↵
}↵
else↵
{↵
val[i]=0;↵
lt[i]=v[s].ff;↵
rt[i]=(v[s].ff*ipw[1])%mod;↵
no[i]=1;↵
}↵
return;↵
}↵
int m=(s+e)/2;↵
int lc=(i<<1),rc=(lc|1);↵
if(x<=m)↵
update(lc,s,m,x,y);↵
else↵
update(rc,m+1,e,x,y);↵
ll tp=(ipw[no[lc]]*rt[rc])%mod;↵
tp=(tp*lt[lc])%mod;↵
val[i]=(val[lc]+val[rc]+tp)%mod;↵
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;↵
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;↵
no[i]=(no[lc]+no[rc]);↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
pw[0]=1;↵
ipw[0]=1;↵
ll inv=power(2,mod-2);↵
for(int i=1;i<M;i++)↵
{↵
pw[i]=(pw[i-1]*2)%mod;↵
ipw[i]=(ipw[i-1]*inv)%mod;↵
}↵
cin>>n;↵
v.pb({-1LL,-1});↵
for(int i=1;i<=n;i++)↵
{↵
cin>>P[i];↵
v.pb({P[i],i});↵
}↵
cin>>q;↵
for(int i=1;i<=q;i++)↵
{↵
cin>>idx[i]>>qr[i];↵
v.pb({qr[i],n+i});↵
}↵
sort(all(v));↵
std::vector<int> pos(n+q+1,0);↵
for(int i=1;i<sz(v);i++)↵
pos[v[i].ss]=i;↵
build(1,1,n+q);↵
cout<<val[1]<<"\n";↵
for(int i=1;i<=q;i++)↵
{↵
update(1,1,n+q,pos[idx[i]],-1);↵
pos[idx[i]]=pos[n+i];↵
update(1,1,n+q,pos[idx[i]],1);↵
cout<<val[1]<<"\n";↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
