费用流，其实bushi
给你长为\(n\)的序列\(a\),\(b\)。\(a\)单增，\(b\)有正有负。
\(q\)次询问\([l,r]\)，保证\(\sum\limits_{i=l}^rb_i=0\)，将区间\([l,r]\)中每个值当节点，\(b_i<0\)的连S,\(b_i>0\)的连T,容量为\(abs(b_i)\)。两两点连边，容量为inf，费用为\(abs(a_i-a_j)\)。问最小费用最大流。
显然有一个感性的贪心思路：每次尽量会去抵消前面最近的需要抵消的流量，抵消后自己剩余的留量就留给后面抵消。这样就可以从前枚举\(l~r\)，考虑每个点贡献对前面流单位流量贡献\(a_i\),后面\(-a_i\)
关键是前后分别流多少？
令\(s_i\)为\(b_i\)求前缀和。
发现询问跟\(i\)和\(s_{l}\)有关，如果用主席树处理好了每个\(i\)的贡献，记录一个版本，具体修改三次区间修改即可，操作2要维护两个值（关于/不关于\(s_{l-1}\)）。这样询问，直接\(rt_{l-1}\)到\(rt_r\)版本差分单点查询。
ps.不建议写，非常卡空间，官方有更好写的树状数组写法，也可以离线线段树，当然我是为了练主席树。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int M=1e7+5e6;
const int mod=1e9+7;
int m,n,rt[N],q;
ll sum[N],s[N],a[N],b[N],val[N];
struct segment {
int nd,p,q,ls[M],rs[M],va[M],vab[M];
ll w1,w2,part;
void Update(int &x,int l,int r,int lst) {
if(x<=part){x=++nd;if(lst){ls[x]=ls[lst],rs[x]=rs[lst];va[x]=va[lst],vab[x]=vab[lst];}}
if(p<=l&&r<=q) {if(w1)va[x]=(va[x]+w1)%mod;vab[x]=(vab[x]+w2)%mod;return;}
int mid=(l+r)>>1;
if(p<=mid)Update(ls[x],l,mid,ls[lst]);
if(q>mid)Update(rs[x],mid+1,r,rs[lst]);
}
void Query(int x,int y,int l,int r) {
// printf("!x=%d y=%d [%d,%d] w1=%lld w2=%lld\n",x,y,l,r,va[y]-va[x],vab[y]-vab[x]);
w1=(w1+va[y]-va[x])%mod;w2=(w2+vab[y]-vab[x])%mod;
if(l==r) {return;}
int mid=(l+r)>>1;
(p<=mid)?Query(ls[x],ls[y],l,mid):Query(rs[x],rs[y],mid+1,r);
}
void init() {
for(int i=1;i<=n;i++) {
part=nd;
// printf("i=%d ~~~\n",i);
int opt=(b[i]<0)?-1:1,l,r;
if(opt<0) {l=s[i],r=s[i-1];}
else {l=s[i-1],r=s[i];}
w1=-a[i]*b[i]%mod,w2=0,p=0,q=l,Update(rt[i],1,m,rt[i-1]);
w1=a[i]*b[i]%mod,w2=0,p=r,q=m,Update(rt[i],1,m,rt[i-1]);
if(r-l<=1)continue;
w1=-opt*(sum[i-1]+sum[i])*a[i]%mod,w2=2*opt*a[i]%mod,p=l+1,q=r-1,Update(rt[i],1,m,rt[i-1]);
}
}
}S;
void in_puts() {
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);}
for(int i=1;i<=n;i++) {scanf("%lld",&b[i]);s[i]=sum[i]=val[i]=s[i-1]+b[i];sum[i]%=mod;}
sort(val,val+1+n);
m=unique(val,val+1+n)-val;
for(int i=0;i<=n;i++) {s[i]=lower_bound(val,val+m,s[i])-val+1;}
}
int main() {
in_puts();
S.init();
for(int i=1;i<=q;i++) {
int l,r;scanf("%d%d",&l,&r);
S.w1=S.w2=0,S.p=s[l-1];S.Query(rt[l-1],rt[r],1,m);
ll ans=S.w2*sum[l-1]+S.w1;
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
有很多关于如何使用javascript获取httpheader的问题，但由于某些原因，它们没有显示HTTP_CF_IPCOUNTRYheader。如果我尝试使用phpecho$_SERVER["HTTP_CF_IPCOUNTRY"];，它会工作，所以CF工作得很好。是否可以使用javascript获取此header？ 最佳答案 @Quentin的回答是正确的，适用于任何试图访问服务器header的javascript客户端。但是，由于这个问题特定于Cloudlfare，并且特定于在HTTP_CF_IPCOUNTRYheader中正常
我使用以下库连接到云Controllerhttps://github.com/prosociallearnEU/cf-nodejs-clientconstendpoint="https://api.mycompany.com/";constusername="myuser";constpassword="mypass";constCloudController=new(require("cf-client")).CloudController(endpoint);constUsersUAA=new(require("cf-client")).UsersUAA;constApps=new
CloudFoundry的CLI工具位于cloudfoundry/cli是用围棋写的。我正在尝试构建CLI工具但出现此错误:gobuildruntime:linux/386必须使用make.bash引导如何解决这个问题？下面是cli/bin/build-all.sh脚本的内容:#!/bin/bashset-eset-xOUTDIR=$(dirname$0)/../outGOARCH=amd64GOOS=windows$(dirname$0)/build&&cp$OUTDIR/cf$OUTDIR/cf-windows-amd64.exeGOARCH=386GOOS=windows$(di
我有一个在CF.NET和.NET下运行的库，但两者之间的序列化不同。因此，在CF.NET下生成的XML文件在.NET下不可读，这对我来说是个大问题!这里是代码示例:[Serializable,XmlRoot("config")]publicsealedclassRemoteHost:IEquatable{//...}publicclassProgram{publicstaticvoidMain(){RemoteHosthost=newRemoteHost("A");Listhosts=newList();hosts.Add(host);XmlSerializerser=newXmlSe
我完全没有使用过Windows编程，但现在我有一个问题想在某个程序中修复。我需要将图像放置到Windows剪贴板，并且我有指向有效DIB(设备独立位图)的原始指针(在我的实验中，dibheader版本为3)。该程序使用具有延迟剪贴板渲染的模型，这意味着首先我们使用SetClipboardData(CF_DIB,NULL)然后在WM_RENDERFORMAT消息上程序将实际数据放入剪贴板使用SetClipboardData(format,dibDataPointer)。当我打开clipbrd.exe(在windowsxp上)并选择DIBView时，我可以毫无问题地看到图像。但是在msdn
我创建了一些模型，添加了迁移，然后执行了更新数据库操作，但在我最后一次更新数据库操作时，我收到了错误消息:Sequencecontainsmorethanoneelement您可以在下面找到我的迁移配置:context.Categories.AddOrUpdate(p=>p.CategoryName,newCategory{CategoryName="Sport"},newCategory{CategoryName="Music"});context.Subcategories.AddOrUpdate(p=>p.SubcategoryName,newSubcategory{Subcat
如何使用ZXing.Net将我的字符串编码为二维码？我已经可以解码了，但是编码有问题。它有一条错误消息:没有可用于AZTEC格式的编码器。这是我的代码:IBarcodeWriterwriter=newBarcodeWriter();BitmapbarcodeBitmap;varresult=writer.Encode("Hello").ToBitmap();barcodeBitmap=newBitmap(result);pictureBox1.Image=barcodeBitmap; 最佳答案 您没有完全初始化BarcodeWrit
我有一个应用程序(.NetCompactFramework3.5)在WindowsMobile6.1设备上运行，我想检测USB连接何时发生变化(连接或断开连接)。我最初使用SystemProperty.CradlePresent属性来触发事件，但我想知道这是否仅在连接的设备具有ActiveSync时才有效？我将通过USB从未运行ActiveSync的Linux设备接收连接。我仍然可以使用SystemProperty.CradlePresent来检测USB的连接/断开连接吗？或者我是否需要探索其他选项来检测USB事件？谢谢。 最佳答案
我需要为元素“aaa”创建一个前缀为“xx”的属性“abc”。以下代码添加了前缀，但它也将namespaceUri添加到元素。要求的输出:我的代码:XmlNodenode=doc.SelectSingleNode("//mybody");XmlElementele=doc.CreateElement("aaa");XmlAttributenewAttribute=doc.CreateAttribute("xx","abc",namespace);newAttribute.Value="ddd";ele.Attributes.Append(newAttribute);node.Inser
这是我的问题，我安装了用于wordpress的联系表7，在wpcf7_before_send_mail期间我调用了API，如果API返回错误，我需要使表单无效，然后我需要使请求无效并返回错误从API调用返回。我在API失败时将标志设置为false，错误消息也被存储，但尽管我导致失败，但我的表单正在成功通过。add_action("wpcf7_before_send_mail","wpcf7_send_contact_builder");functionwpcf7_send_contact_builder($form){$submission=WPCF7_Submission::get_