#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6,inf=1e9,minf=-1e9,lg=30,Mxn=1e9;
int n,k,m,d,q;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int val[mxn+10][2];
int P[mxn+10],sub[mxn+10][2],sz;
vector<int>comp;
struct seg{
int dp[4*mxn+10],waysx[4*mxn+10],ways[4*mxn+10];
pii lazy[4*mxn+10];
//waysx= ways*x
void init(){for(int i=0;i<=4*sz;i++)dp[i]=waysx[i]=ways[i]=0,lazy[i]={1,0};}
void apply(int pos,pii x){
dp[pos]=((x.f*dp[pos])%mod+(x.s*waysx[pos])%mod)%mod;
waysx[pos]=(x.f*waysx[pos])%mod;
ways[pos]=(x.f*ways[pos])%mod;
lazy[pos]={(lazy[pos].f*x.f)%mod,((lazy[pos].s*x.f)%mod+(lazy[pos].f*x.s)%mod)%mod};
}
void push(int pos,int l,int r){
if(lazy[pos].f==1&&lazy[pos].s==0)return;
if(l!=r){
apply(pos<<1,lazy[pos]);
apply(pos<<1|1,lazy[pos]);
}
lazy[pos]={1,0};
}
void pull(int pos){
dp[pos]=(dp[pos<<1]+dp[pos<<1|1])%mod;
waysx[pos]=(waysx[pos<<1]+waysx[pos<<1|1])%mod;
ways[pos]=(ways[pos<<1]+ways[pos<<1|1])%mod;
}
void update(int ql,int qr,int k,int pos=1,int l=0,int r=sz){
if(l>qr||r<ql)return;
if(ql<=l&&r<=qr)return void(apply(pos,{k,k}));
push(pos,l,r);
update(ql,qr,k,pos<<1,l,((l+r)>>1));
update(ql,qr,k,pos<<1|1,((l+r)>>1)+1,r);
pull(pos);
}
void modify(int qpos,int d,int w,int pos=1,int l=0,int r=sz){
if(l>qpos||r<qpos)return;
if(l==r){
dp[pos]=(dp[pos]+d)%mod;
ways[pos]=(ways[pos]+w)%mod;
waysx[pos]=(waysx[pos]+(w*comp[l])%mod)%mod;
return;
}
push(pos,l,r);
if(qpos<=(l+r)>>1)modify(qpos,d,w,pos<<1,l,((l+r)>>1));
else modify(qpos,d,w,pos<<1|1,((l+r)>>1)+1,r);
pull(pos);
}
int getways(int ql,int qr,int pos=1,int l=0,int r=sz){
if(l>qr||r<ql)return 0;
if(ql<=l&&r<=qr)return ways[pos];
push(pos,l,r);
return (getways(ql,qr,pos<<1,l,((l+r)>>1))+getways(ql,qr,pos<<1|1,((l+r)>>1)+1,r))%mod;
}
int getdp(int ql,int qr,int pos=1,int l=0,int r=sz){
if(l>qr||r<ql)return 0;
if(ql<=l&&r<=qr)return dp[pos];
push(pos,l,r);
return (getdp(ql,qr,pos<<1,l,((l+r)>>1))+getdp(ql,qr,pos<<1|1,((l+r)>>1)+1,r))%mod;
}
}t;
struct fen{
int fwk[mxn+10];
void init(){for(int i=0;i<=sz+1;i++)fwk[i]=0;}
void update(int pos,int val){
pos++;
if(pos<=0)return;
for(int i=pos;i<=sz+1;i+=(i&-i))fwk[i]+=val;
}
int qry(int pos){
pos++;
int sum=0;
if(pos<=0)return 0;
for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
return sum;
}
}tmx,tmn;
int32_t main(){
fastio
cin>>n;
int mx=0,ans=0;
P[0]=1;
comp.pb(0);
for(int i=1;i<=n;i++)P[i]=(P[i-1]*2LL)%mod;
for(int i=1;i<=n;i++)cin>>val[i][0];
for(int i=1;i<=n;i++){
cin>>val[i][1];
if(val[i][0]>val[i][1])swap(val[i][0],val[i][1]);
comp.pb(val[i][0]);
comp.pb(val[i][1]);
}
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
sz=comp.size()-1;
for(int i=1;i<=n;i++){
val[i][0]=lb(all(comp),val[i][0])-comp.begin();
val[i][1]=lb(all(comp),val[i][1])-comp.begin();
}
for(int i=1;i<=n;i++){
for(int k=0;k<2;k++)ans=(ans-(P[n-1]*comp[val[i][k]]%mod)+mod)%mod;
}
vector<pii>upd;
int sum2=0;
t.init();
t.modify(0,0,1);
for(int i=1;i<=n;i++)tmx.update(val[i][1],1),tmn.update(val[i][0],1);
for(int i=1;i<=n;i++){
tmx.update(val[i][1],-1);
tmn.update(val[i][0],-1);
for(int k=0;k<2;k++){
if(tmn.qry(val[i][k]-1)==n-i){
sum2=P[tmx.qry(val[i][k]-1)];
ans=(ans+(sum2*(t.getdp(0,val[i][k])+(t.getways(0,val[i][k])*comp[val[i][k]])%mod)%mod)%mod)%mod;
sub[i][k]=sum2;
}
}
upd.clear();
for(int k=0;k<2;k++){
upd.pb({t.getdp(0,val[i][k]-1),t.getways(0,val[i][k]-1)});
}
t.update(0,val[i][0]-1,0);
t.update(val[i][0],val[i][1]-1,1);
t.update(val[i][1],sz,2);
for(int k=0;k<2;k++){
t.modify(val[i][k],(upd[k].f+(comp[val[i][k]]*upd[k].s)%mod)%mod,upd[k].s);
}
}
for(int i=1;i<=n;i++)tmx.update(val[i][1],1),tmn.update(val[i][0],1);
t.init();
t.modify(0,0,1);
for(int i=n;i>=1;i--){
//fix left equal
tmx.update(val[i][1],-1);
tmn.update(val[i][0],-1);
for(int k=0;k<2;k++){
if(tmn.qry(val[i][k])==i-1){
sum2=P[tmx.qry(val[i][k])];
ans=ans+(sum2*(t.getdp(0,val[i][k]-1)+(t.getways(0,val[i][k]-1)*comp[val[i][k]])%mod)%mod)%mod;
ans=(ans-(comp[val[i][k]]*(sub[i][k]*sum2)%mod)%mod+mod)%mod;
}
}
upd.clear();
for(int k=0;k<2;k++){
upd.pb({t.getdp(0,val[i][k]-1),t.getways(0,val[i][k]-1)});
}
t.update(0,val[i][0]-1,0);
t.update(val[i][0],val[i][1]-1,1);
t.update(val[i][1],sz,2);
for(int k=0;k<2;k++){
t.modify(val[i][k],(upd[k].f+(comp[val[i][k]]*upd[k].s)%mod)%mod,upd[k].s);
}
}
cout<<ans;
}
/*
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:12:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
12 | #pragma GCC optimize ("03,unroll-lopps")
| ^
Main.cpp:20:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
20 | void setIO(string name){
| ^
Main.cpp:33:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
33 | void init(){for(int i=0;i<=4*sz;i++)dp[i]=waysx[i]=ways[i]=0,lazy[i]={1,0};}
| ^
Main.cpp:35:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
35 | void apply(int pos,pii x){
| ^
Main.cpp:41:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
41 | void push(int pos,int l,int r){
| ^
Main.cpp:49:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
49 | void pull(int pos){
| ^
Main.cpp:54:67: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
54 | void update(int ql,int qr,int k,int pos=1,int l=0,int r=sz){
| ^
Main.cpp:62:68: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
62 | void modify(int qpos,int d,int w,int pos=1,int l=0,int r=sz){
| ^
Main.cpp:75:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
75 | int getways(int ql,int qr,int pos=1,int l=0,int r=sz){
| ^
Main.cpp:81:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
81 | int getdp(int ql,int qr,int pos=1,int l=0,int r=sz){
| ^
Main.cpp:91:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
91 | void init(){for(int i=0;i<=sz+1;i++)fwk[i]=0;}
| ^
Main.cpp:92:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
92 | void update(int pos,int val){
| ^
Main.cpp:97:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
97 | int qry(int pos){
| ^
Main.cpp:106:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
106 | int32_t main(){
| ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
