#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 500003 , L = 70;
struct Seg {
int siz;
vector<ll> sum;
ll Nutral = 1;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
siz *= 2;
sum.resize(siz * 2 , Nutral);
}
void build(vector<int>& a , int x, int lx , int rx){
if(rx - lx == 1){
if(lx < (int)a.size())sum[x] = a[lx];
return;
}
int m = (lx + rx)/2;
build(a , 2 * x + 1 , lx , m);
build(a , 2 * x + 2 , m , rx);
sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
}
void build(vector<int>& a){
return build(a , 0 , 0 , siz);
}
void set(int i , int v ,int x , int lx , int rx){
if(rx - lx == 1){
sum[x] = v;
return;
}
int m = (lx + rx)/2;
if(i < m){
set(i , v , 2 * x + 1 , lx , m);
}
else set(i , v , 2 * x + 2 , m , rx);
sum[x] = (sum[2 * x + 1] * sum[2 * x + 2])%mod;
}
void set(int i , int v){
set(i , v , 0 , 0 , siz);
}
int sums(int l , int r , int x , int lx , int rx){
if(l >= rx || r <= lx)return Nutral;
if(lx >= l && rx <= r)return sum[x];
int m = (lx + rx)/2;
return (sums(l , r , 2 * x + 1 , lx , m) * sums(l , r , 2 * x +2 , m , rx))%mod;
}
int sums(int l , int r){
return sums(l , r , 0 , 0 , siz);
}
};
struct SegMX {
vector<ll> v;
int siz;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
v.assign(siz * 2 , 0);
}
void build(vector<int>& a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < a.size()){
v[x] = a[lx];
}
return;
}
int m = (lx + rx)/2;
build(a , 2*x+1,lx,m);
build(a , 2 * x + 2 , m , rx);
v[x] = max(v[2 * x + 1] , v[2*x+2]);
}
void build(vector<int>& a){
buld(a , 0 , 0 , siz);
}
void set(int i , int val , int x , int lx, int rx){
if(rx - lx == 1){
v[x] = val;
return;
}
int m = (lx + rx)/2;
if(i < m){
set(i , val ,2 * x + 1 , lx ,m);
}
else {
set(i , val , 2 * x + 2, m , rx);
}
v[x] = max(v[2*x+1] , v[2*x+2]);
}
void set(int i , int val){
set(i , val , 0 , 0, siz);
}
ll find(int l , int r , int x , int lx, int rx){
if(lx >= r || l >= rx)return 0;
if(lx >= l && rx <= r)return v[x];
int m = (lx + rx)/2;
return max(find(l,r,2*x+1,lx,m),find(l , r , 2 * x + 2 , m ,rx));
}
ll find(int l , int r){
return find(l , r , 0 , 0 , siz);
}
};
int n;
vector<int> x,y;
set<int> s,s1;
SegMX st;
Seg st_sum;
vector<pair<int,ll>> last;
int cal(){
int pos = -1;
ll multi = 1;
if(v.size() < L){
int right = n;
auto it = s.upper_bound(0);
if(it != s.end()){
right = *it;
}
cur = st.find(0,right);
if(v.size()){
int idx = v[0].vf;
if(x[idx] * v[0].vs >= cur){
pos = 0;
}
else {
multi *= x[idx];
}
}
}
for(int i = 1; i < v.size(); i++){
int idx = v[i].vf;
if(multi >= 1e9){
pos = i;
multi = 1;
}
else {
if(x[idx] * v[i].vs >= v[i-1].vs){
pos = i;
}
else {
multi *= x[idx];
}
}
}
return (st_sum(x[v[pos].vf] + 1) * v[pos].vs) % mod;
}
int init(int n1 , vector<int> x1 , vector<int> y1){
n = n1;
x = x1;
y = y1;
s.insert(0);
for(int i = 0; i < n; i++){
if(x[i] > 1){
s.insert(i);
}
}
st.init(n + 1);
st.build(y);
st_sum.init(n + 1);
st_sum.build(y);
for(int i = n - 1; i >= 0 && v.size() < L; i--){
if(x[i] > 1){
auto it = s.upper_bound(i);
int right = i;
if(it == s.end()){
right = n;
}
else right = (*it);
v.pb(mp(i,st.find(i,right)));
}
}
reverse(all(v));
return cal();
}
int updateX(int pos , int val){
pos--;
int toerase = -1;
for(int i = 0; i < v.size() && val == 1; i++){
if(x[v[i].vf] == pos){
toerase = i;
break;
}
}
if(toerase != -1){
v.erase(v.begin()+toerase);
s.erase(toerase);
if(v.size()){
auto it = s.lower_bound(toerase);
if(it != s.begin()){
auto it1 = it;
it--;
vector<pair<int,ll>> v1;
v1.pb(mp(*it,st.find(*it,*it1)));
for(auto tp : v){
v1.pb(tp);
}
v = v1;
}
}
}
else {
if(val == 1 && s.find(pos)!=s.end()){
return cal();
}
if(val > 1)s.insert(pos);
if(v.size() == 0 || pos > x[v[0].vf]){
v.erase(v.begin());
auto it = s.upper_bound(pos);
int right = n;
if(it!=s.end()){
right = *it;
}
v.pb(mp(pos , st.find(pos , right)));
}
}
st_sum.set(pos , val);
return cal();
}
int updateY(int pos , int val){
pos--;
st.set(pos , val);
if(v.size() && ix[v[0].vf] <= pos){
int cur = 0;
for(int i = 0; i < v.size() && x[v[i].vf] <= pos; i++){
cur = i;
}
int right = n;
if(cur + 1 < v.size()){
right = x[v[cur+1].vf];
v[cur].vs = st.find(x[v[i].vf] , right);
}
}
return cal();
}
void solve(){
int n;
cin >> n;
vector<int> a, b;
for(int i = 0; i < n; i++){
int x;
cin >> x;
a.pb(x);
}
for(int i = 0; i < n; i++){
int x;
cin >> x;
b.pb(x);
}
int m;
cin >> m;
cout << init(n , a , b) << '\n';
while(m--){
int t;
cin >> t;
int pos , val;
cin >> pos >> val;
if(t == 1){
cout<< updateX(pos , val) << '\n';
}
else cout << updateY(pos , val) << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}
Compilation message
horses.cpp: In member function 'int Seg::sums(int, int, int, int, int)':
horses.cpp:62:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
62 | if(l >= rx || r <= lx)return Nutral;
| ^~~~~~
horses.cpp:63:37: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
63 | if(lx >= l && rx <= r)return sum[x];
| ^
horses.cpp: In member function 'void SegMX::build(std::vector<int>&, int, int, int)':
horses.cpp:86:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if(lx < a.size()){
| ~~~^~~~~~~~~~
horses.cpp: In member function 'void SegMX::build(std::vector<int>&)':
horses.cpp:98:3: error: 'buld' was not declared in this scope; did you mean 'build'?
98 | buld(a , 0 , 0 , siz);
| ^~~~
| build
horses.cpp: In function 'int cal()':
horses.cpp:142:5: error: 'v' was not declared in this scope
142 | if(v.size() < L){
| ^
horses.cpp:148:3: error: 'cur' was not declared in this scope
148 | cur = st.find(0,right);
| ^~~
horses.cpp:159:21: error: 'v' was not declared in this scope
159 | for(int i = 1; i < v.size(); i++){
| ^
horses.cpp:161:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
161 | if(multi >= 1e9){
| ^~~~~
horses.cpp:174:19: error: 'v' was not declared in this scope
174 | return (st_sum(x[v[pos].vf] + 1) * v[pos].vs) % mod;
| ^
horses.cpp: In function 'int init(int, std::vector<int>, std::vector<int>)':
horses.cpp:194:31: error: 'v' was not declared in this scope
194 | for(int i = n - 1; i >= 0 && v.size() < L; i--){
| ^
horses.cpp:207:14: error: 'v' was not declared in this scope
207 | reverse(all(v));
| ^
horses.cpp:6:16: note: in definition of macro 'all'
6 | #define all(x) x.begin(),x.end()
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:215:21: error: 'v' was not declared in this scope
215 | for(int i = 0; i < v.size() && val == 1; i++){
| ^
horses.cpp:222:3: error: 'v' was not declared in this scope
222 | v.erase(v.begin()+toerase);
| ^
horses.cpp:243:6: error: 'v' was not declared in this scope
243 | if(v.size() == 0 || pos > x[v[0].vf]){
| ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:261:5: error: 'v' was not declared in this scope
261 | if(v.size() && ix[v[0].vf] <= pos){
| ^
horses.cpp:261:17: error: 'ix' was not declared in this scope; did you mean 'x'?
261 | if(v.size() && ix[v[0].vf] <= pos){
| ^~
| x
horses.cpp:269:28: error: 'i' was not declared in this scope
269 | v[cur].vs = st.find(x[v[i].vf] , right);
| ^
horses.cpp: In function 'void solve()':
horses.cpp:277:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
277 | int n;
| ^
horses.cpp:132:5: note: shadowed declaration is here
132 | int n;
| ^
horses.cpp:281:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
281 | int x;
| ^
horses.cpp:133:13: note: shadowed declaration is here
133 | vector<int> x,y;
| ^
horses.cpp:286:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
286 | int x;
| ^
horses.cpp:133:13: note: shadowed declaration is here
133 | vector<int> x,y;
| ^
