# 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;
}
printf("%lld\n",dis[nw[1][1]]);
return 0;
}

## 寒假集训日志（二）——最小生成树，拓扑排序，欧拉回路，连通路

Roadblock 时间限制: 1 Sec  内存限制: 64 MB提交: 9  解决: 5[提交][状态][讨论版] 题目描述 Every morning, FJ wakes up and walks across the farm from his house to the barn.  The farm is a collection of N fields (1 <= N <= 250) connected by M bidirectional pathways (1 <= M

## （寒假集训）Mooo Moo （完全背包）

Mooo Moo 时间限制: 1 Sec  内存限制: 64 MB提交: 5  解决: 4[提交][状态][讨论版] 题目描述 Farmer John has completely forgotten how many cows he owns!  He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse.  Ins

## （寒假集训）Watering the Fields （最小生成树）

Watering the Fields 时间限制: 1 Sec  内存限制: 64 MB提交: 26  解决: 10[提交][状态][讨论版] 题目描述 Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000). Each field i is described by a distinct point (x

## 寒假集训.Skew Binary

Skew Binary Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Submit Status Practice UVA 575 Description When a number is expressed in decimal, the k-th digit represents a multiple of 10k. (Digits are numbered from right to left,

## （寒假集训） Piggyback（最短路）

Piggyback 时间限制: 1 Sec  内存限制: 64 MB提交: 3  解决: 3[提交][状态][讨论版] 题目描述 Bessie and her sister Elsie graze in different fields during the day,and in the evening they both want to walk back to the barn to rest.Being clever bovines, they come up with a plan to