# A. U.N.OWEN就是她吗？

$$\sum\limits_{l=1}^{p[i]}\sum\limits_{r=p[i]}^m sumB[r]-sumB[l-1]<=sumA[R[r]]-sumA[L[l]-1]$$

$$sumB[r]-sumA[R[r]]<=sumB[l-1]-sumA[L[l]-1]$$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+50;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
while(!isdigit(ch)) f=ch==‘-‘,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return f?-x:x;
}
int n,m;
int a[N],cf[N],ans[N],I[N];
ll sum[N],C[N<<2],D[N<<2],tagC[N<<2],tagD[N<<2],sc[N],sd[N];
struct O{int l,r,id;}dat[N];
bool cmp(O a,O b){return a.l<b.l;}
#define lch k<<1
#define rch k<<1|1
//C维护最小值，D维护最大值
void down(int k){
if(tagC[k]) C[lch]+=tagC[k],C[rch]+=tagC[k],tagC[lch]+=tagC[k],tagC[rch]+=tagC[k],tagC[k]=0;
if(tagD[k]) D[lch]+=tagD[k],D[rch]+=tagD[k],tagD[lch]+=tagD[k],tagD[rch]+=tagD[k],tagD[k]=0;
}
void add(int k,int l,int r,int L,int R,int opt,int e){//0是C,1是D

if(L>R) return;
if(L<=l&&r<=R) return opt?(D[k]+=e,tagD[k]+=e):(C[k]+=e,tagC[k]+=e)/*,printf("!%d %d %d %d %d %d %lld %lld\n",l,r,L,R,opt,e,C[k],D[k])*/,void();
int mid=(l+r)>>1;down(k);
C[k]=min(C[lch],C[rch]),D[k]=max(D[lch],D[rch]);

}
ll g(int opt,ll res,ll querY){return opt?max(res,querY):min(res,querY);}
ll query(int k,int l,int r,int L,int R,int opt){
if(L<=l&&r<=R) return opt?D[k]:C[k];
int mid=(l+r)>>1;down(k);
ll res=opt?-0x3f3f3f3f3f3f3f3f:0x3f3f3f3f3f3f3f3f;
if(L<=mid) res=g(opt,res,query(lch,l,mid,L,R,opt));
if(R>mid) res=g(opt,res,query(rch,mid+1,r,L,R,opt));
return res;
}
void build(int k,int l,int r){
if(l==r) return C[k]=sc[dat[l].id],D[k]=sd[dat[l].id],void();
int mid=(l+r)>>1;build(lch,l,mid),build(rch,mid+1,r);
C[k]=min(C[lch],C[rch]),D[k]=max(D[lch],D[rch]);
}
#undef lch
#undef rch
int main(){
n=rd();for(int i=1;i<=n;++i) a[i]=rd();m=rd();for(int i=1;i<=m;++i) dat[i].l=rd(),dat[i].r=rd(),ans[i]=rd(),dat[i].id=i,cf[dat[i].l]++,cf[dat[i].r+1]--;
sort(dat+1,dat+m+1,cmp);for(int i=1;i<=m;++i) I[dat[i].id]=i;
for(int i=1;i<=n;++i) cf[i]+=cf[i-1],sum[i]=sum[i-1]+(cf[i]>0?a[i]:0);
for(int i=1;i<=m;++i) sd[i]=-sum[dat[I[i]].r],sc[i]=-sum[dat[I[i]].l-1];
build(1,1,m);
for(int i=1;i<=m;++i){
ll rx=query(1,1,m,I[i],m,1),ln=query(1,1,m,1,I[i],0);
printf("%d\n",ans[i]=min(0ll+ans[i],ln-rx));
//for(int j=1;j<=m;++j) printf("C[%d]=%lld D[%d]=%lld\n",j,query(1,1,m,j,j,0),j,query(1,1,m,j,j,1));puts("");
}
return 0;
}

