估分：80+0+80
实际：0+0+40
心态爆炸
给出一颗有n个节点的无根树，每个节点是黑色，白色或灰色，删去一些边使剩余每个连通块中要么不含黑色节点，要么不含白色节点，求删去边的权值和最小
有T组数据
n<=300000;T<=5
明显是树形dp，但是我方程推错了
事实上，对于每个节点，只需记录三种状态：
有0个黑点和任意个白点有任意个黑点和0个白点有任意个黑点和1个白点随便转移就好了
给出一个n个点，m条边的无向连通图，第i个点的权值为ai。删去一些边使点1到n任意一条最短路径上至少有一条边被删除，删去每条边（x，y）的代价为a[x]或a[y]。
求最小的代价即最优方案是否唯一。
2<=n<=400,2<=m<=4000,无向图可能有重边，不超过5组数据。
最小割裸题。
首先建出最短路图。我们只需要在最短路图上删去若干条边使1到n不连通即可。
但是边(x,y)的权值可能是a[x]也可能是a[y]怎么办呢？
把边拆成(x,z)与(z,y),(x,z)的流量为a[x],(z,y)的流量为a[y]即可
这样跑一下就会有40分的好成绩了
判断最优方案是否唯一就是研究最小割是否有唯一解。
这是本题重点。
先跑出残量网络，找出S集和T集。
（若从S走流量不为0的边能走到x，则x在S集；若从T跑 流量不为0的边 的反向弧 能走到x则x在y集）
枚举每一条边，若这条边连接的x,y分别在S集与T集，则这条边是必割边
若全部必割边的流量之和为最小割，则方案唯一。
如果残量网络中存在长度大于2的有向环，则方案不唯一
这时在环上增减流量可以得到不同解而方案不变。
对于一个整数序列，查询区间第k大数可以在O(logN)的时间内轻松完成。现在我们对这个问题进行推广。
考虑带重复数的集合（multiset）。定义在该类集合上的并操作“+”为两个集合的所有数不剔除重复得到的结果。比如，若A={1,2,2,3}，B={2,3,4,4}，则C={1,2,2,2,3,3,4,4}。对于一个给定序列A[1..N]，定义A[x..y]为包含y-x+1个元素的集合{A[x],A[x+1],…,A[y]}。现在，给定整数序列A，你需要回答很多询问，其中第i个询问要求集合A[x[i,1]..y[i,1]]+A[x[i,2]..y[i,2]]+…+A[x[i,ki]..y[i,ki]]中第pi小的元素。
所有的测试点满足N ≤ 200 000，M ≤ 200 000，0 ≤ A[i] ≤ 1 000 000，ki ≤ 5。
保证1 ≤ x[i, j] ≤ N，1 ≤ y[i, j] ≤ N，1 ≤ pi ≤ ∑j(y[i, j] - x[i, j] + 1)。
比赛时建了主席树，但是只会二分然后枚举每一段，带两个节点进去，O(\(nlog^2n\))只有40分
带十个节点进去，在主席树上面二分即可
O(\(nlogn\))
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct qy { int ch[2],sum; }; int n,m,i,j,k,p,tot,l,r,mid,ans; int a[200005],root[200005],x[10],y[10]; int k1[15],k2[15]; qy tree[6000005]; void insert(int k1,int k2,int l,int r,int x) { if (l==r) { tree[k2].sum++; } else { int mid=(l+r)/2; tree[k2].ch[0]=tree[k1].ch[0]; tree[k2].ch[1]=tree[k1].ch[1]; if (x<=mid) { tree[k2].ch[0]=++tot; tree[tot]=tree[tree[k1].ch[0]]; insert(tree[k1].ch[0],tree[k2].ch[0],l,mid,x); } else { tree[k2].ch[1]=++tot; tree[tot]=tree[tree[k1].ch[1]]; insert(tree[k1].ch[1],tree[k2].ch[1],mid+1,r,x); } tree[k2].sum=tree[tree[k2].ch[0]].sum+tree[tree[k2].ch[1]].sum; } } int query(int k,int l,int r,int x)//重点 { if (l==r) return l; else { int s=0,mid=(l+r)/2; for (int i=1;i<=k;i++)//把2k个节点的和一起计算 s=s+tree[tree[k1[i]].ch[0]].sum-tree[tree[k2[i]].ch[0]].sum; if (s>=x) { for (int i=1;i<=k;i++) { k1[i]=tree[k1[i]].ch[0]; k2[i]=tree[k2[i]].ch[0]; } return query(k,l,mid,x); } else { for (int i=1;i<=k;i++) { k1[i]=tree[k1[i]].ch[1]; k2[i]=tree[k2[i]].ch[1]; } return query(k,mid+1,r,x-s); } } } int read() { int sum=0;char ch=getchar(); while ((ch<'0')||(ch>'9')) ch=getchar(); while ((ch>='0')&&(ch<='9')) { sum=sum*10+ch-'0'; ch=getchar(); } return sum; } int main() { freopen("read.in","r",stdin); // freopen("write.out","w",stdout); scanf("%d%d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",&a[i]); root[i]=++tot; insert(root[i-1],root[i],0,1000000,a[i]); } for (i=1;i<=m;i++) { k=read(); p=read(); for (j=1;j<=k;j++) x[j]=read(),y[j]=read(); for (j=1;j<=k;j++) { k1[j]=root[y[j]]; k2[j]=root[x[j]-1]; } ans=query(k,0,1000000,p); printf("%d\n",ans); } }xzb下午没人叫起床
dyp帮忙打开屏幕，zzx帮忙打开C++，结果没被xc发现
xzb15：53才到教室
转载于:https://www.cnblogs.com/leason-lyx/p/11165083.html
