维护一个数列,操作：查询k在区间内的排名、查询区间内排名为k的值3、修改某一位上的数值、查询k在区间内的前驱(前驱定义为小于x，且最大的数)、查询k在区间内的后继(后继定义为大于x，且最小的数)
线段树套treap，我写了一个星期QAQ第一、三个操作直接搞；第二个操作就二分那个值，然后查它在区间内的排名；第四、五个操作就当查询值≤(≥)当前节点就往左(右)走，用一个全局变量记往左(右)走时遍历过的最大(小)值。反思：本弱各种写挂，以前从来把treap的rotate操作写的和splay的rotate操作一样，结果这题如果还这样写，将会异常麻烦，因此不得不用引用型写法，去掉了一个fa数组，异常不习惯。同时第二个操作也很蛋疼，推了很久（实际上是抄了很久），treap也很久没写了，甚至删除节点还出现if(cnt[x]>1){cnt[x]–,sz[x]–; return;}写成if(cnt[x]>0){cnt[x]–,sz[x]–; return;}的错误，调了一整个晚修QAQ。最后交的时候10s，差点TLE。求了一下序列中的最大最小值，在第二个操作做二分时用，省了0.2s；又将线段树的l、r、lc、rc数组去掉，省了0.6s，最后结果是9.2s，还是卡时啊……
yyl大爷：你要多写些题，提高代码能力！ orzzzzzzz……
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2500000
#define maxm 200000
#define INF 0x3fffffff
using namespace std;
int v[maxn],rnd[maxn],root[maxm],ch[maxn][2],cnt[maxn],sz[maxn],nds,mx,mn,n;
stack <int> pool;
int newnode(){
if(pool.empty())return ++nds;else{int x=pool.top(); pool.pop(); return x;}
}
void delnode(int x){pool.push(x);}
void update(int x){if(! x)return; sz[x]=cnt[x]+sz[ch[x][0]]+sz[ch[x][1]];}
void rotate(int &x,bool lr){
if(!x)return; int a=ch[x][lr]; ch[x][lr]=ch[a][!lr]; ch[a][!lr]=x; update(x); x=a; update(a);
}
void insert(int &x,int num){
if(!x){int y=newnode(); v[y]=num; rnd[y]=rand(); ch[y][0]=ch[y][1]=0; cnt[y]=sz[y]=1; x=y; return;}
if(v[x]==num){cnt[x]++; sz[x]++; return;}
if(num<v[x])insert(ch[x][0],num);else insert(ch[x][1],num); update(x);
if(ch[x][0]&&rnd[ch[x][0]]<rnd[x])rotate(x,0);
if(ch[x][1]&&rnd[ch[x][1]]<rnd[x])rotate(x,1);
}
void del(int &x,int num){
if(!x)return;
if(v[x]==num){
if(cnt[x]>1){cnt[x]--,sz[x]--; return;}
if(ch[x][0]*ch[x][1]==0){delnode(x); x=ch[x][0]+ch[x][1]; return;} int y=x;
if(rnd[ch[x][0]]<rnd[ch[x][1]])rotate(x,0),del(ch[x][1],num);else rotate(x,1),del(ch[x][0],num);
update(x); return;
}
if(num<v[x])del(ch[x][0],num);else del(ch[x][1],num); update(x);
}
int rank(int x,int num){
if(!x)return 0; if(v[x]==num)return sz[ch[x][0]];
if(num<v[x])return rank(ch[x][0],num);else return rank(ch[x][1],num)+sz[ch[x][0]]+cnt[x];
}
int ans;
void before(int x,int num){
if(!x)return; if(num<=v[x])before(ch[x][0],num); else ans=max(ans,v[x]),before(ch[x][1],num);
}
void after(int x,int num){
if(!x)return; if(num>=v[x])after(ch[x][1],num); else ans=min(ans,v[x]),after(ch[x][0],num);
}
void add(int x,int l,int r,int pos,int num){
insert(root[x],num); if(l==r)return; int M=(l+r)>>1;
if(l<=pos&&pos<=M)add(x<<1,l,M,pos,num);
if(M<pos&&pos<=r)add(x<<1|1,M+1,r,pos,num);
}
void change(int x,int l,int r,int pos,int num,int val){
del(root[x],num); insert(root[x],val); if(l==r)return; int M=(l+r)>>1;
if(l<=pos&&pos<=M)change(x<<1,l,M,pos,num,val); if(M<pos&&pos<=r)change(x<<1|1,M+1,r,pos,num,val);
}
int getrank(int k,int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return rank(root[x],k); int M=(l+r)>>1,q=0;
if(ql<=M)q+=getrank(k,x<<1,l,M,ql,qr); if(M<qr)q+=getrank(k,x<<1|1,M+1,r,ql,qr); return q;
}
int getindex(int k,int ql,int qr){
int L=mn,R=mx;
while(L<=R){
int M=(L+R)>>1; int x=getrank(M,1,1,n,ql,qr);
if(x+1<=k)L=M+1,ans=M;else R=M-1;
}
return ans;
}
void getbefore(int k,int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){before(root[x],k); return;} int M=(l+r)>>1;
if(ql<=M)getbefore(k,x<<1,l,M,ql,qr); if(M<qr)getbefore(k,x<<1|1,M+1,r,ql,qr);
}
void getafter(int k,int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){after(root[x],k); return;} int M=(l+r)>>1;
if(ql<=M)getafter(k,x<<1,l,M,ql,qr); if(M<qr)getafter(k,x<<1|1,M+1,r,ql,qr);
}
int val[maxm],m;
int main(){
scanf("%d%d",&n,&m); mx=-1; mn=INF;
inc(i,1,n)scanf("%d",&val[i]),mx=max(mx,val[i]),mn=min(mn,val[i]),add(1,1,n,i,val[i]);
inc(i,1,m){
int opt,x,y,z; scanf("%d",&opt);
if(opt==1)scanf("%d%d%d",&x,&y,&z),printf("%d\n",getrank(z,1,1,n,x,y)+1);
if(opt==2)scanf("%d%d%d",&x,&y,&z),printf("%d\n",getindex(z,x,y));
if(opt==3)scanf("%d%d",&x,&y),change(1,1,n,x,val[x],y),val[x]=y,mx=max(mx,y),mn=min(mn,y);
if(opt==4)scanf("%d%d%d",&x,&y,&z),ans=-1,getbefore(z,1,1,n,x,y),printf("%d\n",ans);
if(opt==5)scanf("%d%d%d",&x,&y,&z),ans=INF,getafter(z,1,1,n,x,y),printf("%d\n",ans);
}
return 0;
}m个任务，任务(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束，优先级为Pi。n个询问，每次询问第Xi秒正在运行的任务中，优先级最小的Ki个任务的优先级之和是多少。若Ki大于第Xi秒正在运行的任务总数，输出第Xi秒任务优先级之和。m，n≤100000，强制在线。
第一次写主席树……（因为没彻底理解被yyl大爷d：你根本不理解主席树）主席树本质上就是权值线段树+重用节点。
反映在本题中，就是给每个时间点建一棵权值线段树，但这样会MLE，所以我们先将所有任务拆成“Si到n时间点的权值+Pi”和“Ei+1到n时间点的权值+(-Pi)，然后按插入的时间点排序，在每个插入操作前，将之前上一次操作得到的权值线段树的根节点指针复制过来，然后插入时只新开节点记录被修改后的节点，因为一次插入只会影响log2n个节点，所以总空间复杂度为O(nlog2n)，同时因为相隔两个插入时间点之间的时间点只要复制一个指针就行，每次插入时间复杂度为log2n，故时间复杂度为O(nlog2n)。本题可以不离散化，但我比较怂所以还是离散了一下省空间。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 400000
#define ll long long
using namespace std;
struct opt{int a,b,c,id;}; opt opts[maxn*2];
bool cmp1(opt a,opt b){return a.b<b.b;}
bool cmp2(opt a,opt b){return a.a<b.a;}
int lc[20*maxn],rc[20*maxn],rt[maxn],sz[20*maxn],n,m,valn,tot,optn;
ll sm[20*maxn];
void build(int &x,int l,int r){
x=++tot; lc[x]=rc[x]=sz[x]=sm[x]=0; if(l==r)return;
int mid=(l+r)>>1; build(lc[x],l,mid); build(rc[x],mid+1,r);
}
void ins(int &x,int l,int r,int y,int z1,int z2){
tot++; sm[tot]=sm[x]+(ll)(z1*z2); sz[tot]=sz[x]+z2;
lc[tot]=lc[x]; rc[tot]=rc[x]; x=tot; if(l==r)return; int mid=(l+r)>>1;
if(y<=mid)ins(lc[x],l,mid,y,z1,z2);else ins(rc[x],mid+1,r,y,z1,z2);
}
ll query(int x,ll k){
ll q=0; int y=x;
while(1){
if(k>=sz[y]){q+=sm[y]; return q;} if(!lc[y]&&!rc[y]){q+=sm[y]/sz[y]*k; return q;}
if(k==sz[lc[y]]){q+=sm[lc[y]]; return q;}
if(k<sz[lc[y]])y=lc[y];else k-=sz[lc[y]],q+=sm[lc[y]],y=rc[y];
}
}
int main(){
scanf("%d%d",&m,&n); optn=0;
inc(i,1,m){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
opts[++optn]=(opt){a,c,1,0}; if(b!=n)opts[++optn]=(opt){b+1,c,-1,0};
}
sort(opts+1,opts+1+optn,cmp1); valn=1; opts[1].id=1;
inc(i,2,optn){if(opts[i].b!=opts[i-1].b)opts[i].id=++valn;else opts[i].id=valn;}
tot=0; build(rt[0],1,valn); sort(opts+1,opts+1+optn,cmp2); opts[optn+1].a=n;
for(int i=1;i<=opts[1].a&&i<=n;i++)rt[i]=rt[i-1];
inc(i,1,optn){
ins(rt[opts[i].a],1,valn,opts[i].id,opts[i].b,opts[i].c);
for(int j=opts[i].a+1;j<=opts[i+1].a&&j<=n;j++)rt[j]=rt[j-1];
}
ll last=1;
inc(i,1,n){
int a;ll b,c,d; scanf("%d%lld%lld%lld",&a,&b,&c,&d);
last=query(rt[a],1+(b*last+c)%d);
printf("%lld\n",last);
}
return 0;
}某人从农场的(0,0)出发，沿边界到处乱走，走过的地方会留下栅栏，等走完后问要在多少个栅栏上开门才能使整个农场连通，最多走1000步。
我的代码比别人的都长~我的做法是先算出最左/最下可能会走到哪里，然后变换一下坐标系（实际是是改变出发起点），然后记录哪个格子的上下左右被栅栏堵了，最后做一下floodfill，输出连通块数-1。注意还要把有栅栏区域的外圈格子也算进去，因为它们代表了有栅栏区域外的广大地区（这个人的农场是无限大的）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
bool unok[2000][2000][4],vis[2000][2000]; int mx,my,tot,n;
char opt[2000];
void dfs(int x,int y){
vis[x][y]=1;
if(y!=0&&!unok[x][y][0]&&!vis[x][y-1])dfs(x,y-1);
if(x!=mx&&!unok[x][y][1]&&!vis[x+1][y])dfs(x+1,y);
if(y!=my&&!unok[x][y][2]&&!vis[x][y+1])dfs(x,y+1);
if(x!=0&&!unok[x][y][3]&&!vis[x-1][y])dfs(x-1,y);
}
int main(){
scanf("%d",&n); int x=1,y=1; scanf("%s",opt);
inc(i,0,n-1){if(opt[i]=='W')y++;if(opt[i]=='S')x++;}
memset(unok,0,sizeof(unok)); mx=my=0;
inc(i,0,n-1){
if(opt[i]=='N'){
unok[x][y][0]=1; unok[x][y-1][2]=1; x++; mx=max(mx,x);
}
if(opt[i]=='S'){
unok[x-1][y][0]=1; unok[x-1][y-1][2]=1; x--;
}
if(opt[i]=='W'){
unok[x][y-1][3]=1; unok[x-1][y-1][1]=1; y--;
}
if(opt[i]=='E'){
unok[x][y][3]=1; unok[x-1][y][1]=1; y++; my=max(my,y);
}
}
memset(vis,0,sizeof(vis)); tot=0;
inc(i,0,mx)inc(j,0,my)if(!vis[i][j])tot++,dfs(i,j);
printf("%d",tot-1);
return 0;
}有N个草堆在数轴的不同位置，向坐标x处扔炸弹，[x−R,x+R]的草堆都会燃爆。 K个炸弹，问如果要引爆所有的草堆最小的R。草堆数最多50000，坐标最大为109
二分R，判定时从小到大枚举草堆，如果这个草堆没被炸就在这里放炸弹（实际上是放在此处坐标+R的位置），炸掉与它距离≤2R的草堆，重复上述操作。本弱一开始以为炸掉的是与它距离≤2R+1的草堆，调了0.5hQAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
int n,k,x[60000];
int main(){
scanf("%d%d",&n,&k); inc(i,1,n)scanf("%d",&x[i]); sort(x+1,x+n+1);
int l=0,r=x[n],ans;
while(l<=r){
int mid=(l+r)>>1,pre=-INF,tot=0; bool f=0;
inc(i,1,n){
if(x[i]-pre>2*mid)tot++,pre=x[i];
if(tot>k){f=1; break;}
}
if(!f)r=mid-1,ans=mid;else l=mid+1;
}
printf("%d",ans);
return 0;
}有N头牛，给M对整数(A,B)，表示牛A认为牛B受欢迎，这种关系具有传递性。求出有多少头牛被所有的牛认为是受欢迎的。N≤10000
因为求的是被所有牛认同的牛，如果该牛不认同任何牛，那么这头牛出度为0，且出度为0的牛有且只有一个否则不存在所求牛。如果这头牛认同别的牛，那么就要求这两头牛互相认同。同时两头牛都是所求牛。因此做个tarjan缩点，缩点后若出度为0的点有多个则没有所求牛，若只有一个那么这个点所表示强连通块里的所有点都是所求牛。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
struct e{int f,t,n;}; e es[60000]; int g[20000],ess;
void pe(int f,int t){es[++ess]=(e){f,t,g[f]}; g[f]=ess;}
int bel[20000],cnt[20000],n,m,sz[20000],tot,low[20000],pre[20000],tim; bool vis[20000],ins[20000];
stack <int> s;
void dfs(int x){
vis[x]=ins[x]=1; s.push(x); low[x]=pre[x]=++tim;
for(int i=g[x];i;i=es[i].n)
if(!vis[es[i].t])dfs(es[i].t),low[x]=min(low[x],low[es[i].t]);
else if(ins[es[i].t])low[x]=min(low[x],pre[es[i].t]);
if(low[x]==pre[x]){
tot++;
while(!s.empty()){
int now=s.top(); s.pop(); bel[now]=tot; sz[tot]++; ins[now]=0; if(now==x)break;
}
}
}
void tarjan(){
while(!s.empty())s.pop(); memset(vis,0,sizeof(vis)); memset(ins,0,sizeof(ins)); memset(sz,0,sizeof(sz));
tot=tim=0; inc(i,1,n)if(! vis[i])dfs(i);
}
void solve(){
memset(cnt,0,sizeof(cnt)); inc(i,1,ess)if(bel[es[i].f]!=bel[es[i].t])cnt[bel[es[i].f]]++; int a=0;
inc(i,1,tot){
if(cnt[i]==0&&a!=0){printf("0\n"); return;}
if(cnt[i]==0)a=i;
}
printf("%d\n",sz[a]);
}
int main(){
scanf("%d%d",&n,&m); ess=0; memset(g,0,sizeof(g));
inc(i,1,m){int a,b; scanf("%d%d",&a,&b); pe(a,b);}
tarjan(); solve();
return 0;
}有n个木块排成一行，有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块，所有油漆刚好足够涂满所有木块。求任意两个相邻木块颜色不同的着色方案。k≤15，ci≤5
解决本题关键是ci≤5，所以以剩余可涂方块数为1,2,3,4,5及上次涂的色这次剩余可涂方块数为状态，做dp就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define mod 1000000007
using namespace std;
ll f[16][16][16][16][16][6],k,c[16],rem[6];
ll dfs(int a,int b,int c,int d,int e,int g){
if(a+b+c+d+e==0)return 1; long long &ff=f[a][b][c][d][e][g];
if(ff!=-1)return ff; ff=0;
if(a)ff=(ff+(ll)(a-(g==1))*dfs(a-1,b,c,d,e,0))%mod;
if(b)ff=(ff+(ll)(b-(g==2))*dfs(a+1,b-1,c,d,e,1))%mod;
if(c)ff=(ff+(ll)(c-(g==3))*dfs(a,b+1,c-1,d,e,2))%mod;
if(d)ff=(ff+(ll)(d-(g==4))*dfs(a,b,c+1,d-1,e,3))%mod;
if(e)ff=(ff+(ll)(e-(g==5))*dfs(a,b,c,d+1,e-1,4))%mod;
return ff;
}
int main(){
scanf("%d",&k); inc(i,1,k)scanf("%d",&c[i]),rem[c[i]]++;
memset(f,-1,sizeof(f)); printf("%lld",dfs(rem[1],rem[2],rem[3],rem[4],rem[5],0));
return 0;
}抢修N个建筑。修理工人一次只能修理一个建筑，如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。求一个能抢修尽可能多的建筑的抢修顺序。
贪心。首先按毁坏时间排序，如果按照当前的时间计算能修好这个建筑，就修好它；如果修不好，就找以前修过的建筑，如果修理时间最长的建筑比它修理时间长，就不修这个建筑，改修当前建筑，使当前时间缩短。这个操作用优先队列维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
struct task{int t1,t2;}; task tasks[200000];
bool cmp(task a,task b){return a.t2<b.t2;}
priority_queue <int> q;
int n,tim,ans,a;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d%d",&tasks[i].t1,&tasks[i].t2); sort(tasks+1,tasks+n+1,cmp); tim=ans=0;
inc(i,1,n){
if(tim+tasks[i].t1<=tasks[i].t2)tim+=tasks[i].t1,q.push(tasks[i].t1),ans++;
else if(!q.empty()&&tasks[i].t1<(a=q.top())&&tim-a+tasks[i].t1<=tasks[i].t2)
tim=tim-a+tasks[i].t1,q.pop(),q.push(tasks[i].t1);
}
printf("%d",ans);
return 0;
}n个钻石，每个都有一个大小，现在将其装进2个盒子里，每个盒子里的钻石最大的与最小的大小不能超过k，问最多能装多少个。n最大50000。
我真傻，真的~首先对大小排序，然后找以i为左端点的可装区间，这个操作两个指针就可以搞，我却以为要二分查找。预处理完了，因为不交错的区间肯定比交错的区间优，所以从n到1递推一下从n到i最大的区间大小是多少，然后枚举每个区间，找到当前区间大小加上右端点+1到n中最大的区间大小中的最大值输出即可。我却以为要找与最大区间不交错的第二大区间，结果WA了好几发，才发现这是错误的贪心QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 60000
using namespace std;
int n,k,sz[maxn],r,cnt[maxn],mx[maxn];
int main(){
scanf("%d%d",&n,&k); inc(i,1,n)scanf("%d",&sz[i]); sort(sz+1,sz+n+1); r=1;
inc(i,1,n){
while(r<=n&&sz[r]-sz[i]<=k)r++; cnt[i]=r-i;
}
mx[n+1]=0; dec(i,n,1)mx[i]=max(mx[i+1],cnt[i]);
int ans=0; inc(i,1,n)ans=max(ans,cnt[i]+mx[i+cnt[i]]); printf("%d",ans);
return 0;
}n个骑士，每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），且有一个战斗力。求从所有的骑士中选出一个骑士之间没有矛盾的骑士军团最大战斗力之和。n最大10e6
厌恶关系实际上是无向的。从每个骑士出发，沿着关系走可以得一个基环树（就是只有一个环，且断了环就会变成一棵树的连通块）。于是先dfs找环，然后断环，分别尝试以去掉的那条边的两个节点u,v为根，作树形dp，将f[u][0]与f[v][0]的最大值计入答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#define ll long long
using namespace std;
bool vis[maxn]; ll f[maxn][2],w[maxn]; int n,bad;
struct e{int f,t,n;}; e es[maxn*2]; int ess,g[maxn];
void pe(int f,int t){
es[++ess]=(e){f,t,g[f]}; g[f]=ess; es[++ess]=(e){t,f,g[t]}; g[t]=ess;
}
void dfs(int x,int fa){
vis[x]=1;
for(int i=g[x];i!=-1;i=es[i].n)if(i!=fa){
if(vis[es[i].t])bad=i;else dfs(es[i].t,i^1);
}
}
ll dp(int x,int fa,int b){
if(f[x][b]!=-1)return f[x][b]; f[x][b]=0; //printf("%d %d %d %d %d\n",x,fa,b,f[x][b]);
for(int i=g[x];i!=-1;i=es[i].n)if(i!=fa&&i!=bad&&i!=(bad^1)){
if(!b)f[x][b]+=max(dp(es[i].t,i^1,0),dp(es[i].t,i^1,1)+w[es[i].t]);
else f[x][b]+=dp(es[i].t,i^1,0);
}
return f[x][b];
}
int main(){
scanf("%d",&n); memset(vis,0,sizeof(vis)); ll ans=0; memset(g,-1,sizeof(g)); ess=-1;
inc(i,1,n){ll a; int b; scanf("%lld%d",&a,&b); w[i]=a; pe(i,b);}
inc(i,1,n)if(!vis[i]){
dfs(i,-1); ll mx=0;
memset(f,-1,sizeof(f)); mx=max(mx,dp(es[bad].f,-1,0));
memset(f,-1,sizeof(f)); mx=max(mx,dp(es[bad].t,-1,0));
ans+=mx;
}
printf("%lld",ans);
}n种牌，第i种牌的数目为ci还有m张鬼。可以用每种牌各一张来组成一套牌，其中一张可以用鬼代替。求最多可组几套牌。n最大50。
其实这道题我不是特别理解。做法是二分可组多少套，累加套数减每个ci的差，如果这个累加和大于m与套数比较的最小值就不为可行解。还要再思考。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a[60],n,m;
bool check(int x){
int y=min(x,m); inc(i,1,n)if(x>a[i]){y-=(x-a[i]); if(y<0)return 0;} return 1;
}
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%d",&a[i]);
int l=0,r=1000000000,ans;
while(l<=r){
int mid=l+((r-l)>>1); if(check(mid))ans=mid,l=mid+1;else r=mid-1;
}
printf("%d",ans);
return 0;
}N个工厂，第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，产品都只能运往编号更大的工厂的仓库，一件产品运送1个单位距离的费用是1。求最小总费用（建造费用+运输费用）。N最大10e6
斜率优化dp。我公式推错了3次QAQ
f[i]=max{f[j]+sigma(k,j+1,i)(x[i]-x[k])*p[k]+c[i]} =max{f[j]+sigma(k,j+1,i)x[i]*p[k]-sigma(k,j+1,i)x[k]*p[k]+c[i]} =max{f[j]+(sump[i]-sump[j])*x[i]-(sumxp[i]-sumxp[j])+c[i]} =max{f[j]+sump[i]*x[i]-sump[j]*x[i]-sumxp[i]+sumxp[j]+c[i]}
f[j]+sump[i]*x[i]-sump[j]*x[i]-sumxp[i]+sumxp[j]+c[i]<f[k]+sump[i]*x[i]-sump[k]*x[i]-sumxp[i]+sumxp[k]+c[i] f[j]-f[k]+sumxp[j]-sumxp[k]<sump[j]*x[i]-sump[k]*x[i] (f[j]-f[k]+sumxp[j]-sumxp[k])/(sump[j]-sump[k])>x[i]（j在k前面）
注意开始是单调队列里要有一个f[0]，因为不需要一定在1处建仓库（本弱和标程对拍才发现这个错误，好弱啊！）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000100
#define ll long long
using namespace std;
ll sump[maxn],sumxp[maxn],f[maxn],c[maxn],x[maxn]; int n,q[maxn],l,r;
double calc(int j,int k){
return (double)(f[j]-f[k]+sumxp[j]-sumxp[k])/(double)(sump[j]-sump[k]);
}
int main(){
scanf("%d",&n); sump[0]=sumxp[0]=0;
inc(i,1,n){
ll p; scanf("%lld%lld%lld",&x[i],&p,&c[i]); sump[i]=sump[i-1]+p; sumxp[i]=sumxp[i-1]+x[i]*p;
}
l=0; r=0; q[l]=0; f[0]=0;
inc(i,1,n){
while(l<r&&calc(q[l],q[l+1])<x[i])l++;
f[i]=f[q[l]]+sump[i]*x[i]-sump[q[l]]*x[i]-sumxp[i]+sumxp[q[l]]+c[i];
while(l<r&&calc(q[r],i)<calc(q[r-1],q[r]))r--; q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}n个顶点，找一个矩形，使其面积最大。注意：矩形的边不一定要和坐标轴平行！
先将点两两组成线段，然后将它们按中点和长度排序，则每组中点和长度都相等的线段两两都可以组成矩形，比较它们的面积就行。求面积用叉积（即两个向量末端点与它们的和末端点组成的平行四边形的面积，公式：x1*y2-x2*y1或|a|*|b|*sin<a,b>）除以2。反思：本蒟蒻正因为加粗部分WA了，而且本题的数据似乎并没有那么大，才能这样写。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2000
#define ll long long
using namespace std;
inline ll sqr(ll a){return a*a;}
struct line{ll x1,y1,x2,y2;}; line lines[maxn*maxn]; int linen;
inline ll length(line a){return sqr(a.x1-a.x2)+sqr(a.y1-a.y2);}
bool cmp(line a,line b){
if(a.x1+a.x2==b.x1+b.x2&&a.y1+a.y2==b.y1+b.y2)
return length(a)<length(b);
else return a.x1+a.x2==b.x1+b.x2?a.y1+a.y2<b.y1+b.y2:a.x1+a.x2<b.x1+b.x2;
}
ll x[maxn],y[maxn]; int n;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%lld%lld",&x[i],&y[i]); linen=0;
inc(i,1,n)inc(j,i+1,n)lines[++linen]=(line){x[i],y[i],x[j],y[j]};
sort(lines+1,lines+1+linen,cmp); ll mx=0;
inc(i,1,linen-1){
line &a=lines[i]; int j=i+1;
while(j<=linen&&length(a)==length(lines[j])&&a.x1+a.x2==lines[j].x1+lines[j].x2&&a.y1+a.y2==lines[j].y1+lines[j].y2)
mx=max(mx,abs((a.x2-a.x1)*(lines[j].y2-lines[j].y1)-(a.y2-a.y1)*(lines[j].x2-lines[j].x1))>>1),j++;
}
printf("%lld",mx); return 0;
}n个装备，每种装备都有2个属性值，分别用[1,10000]之间的数表示。使用某种装备时，只能使用该装备的某一个属性。并且每种装备最多只能使用一次。攻击boss的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。求最多能连续攻击boss多少次。
本题竟然用并查集！把每个装备看成1条无向边，当n条边没有组成一个环时，则一共可以得到n-1个属性，如果n条边组成了一个环，则可以得到n个属性。因此可以使用并查集，根据它除了并操作不会改变根节点的性质，用它维护一个vis数组表示第i个属性能否得到，当一条边插入时，如果两个端点不在一个联通块中，就将根节点表示属性小的那个联通块连到大的那个，并将小的联通块根节点的vis置为1，大的不变；如果在一个联通块中，就将该联通块根节点vis置为1。最后枚举一下vis从1到多少均为1就是答案。
注意：因为我的程序是枚举到vis为0的那个值退出，由于属性最大是10000，所以要枚举到10001。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
bool vis[20000]; int fa[20000],n;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
scanf("%d",&n); inc(i,1,10000)fa[i]=i; memset(vis,0,sizeof(vis));
inc(i,1,n){
int a,b,x,y; scanf("%d%d",&a,&b); x=find(a); y=find(b);
if(x==y)vis[x]=1;else{if(x>y)swap(x,y); fa[x]=y; vis[x]=1;}
}
inc(i,1,10001)if(!vis[i]){printf("%d",i-1); break;}
return 0;
}给定一个连通无向图，假设现在加入一条边权为L的边(u,v)，求需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上。
最小割。如果一个边出现在最小生成树上，那么权值比它小的边一定不能使图联通。因为要求删掉最少，所以当加入这条边后整个图刚好联通。因此可以将这条边的一个端点作为源，另一端点作为汇，插入所以权值比L小的边，每条边流量为1，跑最小割，求出来的答案就是使源、汇不联通最少删掉边。最大生成树同理，插入的是权值比L大的。最后答案是两次跑最小割的结果相加。反思：注意边要开到4倍，而且图中边是无向边，在网络流插边时要插两个方向。这道题也告诉我们实际上数据范围上万的可能也是用网络流。dinic/ISAP的玄学复杂度QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 30000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[maxn*40]; int g[maxn],ess;
inline void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
}
inline void init(){
ess=-1; memset(g,-1,sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
int dinic(int s,int t){
int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;
}
int n,m,u[maxn*10],v[maxn*10],w[maxn*10],U,V,L;
int main(){
scanf("%d%d",&n,&m); inc(i,1,m)scanf("%d%d%d",&u[i],&v[i],&w[i]); scanf("%d%d%d",&U,&V,&L); int ans=0;
init(); inc(i,1,m)if(w[i]<L)pe(u[i],v[i],1),pe(v[i],u[i],1); ans+=dinic(U,V);
init(); inc(i,1,m)if(w[i]>L)pe(u[i],v[i],1),pe(v[i],u[i],1); ans+=dinic(U,V);
printf("%d",ans); return 0;
}一个矩形蛋糕边长分别为X和Y，须切成N块面积相等的蛋糕。每一切只能平行于一块蛋糕的任意一边，并且必须把这块蛋糕切成两块。因此必须切 N-1 次。求 N块蛋糕的长边与短边的比值的最大值的最小值。X，Y≤10000，N≤10
爆搜，dfs(x,y,cnt)表示要把长为x宽为y的蛋糕切成cnt块，因为只能切在x/cnt或y/cnt的倍数的位置上，所以每次枚举切哪个位置就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3fffffff
#define inc(i,j,k) for(double i=j;i<=k;i++)
using namespace std;
double dfs(double x,double y,double cnt){
if(cnt==1)return max(x,y)/min(x,y); double ans=INF;
inc(i,1,cnt-1){
ans=min(ans,max(dfs(x/cnt*i,y,i),dfs(x/cnt*(cnt-i),y,cnt-i)));
ans=min(ans,max(dfs(x,y/cnt*i,i),dfs(x,y/cnt*(cnt-i),cnt-i)));
}
return ans;
}
int x,y,n;
int main(){
scanf("%d%d%d",&x,&y,&n); printf("%.6lf",dfs((double)x,(double)y,(double)n)); return 0;
}n场比赛，知道自己所有选手的能力值和对方所有选手的能力值，能力值大的一定赢。比赛赢一场得2分，平局得1分，输了不得分。对方随机决定选手顺序，你想知道自己最多能得多少分和最少能得多少分。N≤100000
贪心。设一个高分方和低分方，将两方选手按能力排好序。如果高分方目前最强能赢低分方目前最强，就让他们比赛；如果高分方目前最弱能赢低分方目前最弱，也让他们比赛；否则用高分方最弱的和低分方最强的打。开始先让自己方为高分方，求最大值，再让对方做高分方，本方最小值就是2*n-对方得分。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200000
using namespace std;
int a[maxn],b[maxn],n,ans,la,ra,lb,rb;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&a[i]); inc(i,1,n)scanf("%d",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+n);
ans=0; la=1; ra=n; lb=1; rb=n;
inc(i,1,n){
if(a[ra]>b[rb])ra--,rb--,ans+=2;else if(a[la]>b[lb])la++,lb++,ans+=2;else ans+=(a[la]==b[rb]),la++,rb--;
}
printf("%d ",ans); swap(a,b);
ans=0; la=1; ra=n; lb=1; rb=n;
inc(i,1,n){
if(a[ra]>b[rb])ra--,rb--,ans+=2;else if(a[la]>b[lb])la++,lb++,ans+=2;else ans+=(a[la]==b[rb]),la++,rb--;
}
printf("%d",2*n-ans); return 0;
}N个地方，在i处建立通讯中转站需要的成本为Pi。M个用户，第i个用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。求净获利最大值。N≤5000，M≤50000
最小割。源点向所有地方连边，流量为建站成本，第Ai个地方和第Bi个地方分别向第i个用户连边，流量无穷，所有用户向汇点连边，流量为获益。这样割源点与地方的连边表示付出成本，割用户与汇点的连边表示放弃利益。最后答案是所有获益和-最小割。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 60000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[maxn*20]; int g[maxn],ess;
inline void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
}
inline void init(){
ess=-1; memset(g,-1,sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
int dinic(int s,int t){
int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;
}
int n,m,s,t,tot;
int main(){
scanf("%d%d",&n,&m); s=0; t=n+m+1; init();
inc(i,1,n){int a; scanf("%d",&a); pe(s,i,a);}
inc(i,1,m){int a,b,c; scanf("%d%d%d",&a,&b,&c); pe(a,n+i,INF); pe(b,n+i,INF); pe(n+i,t,c); tot+=c;}
printf("%d",tot-dinic(s,t)); return 0;
}N个数，M个询问求区间[L,R]中包含了多少种不同的数。
莫队好像可以做~但正解是树状数组。先将询问按左端点排序，并求出每个数的下一个与它相等的数的位置，同时将每个数第一次出现的位置在树状数组中置为1，此时query(x)求出来的就是1到x里有多少个不同的数。枚举排序后的询问，将当前左端点向右移动，每右移一位就将原位置的数的下一个与它相同的数的位置在树状数组中置为1，保证如果这个数在[l,r]中出现不会漏算。当左端点移动到询问的左端点位置时，就输出query(r)-query(l-1)，表示l到r里有多少个不同的数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50100
#define lb(x) x&-x;
using namespace std;
int a[maxn],last[maxn*20],next[maxn],sm[maxn],n,m;
struct ask{int l,r,ans,id;}; ask asks[maxn*6];
bool cmp1(ask a,ask b){return a.l<b.l;}
bool cmp2(ask a,ask b){return a.id<b.id;}
inline void update(int x,int v){while(x<=n){sm[x]+=v,x+=lb(x);}}
inline int query(int x){int q=0; while(x>0){q+=sm[x],x-=lb(x);} return q;}
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&a[i]);
scanf("%d",&m); inc(i,1,m)scanf("%d%d",&asks[i].l,&asks[i].r),asks[i].id=i;
memset(last,0,sizeof(last)); inc(i,1,n){if(last[a[i]])next[last[a[i]]]=i;else update(i,1); last[a[i]]=i;}
sort(asks+1,asks+1+m,cmp1); int l=1;
inc(i,1,m){
while(l<asks[i].l){if(next[l])update(next[l],1); l++;}
asks[i].ans=query(asks[i].r)-query(asks[i].l-1);
}
sort(asks+1,asks+1+m,cmp2); inc(i,1,m)printf("%d\n",asks[i].ans);
return 0;
}有一个a*b的整数组成的矩阵，求一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。a,b≤1000，n≤100
做4次单调队列。先利用单调队列求出第i行第j列到第i行第j+n-1列的最大最小值，再利用这个求出第i行第j列到第i+n-1行第j+n-1列的最大最小值。最后枚举一下求最小的差就行了。反思：本蒟蒻单调队列开始各种符号写反，比如判断是否要l++的那个条件。以及因为INF设得太小WA了一发，拍都拍不出，最后改成2147483647乱交一发结果过了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1500
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 2147483647
using namespace std;
int maxh[maxn][maxn],minh[maxn][maxn],maxl[maxn][maxn],minl[maxn][maxn];
int v[maxn][maxn],q1[maxn],q2[maxn],a,b,n,l,r,ans;
int main(){
scanf("%d%d%d",&a,&b,&n); inc(i,1,a)inc(j,1,b)scanf("%d",&v[i][j]);
inc(i,1,a){
l=1; r=0;
inc(j,1,n){while(r>=l&&v[i][j]>q1[r])r--; q1[++r]=v[i][j]; q2[r]=j;} maxh[i][1]=q1[l];
inc(j,n+1,b){
if(j-n>=q2[l])l++; while(r>=l&&v[i][j]>q1[r])r--;
q1[++r]=v[i][j]; q2[r]=j; maxh[i][j-n+1]=q1[l];
}
}
inc(i,1,a){
l=1; r=0;
inc(j,1,n){while(r>=l&&v[i][j]<q1[r])r--; q1[++r]=v[i][j]; q2[r]=j;} minh[i][1]=q1[l];
inc(j,n+1,b){
if(j-n>=q2[l])l++; while(r>=l&&v[i][j]<q1[r])r--;
q1[++r]=v[i][j]; q2[r]=j; minh[i][j-n+1]=q1[l];
}
}
inc(j,1,b){
l=1; r=0;
inc(i,1,n){while(r>=l&&maxh[i][j]>q1[r])r--; q1[++r]=maxh[i][j]; q2[r]=i;} maxl[1][j]=q1[l];
inc(i,n+1,a){
if(i-n>=q2[l])l++; while(r>=l&&maxh[i][j]>q1[r])r--;
q1[++r]=maxh[i][j]; q2[r]=i; maxl[i-n+1][j]=q1[l];
}
}
inc(j,1,b){
l=1; r=0;
inc(i,1,n){while(r>=l&&minh[i][j]<q1[r])r--; q1[++r]=minh[i][j]; q2[r]=i;} minl[1][j]=q1[l];
inc(i,n+1,a){
if(i-n>=q2[l])l++; while(r>=l&&minh[i][j]<q1[r])r--;
q1[++r]=minh[i][j]; q2[r]=i; minl[i-n+1][j]=q1[l];
}
}
ans=INF;
inc(i,1,a-n+1)inc(j,1,b-n+1){
ans=min(ans,maxl[i][j]-minl[i][j]);
}
printf("%d",ans); return 0;
}赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好一次。赛车超能电驴在高速航行模式下，沿星际航路航行，但只能由每个星球飞往引力比它大的星球。在能力爆发模式下，超能电驴在经过一段时间的定位之后，能瞬间移动到任意一个行星。求完成比赛最短时间。N≤800，M≤15000
费用流。对每个点拆成X，Y两个点，源向每个Y点连边，流量为1，费用为对这个行星的定位时间，表示直接经过这个行星。源再向每个X点连边流量1，费用0，每个Y点向汇连边，流量1，费用0。X与Y之间按“星际航路”连边，表示从X点到Y点。我们不关心从哪里到这个行星再到哪里去，我们只考虑每个行星只能经过一次。反思：本智障一开始看不懂任何题解，后来发现自己以为是能力爆发模式需要受引力限制，不审题退役QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2000
#define INF 0x3fffffff
using namespace std;
struct e{int f,t,c,w,n;}; e es[maxn*40]; int ess,g[maxn];
inline void pe(int f,int t,int c,int w){
es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
int d[maxn],fr[maxn]; bool inq[maxn]; queue <int> q;
bool spfa(int s,int t){
while(!q.empty())q.pop(); memset(inq,0,sizeof(inq)); memset(d,-1,sizeof(d));
inq[s]=1; d[s]=0; q.push(s); fr[s]=-1;
while(! q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&(d[es[i].t]==-1||d[es[i].t]>d[x]+es[i].w)){
d[es[i].t]=d[x]+es[i].w; fr[es[i].t]=i; if(!inq[es[i].t])inq[es[i].t]=1,q.push(es[i].t);
}
}
return d[t]!=-1;
}
int advanced(int s,int t){
int a=INF,c=0;
for(int i=fr[t];i!=-1;i=fr[es[i].f])a=min(a,es[i].c);
for(int i=fr[t];i!=-1;i=fr[es[i].f])es[i].c-=a,es[i^1].c+=a,c+=(a*es[i].w);
return c;
}
int maxflowmincost(int s,int t){
int c=0; while(spfa(s,t))c+=advanced(s,t); return c;
}
int n,m,s,t;
int main(){
scanf("%d%d",&n,&m); s=0; t=2*n+1; init();
inc(i,1,n){int a; scanf("%d",&a); pe(s,i+n,1,a);}
inc(i,1,m){int a,b,c; scanf("%d%d%d",&a,&b,&c); pe(min(a,b),max(a,b)+n,1,c);}
inc(i,1,n)pe(s,i,1,0),pe(i+n,t,1,0);
printf("%d",maxflowmincost(s,t)); return 0;
}有N个经理，Ei,j表示i经理对j经理的了解程度，当经理i和经理j同时被雇佣时，利润增加Ei,j*2。同时，雇佣每一个经理都需要花费一定的金钱Ai。没有被雇佣的人会被竞争对手所雇佣，使得所赚得的利润减少Ei,j（意思是经理i和j如果只雇佣一个，就会少Ei,j，如果两个都没被雇佣就不扣钱）。求最大利润。N≤1000
S集表示雇佣，T集表示不雇佣。每个经理拆成x，y两点。s向所有x点连，流量为雇佣费用。对于每个Ei,j，i，j经理连一条流量为2*Ei,j的无向边，同时i和j都向t连流量为Ei,j的边，最小割为所有Ei,j*2减最大流。由于边数大，需要合并一下边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 1100
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 1000000000000000000
#define ll long long
using namespace std;
struct e{int t;ll c;int n;}; e es[maxn*2000]; int g[maxn],ess;
inline void pe(int f,int t,ll c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
}
inline void pe2(int f,int t,ll c){
es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess;
}
inline void init(){
ess=-1; memset(g,-1,sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
ll dfs(int x,int t,ll f){
if(x==t)return f; ll u=0;
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
ll w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(u==0)h[x]=-1; return u;
}
ll dinic(int s,int t){
ll f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;
}
int n,s,t; ll a[maxn],b,tot;
int main(){
scanf("%d",&n); s=0; t=n+1; init(); inc(i,1,n)scanf("%lld",&b),pe(s,i,b); memset(a,0,sizeof(a));
inc(i,1,n)inc(j,1,n){
scanf("%lld",&b); if(i>j||b==0)continue; a[i]+=b; a[j]+=b; pe2(i,j,2*b); tot+=2*b;
}
inc(i,1,n)pe(i,t,a[i]); printf("%lld",tot-dinic(s,t)); return 0;
}有N个节点，M个操作：连接两个节点、单个节点的权值增加v、节点所在的连通块的所有节点的权值增加v、所有节点的权值增加v、询问节点当前的权值、询问节点所在的连通块中权值最大的节点的权值、询问所有节点中权值最大的节点的权值。N，M≤300000
可并堆，虽然听说配对堆非常快，但教程太少了不会写，所以去学了斜堆，比较好写。斜堆实际上是一棵二叉树，核心是合并操作，这是一个递归过程，有点像treap的删除操作。斜堆保证复杂度的方法是每次递归合并右节点，合并完后交换左右节点，使整棵树和splay一样，可以“自动”平衡，也是玄学。要修改整个连通块，打标记就行了。这道题特殊的一点在于询问所有节点权值的最大值，可以用STL的set维护所有连通块的根节点，当连边和修改权值时如果根节点被修改需要维护一下set。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 300100
#define INF 0x3fffffff
using namespace std;
int fa[maxn],ch[maxn][2],tg[maxn],v[maxn],n,m,add;
multiset <int> st;
void pushdown(int x){
if(tg[x]){
if(ch[x][0])tg[ch[x][0]]+=tg[x],v[ch[x][0]]+=tg[x];
if(ch[x][1])tg[ch[x][1]]+=tg[x],v[ch[x][1]]+=tg[x];
tg[x]=0;
}
}
int dt[maxn],dts;
int find(int x){
dt[dts=1]=x; while(fa[x])x=fa[x],dt[++dts]=x;
for(int i=dts;i>=1;i--)pushdown(dt[i]); return x;
}
int merge(int x,int y){
if(!x||!y)return x+y; if(v[x]<v[y])swap(x,y); pushdown(x);
ch[x][1]=merge(ch[x][1],y); fa[ch[x][1]]=x; swap(ch[x][0],ch[x][1]); return x;
}
int del(int x){
int t=merge(ch[x][0],ch[x][1]),f=fa[x]; fa[x]=ch[x][0]=ch[x][1]=0;
fa[t]=f; if(f)ch[f][ch[f][1]==x]=t; return t;
}
void update1(int x,int val){
int y=find(x); int t=del(x); v[x]+=val;
if(y!=x){
int z=merge(y,x); st.erase(st.find(v[y])); st.insert(v[z]);
}else{
if(t){
int z=merge(t,x); st.erase(st.find(v[x]-val)),st.insert(v[z]);
}else st.erase(st.find(v[x]-val)),st.insert(v[x]);
}
}
void update2(int x,int val){
x=find(x); tg[x]+=val; v[x]+=val; if(!fa[x])st.erase(st.find(v[x]-val)),st.insert(v[x]);
}
void update3(int val){add+=val;}
int query1(int x){find(x); return v[x];}
int query2(int x){int y=find(x); return v[y];}
int query3(){return * --st.find(INF);}
void connect(int x,int y){
int xx=find(x),yy=find(y); if(xx==yy)return; int z=merge(xx,yy);
if(z==xx)st.erase(st.find(v[yy]));else st.erase(st.find(v[xx]));
}
char opt[3];
int main(){
//freopen("test.txt","r",stdin);
scanf("%d",&n); add=0; st.clear();
inc(i,1,n){
scanf("%d",&v[i]); st.insert(v[i]); fa[i]=ch[i][0]=ch[i][1]=tg[i]=0;
}
scanf("%d",&m);
inc(i,1,m){
scanf("%s",opt); int x,y;
if(opt[0]=='U')scanf("%d%d",&x,&y),connect(x,y);
if(opt[0]=='A'){
if(opt[1]=='1')scanf("%d%d",&x,&y),update1(x,y);
if(opt[1]=='2')scanf("%d%d",&x,&y),update2(x,y);
if(opt[1]=='3')scanf("%d",&x),update3(x);
}
if(opt[0]=='F'){
if(opt[1]=='1')scanf("%d",&x),printf("%d\n",query1(x)+add);
if(opt[1]=='2')scanf("%d",&x),printf("%d\n",query2(x)+add);
if(opt[1]=='3')printf("%d\n",query3()+add);
}
//if(i==2)break;
}
return 0;
}n个点组成一棵树，每个点都有一个领导力和费用，可以让一个点当领导，然后在这个点的子树中选择一些费用之和不超过m的点，得到领导的领导力乘选择的点的个数（领导可不被选择）的利润。求利润最大值。n≤100000
可并堆。可以得到一个结论，就是在子树中选点的时候，先选所有点，如果费用超了，就不断把费用最大的剔除，直到费用不超，这样得到的选点数量最大，这过程可以用堆维护。同时每个点的堆都可以由子树的堆合并得到，所以需要可并堆。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100100
#define ll long long
using namespace std;
int ch[maxn][2],rt[maxn],n,m,st; ll sz[maxn],v[maxn],ans,sm[maxn],gd[maxn];
struct e{int t,n;}; e es[maxn]; int ess,g[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
void init(){ess=0; memset(g,0,sizeof(g));}
void update(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; sm[x]=sm[ch[x][0]]+sm[ch[x][1]]+v[x];}
int merge(int x,int y){
if(!x||!y)return x+y; if(v[x]<v[y])swap(x,y); ch[x][1]=merge(ch[x][1],y);
swap(ch[x][0],ch[x][1]); update(x); return x;
}
void pop(int &x){
int y=merge(ch[x][0],ch[x][1]); ch[x][0]=ch[x][1]=0; sz[x]=1; sm[x]=v[x]; x=y;
}
void dfs(int x){
rt[x]=x; for(int i=g[x];i;i=es[i].n)dfs(es[i].t),rt[x]=merge(rt[x],rt[es[i].t]);
while(sz[rt[x]]&&sm[rt[x]]>m)pop(rt[x]); ans=max(ans,sz[rt[x]]*gd[x]);
}
int main(){
scanf("%d%d",&n,&m); init();
inc(i,1,n){
int a; ll b,c; scanf("%d%lld%lld",&a,&b,&c); if(a)pe(a,i);else st=i;
v[i]=sm[i]=b; sz[i]=1; gd[i]=c; ch[i][0]=ch[i][1]=rt[i]=0;
}
ans=0; dfs(st); printf("%lld",ans); return 0;
}n天，每天得到一个值，要求输出每一天和这天得到的值相差最小的之前天得到的值与这个值的差的和。n不知道，不过O(nlog2n)可写。
说是平衡树模板题，不过可以用set水过去。先在set插入一个-INF和INF防溢出（yyl大爷教我的）每次在set中lower_bound这天得到的值，求出的是≤它的最大值，比较一下这个值和set中这个值的后继与这天得到的值的差。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define INF 2147483647
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,ans,x; set <int> st;
int main(){
scanf("%d",&n); st.clear(); st.insert(INF); st.insert(-INF); ans=0;
inc(i,1,n){
scanf("%d",&x);
if(i==1)ans+=x;else{
int y=* (st.lower_bound(x)),z=* (--st.lower_bound(x)); //printf("%d %d\n",y,z);
if(y==INF)ans+=abs(x-z);else if(z==-INF)ans+=abs(x-y);else ans+=min(abs(x-z),abs(x-y));
}
st.insert(x);
}
printf("%d",ans); return 0;
}修n-1条公路将n个点连通，每个点可建一级公路也可建二级公路，要求一级公路必须有k条，要求花费最多的公路花费最少。
首先二分最大花费，接着判定：先在不产生环的前提下（用并查集维护）让每条路尽量修一级公路，如果最后无法构成树则考虑修二级公路。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10500
using namespace std;
int n,k,m,u[maxn*2],v[maxn*2],c1[maxn*2],c2[maxn*2],mx,fa[maxn],cnt;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
bool check(int lim){
inc(i,1,n)fa[i]=i; cnt=0;
inc(i,1,m)if(c1[i]<=lim){
int x=find(u[i]),y=find(v[i]); if(x==y)continue; fa[y]=x; cnt++;
}
if(cnt<k)return 0;
inc(i,1,m)if(c2[i]<=lim){
int x=find(u[i]),y=find(v[i]); if(x==y)continue; fa[y]=x; cnt++;
}
if(cnt<n-1)return 0; return 1;
}
int main(){
scanf("%d%d%d",&n,&k,&m); mx=0;
inc(i,1,m-1)scanf("%d%d%d%d",&u[i],&v[i],&c1[i],&c2[i]),mx=max(mx,c1[i]),mx=max(mx,c2[i]);
int l=0,r=mx,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;else l=mid+1;
}
printf("%d",ans); return 0;
}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。