# C. 平安时代的外星人

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=405;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
while(!isdigit(ch)) f=ch==‘-‘,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return f?-x:x;
}
const int sx[4]={0,0,1,-1},sy[4]={1,-1,0,0};
ll s[N][N],dis[N*N],pre[N*N],w[N*N*16];
map<int,int>lim[N*N],a[N*N];
pair<int,int> rem(int x){return make_pair((x-1)/m+1,(x-1)%m+1);}
bool check(int x,int y){return (x<=0||x>n||y<=0||y>m)?0:1;}
int id(int x,int y){return check(x,y)?(x-1)*m+y:0;}
void lnk(int x,int y,int value){if(!x||!y) return ;
}
int main(){
n=rd();m=rd();n++;m++;//点的数量是块的数量+1
for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) s[i][j]=rd();
for(int i=1;i<=n-1;++i) for(int j=1;j<=m;++j) a[id(i,j)][id(i+1,j)]=a[id(i+1,j)][id(i,j)]=rd();
for(int i=1;i<=n;++i) for(int j=1;j<=m-1;++j) a[id(i,j)][id(i,j+1)]=a[id(i,j+1)][id(i,j)]=rd();
for(int i=1;i<=n*m;++i) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
priority_queue<pair<ll,int> >q;q.push(make_pair(dis[1]=0,1));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;vis[u]=1;
pair<int,int>A=rem(u);
for(int i=0,I;i<4;++i) if(check(A.first+sx[i],A.second+sy[i])&&dis[I=id(A.first+sx[i],A.second+sy[i])]>dis[u]+a[u][I]) pre[I]=u,q.push(make_pair(-(dis[I]=dis[u]+a[u][I]),I));
}
for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) if(s[i][j]){
int I=id(i,j),J;
while(I!=1) J=pre[I],lim[I][J]=lim[J][I]=1,I=J;
}
int tot=0;for(int i=1;i<=n*m;++i) for(int j=0;j<4;++j) nw[i][j]=++tot;

al[id(1,1)][0]=1;
for(int i=1;i<=n-1;++i) for(int j=1;j<=m-1;++j) if(s[i][j]) al[id(i,j)][2]=al[id(i+1,j)][3]=al[id(i,j+1)][1]=al[id(i+1,j+1)][0]=1;

for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
int I=id(i,j),J;
if(!al[I][0]&&!al[I][3]&&!lim[I][id(i-1,j)]) lnk(nw[I][0],nw[I][3],0),lnk(nw[I][3],nw[I][0],0);
if(!al[I][0]&&!al[I][1]&&!lim[I][id(i,j-1)]) lnk(nw[I][0],nw[I][1],0),lnk(nw[I][1],nw[I][0],0);
if(!al[I][1]&&!al[I][2]&&!lim[I][id(i+1,j)]) lnk(nw[I][1],nw[I][2],0),lnk(nw[I][2],nw[I][1],0);
if(!al[I][2]&&!al[I][3]&&!lim[I][id(i,j+1)]) lnk(nw[I][2],nw[I][3],0),lnk(nw[I][3],nw[I][2],0);

if(j-1>=1){J=id(i,j-1);
if(!al[I][0]&&!al[J][3]) lnk(nw[I][0],nw[J][3],a[J][I]);
if(!al[I][1]&&!al[J][2]) lnk(nw[I][1],nw[J][2],a[J][I]);
}
if(j+1<=m){J=id(i,j+1);
if(!al[I][3]&&!al[J][0]) lnk(nw[I][3],nw[J][0],a[J][I]);
if(!al[I][2]&&!al[J][1]) lnk(nw[I][2],nw[J][1],a[J][I]);
}
if(i-1>=1){J=id(i-1,j);
if(!al[I][0]&&!al[J][1]) lnk(nw[I][0],nw[J][1],a[J][I]);
if(!al[I][3]&&!al[J][2]) lnk(nw[I][3],nw[J][2],a[J][I]);
}
if(i+1<=n){J=id(i+1,j);
if(!al[I][1]&&!al[J][0]) lnk(nw[I][1],nw[J][0],a[J][I]);
if(!al[I][2]&&!al[J][3]) lnk(nw[I][2],nw[J][3],a[J][I]);
}
}

for(int i=1;i<=tot;++i) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0;
q.push(make_pair(dis[nw[1][3]]=0,nw[1][3]));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;vis[u]=1;
}