#include<bits/stdc++.h>
#define pii pair <int, int>
#define fr first
#define sc second
#define N 100010
#define inf 1e18
#define int long long
using namespace std;
int n;
int h[N], w[N];
int pref[N];
const int mod = 1e9+7;
struct Segtree{
pair <int,int> tree[4*N];
pair <int,int> join(pii a, pii b){
if(a.fr < b.fr) return a;
if(a.fr > b.fr) return b;
if(a.sc < b.sc) return a;
return b;
}
void build(int l, int r, int node){
if(l == r){
tree[node] = {h[l], l};
return;
}
int mid = (l+r)/2;
build(l, mid, 2*node);
build(mid+1, r, 2*node+1);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int l, int r, int tl, int tr, int node){
if(tl > r or tr < l) return {inf, inf};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(l, r, tl, mid, 2*node), query(l, r, mid+1, tr, 2*node+1));
}
} seg;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int query(int l, int r, int minant){
int c = pref[r] - pref[l-1];
c %= mod;
int a = seg.query(l, r, 1, n, 1).fr;
int res = (c-1)*(a-1);
res %= mod
res *= c*a;
res %= mod;
res *= binpow(4, mod-1, mod);
res %= mod;
res += ((a+c-2)*a*c)/2;
res %= mod;
res += a*c;
res %= mod;
a = minant;
int res2 = (c-1)*(a-1);
res2 %= mod;
res2 *= c*a;
res2 %= mod;
res2 *= binpow(4, mod-1, mod);
res2 %= mod;
res2 %= mod;
res2 += ((a+c-2)*a*c)/2;
res2 %= mod;
res2 += a*c;
res2 %= mod;
res -= res2;
res %= mod;
res += mod;
res %= mod;
// cout << l << ' ' << r << ' ' << minant << ": " << res << "\n";
return res % mod;
}
int32_t main(){
cin >> n;
for(int i = 1;i <= n;i++){
cin >> h[i];
}
for(int i = 1;i <= n;i++){
cin >> w[i];
}
seg.build(1, n, 1);
queue <array <int,4>> q;
q.push({1, n, 0, 0});
for(int i = 1;i <= n;i++){
pref[i] = pref[i-1] + w[i];
pref[i] %= mod;
}
int res = 0;
while(!q.empty()){
auto [l, r, minant, aux] = q.front();
q.pop();
if(aux == 0){
res += query(l, r, minant); res %= mod;
auto [minn, pos] = seg.query(l, r, 1, n, 1);
if(pos != l) q.push({l, pos-1, minn, 0});
if(pos != r) q.push({pos+1, r, minn, 1});
}
else{
auto [minn, pos] = seg.query(l, r, 1, n, 1);
if(minant == minn){
if(pos != l) q.push({l, pos-1, minn, 0});
if(pos != r) q.push({pos+1, r, minn, 1});
}
else{
q.push({l, r, minant, 0});
}
}
}
cout << res << '\n';
return 0;
}
Compilation message
fancyfence.cpp: In function 'long long int query(long long int, long long int, long long int)':
fancyfence.cpp:70:15: error: expected ';' before 'res'
70 | res %= mod
| ^
| ;
71 | res *= c*a;
| ~~~
