P2517 [HAOI2010] 订货
考虑费用流。
记源点为 \(S\)，汇点为 \(T\)。流量为 \(w\) 费用为 \(c\) 的边为 \((w,c)\)。\(k\) 为题面中的 \(S\)。
点 \(i\) 表示第 \(i\) 天的情况。
\(S\to i,(\infty,d_i)\) 表示进货，没有限制，费用为 \(d_i\)。
\(i\to T,(U_i,0)\) 表示供货，用最大流限制满足需求。
\(i\to i+1,(k,m)\) 表示存储到下一个月，最多存 \(k\) 个，存储费用 \(m\)。
跑最小费用最大流就是答案。
#include<bits/stdc++.h>
#define N 5005
using namespace std;
namespace Network{struct edge{int x,w,c,id;};bool vis[N];queue<int>q;int n,S,T,maxflow,dis[N];int cost;vector<edge>s[N];vector<edge>::iterator cur[N];void add(int u,int v,int w,int c){n=max({n,u,v});int id1=s[u].size();int id2=s[v].size();s[u].push_back({v,w,c,id2});s[v].push_back({u,0,-c,id1});}int dfs(int x,int flow){if(x==T) returnmaxflow+=flow,cost+=dis[T]*flow,flow;vis[x]=true;int res=0;auto it=cur[x];for(;it!=s[x].end();it++){auto &p=*it;if(!vis[p.x]&&p.w&&dis[x]+p.c==dis[p.x]){int t=dfs(p.x,min(flow-res,p.w));p.w-=t,s[p.x][p.id].w+=t,res+=t;if(res==flow) break;}}cur[x]=it;return vis[x]=false,res;}bool SPFA(){memset(vis,0,sizeof vis);memset(dis,0x3f,sizeof dis);q.push(S),dis[S]=0,vis[S]=true;while(!q.empty()){int x=q.front();q.pop(),vis[x]=false;for(auto p:s[x]) if(p.w&&dis[p.x]>dis[x]+p.c){dis[p.x]=dis[x]+p.c;if(!vis[p.x]) q.push(p.x),vis[p.x]=true;}}return dis[T]<0x3f3f3f3f;}pair<int,int>MCMF(int st,int ed){S=st,T=ed,maxflow=cost=0;while(SPFA()){for(int i=1;i<=n;i++)cur[i]=s[i].begin();dfs(S,INT_MAX);}return {maxflow,cost};}
};using Network::add;
const int inf=0x3f3f3f3f;
int n,m,k,S,T;
int main(){scanf("%d%d%d",&n,&m,&k),S=n+1,T=n+2;for(int i=1,x;i<=n;i++) scanf("%d",&x),add(i,T,x,0);for(int i=1,x;i<=n;i++) scanf("%d",&x),add(S,i,inf,x);for(int i=1;i<n;i++) add(i,i+1,k,m);printf("%d\n",Network::MCMF(S,T).second);return 0;
}
P4585 [FJOI2015] 火星商店问题
求最大异或值可以使用 01-trie 树 \(\mathcal O(\log n)\) 维护和查询。
还剩下位置、时间两维，可以用树套树做。但这样时间复杂度 \(\mathcal O(n\log n^3)\) 且很难实现。
事实上在时间维越后出现的位置越优，因此可以在 trie 树上记录每个节点最后一个出现的位置看是否在查询的区间。
剩下位置维用线段树解决，可以使用标记永久化避免 trie 树合并，时间复杂度 \(\mathcal O(n\log^2 n)\)。
#include<bits/stdc++.h>
#define N 100000
using namespace std;
struct node{int ch[2],val;
}a[N*400];
int n,m,idx,day;
struct Trie{int rt=0;void ins(int x,int tim){int p=rt?rt:(rt=++idx);for(int i=20;~i;i--){bool t=x&1<<i;if(!a[p].ch[t]) a[p].ch[t]=++idx;p=a[p].ch[t],a[p].val=max(a[p].val,tim);}}int query(int x,int tim){if(!rt) return 0;int p=rt,res=0;for(int i=20;~i;i--){bool t=!(x&1<<i);if(a[a[p].ch[t]].val>tim)p=a[p].ch[t],res|=1<<i;else p=a[p].ch[!t];}return res;}
};
class SGT{#define l(i) ((i)<<1)#define r(i) ((i)<<1|1)private:Trie tr[N<<2];public:void upd(int p,int v,int tim,int x=1,int l=1,int r=n){tr[x].ins(v,tim);if(l==r) return;int mid=l+r>>1;if(p<=mid) upd(p,v,tim,l(x),l,mid);else upd(p,v,tim,r(x),mid+1,r);}int query(int ql,int qr,int v,int tim,int x=1,int l=1,int r=n){if(ql<=l&&qr>=r) return tr[x].query(v,tim);int mid=l+r>>1,res=0;if(ql<=mid) res=max(res,query(ql,qr,v,tim,l(x),l,mid));if(qr>mid) res=max(res,query(ql,qr,v,tim,r(x),mid+1,r));return res;}
}tr;
int main(){scanf("%d%d",&n,&m);for(int i=1,x;i<=n;i++)scanf("%d",&x),tr.upd(i,x,n);while(m--){int op,l,r,x,d;scanf("%d",&op);if(op)scanf("%d%d%d%d",&l,&r,&x,&d),printf("%d\n",tr.query(l,r,x,max(day-d,0)));else scanf("%d%d",&x,&d),tr.upd(x,d,++day);}return 0;
}