北京集训简要题解集合
shadowice1984
2018-12-25 19:44:43
rt,这里是一句话题解博客，仅限我看的懂的水平qwq……
由于我太菜了会的题并不是很多………求轻拍
### 12/17
#### T3:dist
给定一个图，并且告诉你有一些团这些团之间的点都连接着权为c(i)的边，求所有点对的最短路之和
$$n \leq 10^5,k\leq 18$$
由于我们的团的个数十分的小只有18个，因此我们可以将每个团拆个虚点出来然后用floyd处理出虚点间的最短路
容易看出计算两个点间的最短路就是枚举所有的虚点对进行松弛的过程
接下来枚举每一个点计算这些点出发的最短路，对于每一个出点v计算出假如有v的最短路然后排序，问题转化为一个给定优先级下lowbit计数问题，可以枚举超集相减来做，fwt即可，注意去重和除2问题
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;const int N=1e5+10;const int M=262144+10;typedef unsigned long long ll;
ll cnt[M];int al[N];ll dis[30][30];bitset <N> su[20];bitset <N> zer;
ll we[30];ll ans;int n;int m;
struct data{int bit;ll val;friend bool operator <(data a,data b){return a.val<b.val;}}q[30];
inline void fwt(ll* a,int len)
{
for(int k=1;k<len;k<<=1)
for(int s=0;s<len;s+=(k<<1))
for(int i=s;i<s+k;i++)a[i+k]+=a[i];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0,t;i<m;i++)
{
scanf("%lld",&we[i]),scanf("%d",&t);
for(int j=1,u;j<=t;j++)scanf("%d",&u),al[u]|=(1<<i),su[i][u]=1;
}for(int i=1;i<=n;i++)cnt[al[i]]++;
for(int i=0;i<m;i++)for(int j=0;j<m;j++)dis[i][j]=(1LL<<50);
for(int i=0;i<m;i++)dis[i][i]=0;
for(int i=0;i<m;i++)
for(int j=0;j<i;j++)if((su[i]&su[j])!=zer)dis[i][j]=dis[j][i]=we[i]+we[j];
for(int k=0;k<m;k++)
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
fwt(cnt,(1<<m));
for(int i=1;i<=n;i++)
{
for(int p=0;p<m;p++)
{
q[p].val=(1LL<<50);q[p].bit=p;
for(int t=0;t<m;t++)
if((al[i]>>t)&1)q[p].val=min(q[p].val,we[p]+we[t]+dis[p][t]);
q[p].val/=2;
}sort(q,q+m);int s=0;
for(int p=0;p<m;p++)
{
ans+=(ll)q[p].val*cnt[((1<<m)-1)^s];
s|=(1<<q[p].bit),ans-=(ll)q[p].val*cnt[((1<<m)-1)^s];
}
}
for(int i=1;i<=n;i++)
{
ll miv=(1LL<<50);
for(int p=0;p<m;p++)if((al[i]>>p)&1)miv=min(miv,we[p]);
ans-=miv;
}
printf("%lld",ans/2);return 0;
}
```
### 12/18
#### T3:tvt
给定一颗树，有两个人分别走在$(u1,v1),(u2,v2)$这两条路径出发，出发时间分别是$t1,t2$,速度均为1,多组询问你这两个人会不会在同一条边上相遇，在同一个点上相遇不算
$n \leq 10^ 5,q\leq 10^5$
并不会lca路径求交的高论做法，我是直接把两个路径拆成了log条重链判交，如果都是一条重链上的话需要判一下同向还是异向，然后决定是去查树上距离还是树上最大值，然后稍微搞一下就行了
注意特判异向的时候两个人撞在同一个点的情况
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
ll dis[N];int v[N<<1];int x[N<<1];int ct;int al[N];ll val[N<<1];int top[N];
int dep[N];int fa[N][22];int n;int q;ll mx[N][22];int h[N];int siz[N];
char mde[N][20];
inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
inline void dfs(int u)
{
for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i];
for(int i=0;fa[u][i];i++)mx[u][i+1]=max(mx[u][i],mx[fa[u][i]][i]);
for(int i=al[u];i;i=x[i])
if(v[i]!=fa[u][0])fa[v[i]][0]=u,mx[v[i]][0]=val[i],
dis[v[i]]=dis[u]+val[i],dep[v[i]]=dep[u]+1,dfs(v[i])
,siz[u]+=siz[v[i]],h[u]=(siz[v[i]]>siz[h[u]])?v[i]:h[u];siz[u]++;
}
inline void dfs2(int u)
{
top[u]=top[u]?top[u]:u;if(h[u])top[h[u]]=top[u],dfs2(h[u]);
for(int i=al[u];i;i=x[i])if(v[i]!=fa[u][0]&&v[i]!=h[u])dfs2(v[i]);
}
inline int lca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);for(int d=dep[u]-dep[v],i=0;d;d>>=1,i++)if(d&1)u=fa[u][i];
if(u==v)return u;for(int i=18;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
inline int qmx(int u,int d)
{
ll ans=-1;for(int i=0;d;d>>=1,i++)if(d&1)ans=max(ans,mx[u][i]),u=fa[u][i];
return ans;
}
inline int cmi(const int& x,const int& y){return (dep[x]<dep[y])?x:y;}
inline int cmx(const int& x,const int& y){return (dep[x]<dep[y])?y:x;}
inline ll mabs(ll x,ll y){return (x>y)?x-y:y-x;}
inline bool jud(int u1,int v1,ll t1,int u2,int v2,ll t2)
{
// printf("jud %d %d %lld %d %d %lld\n",u1,v1,t1,u2,v2,t2);
if(u1==v1||u2==v2)return false;
int tw1;if(dep[u1]<dep[v1])swap(u1,v1),tw1=0;else tw1=1;
int tw2;if(dep[u2]<dep[v2])swap(u2,v2),tw2=0;else tw2=1;
int mu=cmi(u1,u2);int mv=cmx(v1,v2);if(dep[mu]<=dep[mv])return false;
if(tw1)t1+=dis[u1]-dis[mu];else t1+=dis[mv]-dis[v1];
if(tw2)t2+=dis[u2]-dis[mu];else t2+=dis[mv]-dis[v2];
if(tw1^tw2)
{
// printf("CASE A: t1=%lld,t2=%lld\n",t1,t2);
ll del=dis[mu]-dis[mv]-mabs(t1,t2);if(del<=0)return false;
// printf("tdel=%lld,tw1=%d,tw2=%d\n",del,tw1,tw2);
if(del&1)return true;del>>=1;int p=mu;
if((t1>t2)^(tw1))del+=mabs(t1,t2);
// printf("del=%lld\n",del);
for(int i=18;i>=0;i--)if(fa[p][i]&&dis[mu]-dis[fa[p][i]]<=del)p=fa[p][i];
// printf("mdel=%lld\n",dis[mu]-dis[p]);
return (dis[mu]-dis[p]!=del);
}else return mabs(t1,t2)<qmx(mu,dep[mu]-dep[mv]);
}
struct data{int u;int v;ll t;}pos[N];ll tim[N];int book[N];
inline bool qry(int u1,int v1,ll t1,int u2,int v2,ll t2)
{
//printf("qry %d %d %lld %d %d %lld\n",u1,v1,t1,u2,v2,t2);
//printf("top[2]=%d\n",top[2]);
if(u1==v1||u2==v2)return false;
if(dep[u1]>=dep[v1])
{
int p;ll cur=t1;int nx;
//printf("top1[%d]=%d,top=%d\n",u1,top[u1],top[v1]);
for(p=u1;top[p]!=top[v1];p=fa[top[p]][0])
{
nx=top[p];book[nx]=2;pos[nx]=(data){p,nx,cur};cur+=dis[p]-dis[nx];
tim[nx]=cur;cur+=mx[nx][0];
}//printf("p=%d,top[2]=%d\n",p,top[2]);
if(p!=v1)book[top[v1]]=1,pos[top[v1]]=(data){p,v1,cur};
}
else
{
int p;ll cur=t1+dis[v1]-dis[u1];int nx;
for(p=v1;top[p]!=top[u1];p=fa[top[p]][0])
{
nx=top[p];book[nx]=2;cur-=dis[p]-dis[nx];pos[nx]=(data){nx,p,cur};
cur-=mx[nx][0];tim[nx]=cur;
}if(p!=u1)book[top[u1]]=1,pos[top[u1]]=(data){u1,p,t1};
}bool ret=false;
if(dep[u2]>=dep[v2])
{
int p;ll cur=t2;int nx;
for(p=u2;top[p]!=top[v2];p=fa[top[p]][0])
{
nx=top[p];if(book[nx])ret|=jud(pos[nx].u,pos[nx].v,pos[nx].t,p,nx,cur);
cur+=dis[p]-dis[nx];if(book[nx]==2)ret|=(mabs(tim[nx],cur)<mx[nx][0]);
cur+=mx[nx][0];
}//printf("p=%d,top[2]=%d\n",p,top[2]);
if(p!=v2&&book[top[v2]])nx=top[v2],ret|=jud(pos[nx].u,pos[nx].v,pos[nx].t,p,v2,cur);
//printf("p=%d,top[2]=%d\n",p,top[2]);
}
else
{
int p;int nx;ll cur=t2+dis[v2]-dis[u2];
for(p=v2;top[p]!=top[u2];p=fa[top[p]][0])
{
nx=top[p];cur-=dis[p]-dis[nx];if(book[nx])ret|=jud(pos[nx].u,pos[nx].v,pos[nx].t,nx,p,cur);
cur-=mx[nx][0];if(book[nx]==2)ret|=(mabs(tim[nx],cur)<mx[nx][0]);
}if(p!=u2&&book[top[u2]])nx=top[u2],ret|=jud(pos[nx].u,pos[nx].v,pos[nx].t,u2,p,t2);
}
if(dep[u1]>=dep[v1])
{for(int p=u1;top[p]!=top[v1];p=fa[top[p]][0])book[top[p]]=0;book[top[v1]]=0;}
else {for(int p=v1;top[p]!=top[u1];p=fa[top[p]][0])book[top[p]]=0;book[top[u1]]=0;}
return ret;
}
int main()
{
// freopen("tvt9.out","r",stdin);int CNT=1;
// while(scanf("%s",mde[CNT]+1)!=-1)++CNT;
// system("fc tvt9.out ntst.txt");return 0;
// freopen("tvt9.in","r",stdin);freopen("ntst.txt","w",stdout);
scanf("%d%d",&n,&q);ll va;
for(int i=2,u,v;i<=n;i++)scanf("%d%d%lld",&u,&v,&va),add(u,v,va),add(v,u,va);
dfs(1);dfs2(1);ll t1;ll t2;
// for(int i=1;i<=n;i++)printf("%d ",top[i]);printf("\n");
for(int i=1,u1,v1,u2,v2;i<=q;i++)
{
scanf("%d%d%lld%d%d%lld",&u1,&v1,&t1,&u2,&v2,&t2);
// printf("qry %d %d %lld %d %d %lld\n",u1,v1,t1,u2,v2,t2);
int lc1=lca(u1,v1);int lc2=lca(u2,v2);
// printf("%s ",mde[i]+1);
if(qry(u1,lc1,t1,u2,lc2,t2)){
printf("YES\n");
// if(mde[i][1]!='Y')goto stp;
continue;}
if(qry(u1,lc1,t1,lc2,v2,t2+dis[u2]-dis[lc2])){printf("YES\n");
// if(mde[i][1]!='Y')goto stp;
continue;}
if(qry(lc1,v1,t1+dis[u1]-dis[lc1],u2,lc2,t2)){printf("YES\n");
// if(mde[i][1]!='Y')goto stp;
continue;}
if(qry(lc1,v1,t1+dis[u1]-dis[lc1],lc2,v2,t2+dis[u2]-dis[lc2]))
{printf("YES\n");
// if(mde[i][1]!='Y')goto stp;
continue;}printf("NO\n");//if(mde[i][1]!='N')goto stp;
// continue;
// stp:;int k;while(1)k++;
}return 0;
}
```
### 12/19
~~LCA题做不来的，告辞~~
### 12/20
~~哦三道思博题，我相信没有写题解的必要~~
### 12/21
#### t1:yjqa
给你一个电梯，有一堆人要上楼，第i个人会在t时刻到达需要上a层，你需要把这些人分好几车运上去，问你如何运人消耗时间最短
$$n \leq 10^5 $$
稍微推推式子会发现答案和a的后缀最大值，显然拿单调队列维护这个分段函数，由于dp数组是单调的所以需要资瓷弹出操作，查区间最大值写个st表就行了
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int t[N];int a[N];ll dp[N];
namespace st_t
{
ll st[N][22];int lg[N];
inline void clg()
{for(int i=1,j=0;i<=n;j++){if((1<<(j+1))<=i)j++;lg[i]=j;}}
inline void ins(int pos,ll val)
{
st[pos][0]=val;
for(int i=1,k=2;pos-k>=0;i++,k<<=1)
st[pos][i]=min(st[pos][i-1],st[pos-(k>>1)][i-1]);
}
inline ll qmi(int l,int r)
{int j=lg[r-l+1];return min(st[r][j],st[l+(1<<j)-1][j]);}
}
struct data
{
int l;int r;int val;ll fv;
friend data operator +(data a,data b)
{
int nv=max(a.val,b.val);
return (data){a.l,b.r,nv,(nv<<1)+st_t::qmi(a.l,b.r)};
}
inline void pop(){l++;fv=(val<<1)+st_t::qmi(l,r);}
}qu[3*N];int hd;int tl;multiset <ll> ans;
inline void ins(data a){
//printf("ins (%d,%d)\n",a.l,a.r);
qu[++tl]=a;ans.insert(a.fv);}
inline void pophd()
{
// printf("dec (%d,%d)\n",qu[hd].l,qu[hd].r);
ans.erase(ans.find(qu[hd].fv));
if(qu[hd].l==qu[hd].r){hd++;return;}
qu[hd].pop();ans.insert(qu[hd].fv);
}
inline void poptl(){
//printf("pop (%d,%d)\n",qu[tl].l,qu[tl].r);
ans.erase(ans.find(qu[tl].fv));tl--;}
int dq[3*N];int hd1;int tl1;
int main()
{
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
st_t::clg();scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&a[i]);//ll mx=0;
// for(int i=1;i<=n;i++){mx=max(mx,(ll)a[i]);dp[i]=t[i]+(mx<<1);}
hd=1;tl=0;hd1=1;tl1=0;
for(int i=1,j=0;i<=n;i++)
{
data nw=(data){i-1,i-1,a[i],dp[i-1]+(a[i]<<1)};st_t::ins(i-1,dp[i-1]);
while(hd<=tl&&qu[tl].val<=nw.val)nw=qu[tl]+nw,poptl();ins(nw);
while(hd1<=tl1&&a[dq[tl1]]<=a[i])tl1--;dq[++tl1]=i;
while(j!=i&&dp[j]<=t[i])pophd(),j++;
while(hd1<=tl1&&dq[hd1]<j)hd1++;
if(ans.empty())dp[i]=t[i]+(ll)(a[dq[hd1]]<<1);
else dp[i]=min(*ans.begin(),t[i]+(ll)(a[dq[hd1]]<<1));
// printf("dp[%d]=%lld\n",i,dp[i]);
}//mx=0;
//ll ret=(1LL<<50);ll mit=(1LL<<50);
printf("%lld",dp[n]);
// for(int i=1;i<=n;i++)
// {
// printf("%lld ",dp[i]);
// if(i%5==0)printf("\n");
// }printf("\n");
// for(int i=n;i>=1;i--)
// {
// mx=max(mx,(ll)a[i]);ll nit=max(dp[i-1],(ll)t[n])+mx;ll ncs=nit+mx;
// if(nit<mit){mit=nit;ret=ncs;}else if(nit==mit)ret=min(ret,ncs);
// }printf("%lld",ret);
return 0;
}
```
#### t2:yjqb
51nod 小C的二分图
考虑大力$dp(i,j)$表示两个匹配点分别在i和j时的最大匹配，然后我们将i不停的增量然后维护dp(j)数组，此时我们会发现转移涉及到取max操作，既然如此我们就维护前向差分数组这样区间加取后缀max就变成了插入差分点和弹出第一个差分点
具体点来讲我们需要支持插入删除区间加，写个spaly就可以了
注意一件事情是splay查找前驱后继的时候splay最底侧的点而不是前驱和后继否则复杂度退化，另外提取区间的时候给一个提根另一个提到根的儿子位置不然双旋的时候会gg
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e5+10;typedef long long ll;
int n;int pr[N];
struct splaytree
{
int s[N][2];int ct;int fa[N];int val[N];int add[N];int st[N];int tp;int rot;
splaytree()
{ct=2;val[1]=-0x3f3f3f3f;val[2]=0x3f3f3f3f;rot=2;s[2][0]=1;fa[1]=2;}
inline int gc(const int& x){return s[fa[x]][1]==x;}
inline void fpri(int p)
{
pd(p);if(s[p][0])fpri(s[p][0]);
printf("%d ",val[p]);
//if(p!=1&&p!=2){pr[val[p]]=1;}
if(s[p][1])fpri(s[p][1]);
}
inline void pd(const int& x)
{
if(add[x]==0)return;
if(s[x][0])val[s[x][0]]+=add[x],add[s[x][0]]+=add[x];
if(s[x][1])val[s[x][1]]+=add[x],add[s[x][1]]+=add[x];add[x]=0;
}
inline void rt(const int& x)
{
int d=fa[x];int t=gc(x);s[d][t]=s[x][t^1];fa[s[x][t^1]]=d;
s[fa[d]][gc(d)]=x;fa[x]=fa[d];s[x][t^1]=d;fa[d]=x;
}
inline void rtup(const int& x){rt((gc(x)^gc(fa[x]))?x:fa[x]);rt(x);}
inline void splay(const int& x)
{
tp=0;for(int p=x;p;p=fa[p])st[++tp]=p;while(tp)pd(st[tp--]);
// printf("bf splay %d:",x);fpri(rot);printf("\n");
for(;fa[x]&&fa[fa[x]];rtup(x));if(fa[x])rt(x);rot=x;
// printf("af splay %d:",x);fpri(rot);printf("\n");
}
inline void splay1(const int& x)
{
//printf("splay1 %d %d\n",x,rot);
if(rot==x){return;}
tp=0;for(int p=x;p;p=fa[p])st[++tp]=p;while(tp)pd(st[tp--]);
for(;fa[x]!=rot&&fa[fa[x]]!=rot;rtup(x));if(fa[x]!=rot)rt(x);
}
inline void ins(const int& va)
{
int p=rot;int tw;
for(pd(p),tw=s[p][val[p]<va];tw;p=tw,pd(p),tw=s[p][val[p]<va]);
val[++ct]=va;fa[ct]=p;s[p][val[p]<va]=ct;splay(ct);
}
inline int fmi(int x){for(;s[x][0];x=s[x][0]);return x;}
inline int pre(const int& va)
{
int ret=1;int p=rot;int lst=rot;
while(p){pd(p);lst=p;if(val[p]<va)ret=p,p=s[p][1];else p=s[p][0];}
splay(lst);return ret;
}
inline int suc(const int& va)
{
int ret=2;int p=rot;int lst=rot;
while(p){pd(p);lst=p;if(val[p]<va)p=s[p][1];else ret=p,p=s[p][0];}
splay(lst);return ret;
}
inline void setadd(int l,int r)
{
if(l>r)return;
//printf("set add %d %d:",l,r);
//fpri(rot);printf("\n");
r=suc(r+1);l=pre(l-1);splay(r);splay1(l);
if(s[l][1])add[s[l][1]]++,val[s[l][1]]++;
//printf("aft:");fpri(rot);printf("\n");
}
inline void solve(int l,int r)
{int p=suc(r);if(p!=2)del(p);setadd(l,r-1);ins(l);}
inline int dfs(int p)
{
int ret=1;if(s[p][0])ret+=dfs(s[p][0]);
if(s[p][1])ret+=dfs(s[p][1]);return ret;
}
inline void cpr()
{
for(int i=1;i<=n;i++)pr[i]=0;
fpri(rot);printf("\n");
//for(int i=1;i<=n;i++)printf("%d ",pr[i]);printf("\n");
}
inline void del(const int p)
{
if(p==0)return;splay(p);splay(fmi(s[p][1]));
fa[s[p][0]]=rot;s[rot][0]=s[p][0];return;
}
}sp;
int main()
{
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
scanf("%d",&n);
for(int i=1,l,r;i<=n;i++)
{
scanf("%d%d",&l,&r),sp.solve(l,r);//sp.cpr();
}
printf("%d",sp.dfs(sp.rot)-2);return 0;
}
```
### 12/23
#### t3 yjqcc
哦这可真是道恶心题……
对一个矩阵执行以下两种操作，将第l行到第r行染成一种颜色，将第l列到第r列染成同一种颜色，最后询问你这个矩阵里有多少个无序点对满足以下条件
1.他们的颜色一样
2.他们行相邻或者列相邻或者角相邻
$$n,m,q \leq 10^5$$
首先线段树处理出每个点的最晚覆盖时间，然后接下来一行一行的处理，剩余的点可以将矩阵横行翻转之后做个转置然后求剩下的
同一行的比较好说，随便扫描线几下就行了
对于对角线的情况，平移一下变成列相邻的情况然后接下来我们需要处理一堆二元组询问$(t1,t2)$表示第一行在时间t1而第二行在时间t2的情况
接下来我们看看我们能不能把$(t1,t2)$快速的++--这样就能够跑莫队了
答案是可行的，我们把每一个点挂在他的改变时间上，这样我们可以暴力for一下这个时间点的上的询问来做到
不过此时我们的复杂度是均摊的复杂度会假……
不要紧分块的时候按照根号m一个询问分块就可以保证每个点最多被扫根号m次这样复杂度就是针的
~~数据造的很水，居然跑得比树状数组块~~
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=1e5+10;const int B=310;typedef long long ll;
int al[N];int ar[N];int cnt[N];int ucnt[N];int dcnt[N];
int n;int m;int q;int typ;ll pans;ll nans;int bi[N];
struct data
{
int tim;int c;
friend bool operator <(data a,data b){return a.tim<b.tim;}
}ac[N],arw[N],tr2[N];
struct linetree
{
data v[4*N];
inline void pd(int p){v[p<<1]=max(v[p<<1],v[p]);v[p<<1|1]=max(v[p<<1|1],v[p]);}
inline void setv(int p,int l,int r,int dl,int dr,data va)
{
if(dl==l&&dr==r){v[p]=va;return;}int mid=(l+r)/2;
if(dl<mid)setv(p<<1,l,mid,dl,min(dr,mid),va);
if(mid<dr)setv(p<<1|1,mid,r,max(dl,mid),dr,va);
}
inline void dfs(int p,int l,int r,data* op)
{
if(r-l==1){op[r]=v[p];return;}int mid=(l+r)/2;pd(p);
dfs(p<<1,l,mid,op);dfs(p<<1|1,mid,r,op);
}inline void clr(int lim){for(int i=1;i<=(lim<<2);i++)v[i]=(data){0,0};}
}lt;
struct gr
{
int v[N];int x[N];int al[N];int ct;
inline void add(int u,int V){
// printf("add %d %d\n",u,V);
v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void clear(){for(int i=0;i<=q+5;i++)al[i]=0;ct=0;}
}g;int row_col;
inline void rvl(const int& pos,const int& nw)
{
// printf("rvl %d %d\n",pos,nw);
if(pos>m)return;int nw1=ar[pos];
if(al[pos]==-1)
{if(nw1==-1)pans--,dcnt[nw]++;else ucnt[nw1]--,nans+=(nw==nw1);}
else
{if(nw1==-1)pans++,dcnt[nw]--;else nans-=(nw==nw1),ucnt[nw1]++;}
//printf("rvl %d %d %d %d\n",pos,nw,nw1,nans);
al[pos]=(al[pos]==-1)?nw:-1;
}
inline void rvr(const int& pos,const int& nw)
{
if(pos==1)return;
int nw1=al[pos];
//printf("rvr %d %d->%d [%d]\n",pos,nw,ar[pos],nw1);
if(ar[pos]==-1)
{if(nw1==-1)pans--,ucnt[nw]++;else dcnt[nw1]--,nans+=(nw==nw1);}
else
{if(nw1==-1)pans++,ucnt[nw]--;else nans-=(nw==nw1),dcnt[nw1]++;}
ar[pos]=(ar[pos]==-1)?nw:-1;
}
inline void incl(int& tl)
{tl++;for(int i=g.al[tl],pos;i;i=g.x[i])pos=g.v[i]+1,rvl(pos,ac[pos-1].c);}
inline void decl(int& tl)
{
//printf("decl\n");
for(int i=g.al[tl],pos;i;i=g.x[i])pos=g.v[i]+1,rvl(pos,ac[pos-1].c);tl--;}
inline void incr(int& tr)
{tr++;for(int i=g.al[tr],pos;i;i=g.x[i])pos=g.v[i],rvr(pos,ac[pos].c);}
inline void decr(int& tr)
{for(int i=g.al[tr],pos;i;i=g.x[i])pos=g.v[i],rvr(pos,ac[pos].c);tr--;}
struct qry
{
int t1;int t2;int uc;int dc;
friend bool operator <(qry a,qry b)
{return (bi[a.t1]==bi[b.t1])?a.t2<b.t2:bi[a.t1]<bi[b.t1];}
}qr[N];
inline void ins(const int& tim)
{
// printf("ins %d\n",tim);
for(int i=g.al[tim];i;i=g.x[i])
{
int pos=g.v[i];int nw=ar[pos];
// printf("del %d\n",pos);
if(pos!=1)
{
int nw1=ar[pos-1];
if(nw1==-1)nans++,cnt[nw]--;
else nans-=(ar[pos]==nw1),cnt[nw1]++;
}
if(pos!=m)
{
int nw1=ar[pos+1];
if(nw1==-1)nans++,cnt[nw]--;
else nans-=(ar[pos]==nw1),cnt[nw1]++;
}
ar[pos]=-1;
}
}
inline ll solve()
{
ll ret=0;for(int i=1;i<=m;i++)g.add(ac[i].tim,i);
for(int i=1;i<=n;i++)tr2[i]=arw[i];sort(tr2+1,tr2+n+1);
for(int i=1;i<=m;i++)ar[i]=ac[i].c;
for(int i=2;i<=m;i++)nans+=(ar[i]==ar[i-1]);
for(int i=1,j=1;i<=n;i++)
{
while(j<=tr2[i].tim)ins(j),j++;ret+=nans+cnt[tr2[i].c];
// for(int i=1;i<=m;i++)printf("%d ",ar[i]);printf("\n");
// printf("nans+cnt[tr2[i].c]=%lld,%d\n",nans+cnt[tr2[i].c],tr2[i].c);
}nans=0;//printf("%lld\n",ret);
if(typ==0)return ret;
for(int i=2;i<=m;i++)al[i]=ac[i-1].c;
for(int i=1;i<=m;i++)ar[i]=ac[i].c;for(int i=2;i<=m;i++)nans+=(al[i]==ar[i]);
for(int i=2;i<=n;i++)
qr[i-1]=(qry){arw[i-1].tim,arw[i].tim,arw[i-1].c,arw[i].c};
int len=0;int lenm=0;
for(int i=1;i<=q;i++)
{
for(int j=g.al[i];j;j=g.x[j])lenm++;len++;
if(len>=B||lenm>=B)bi[i]=bi[i-1]+1,len=0,lenm=0;else bi[i]=bi[i-1];
}sort(qr+1,qr+n);int tl=0;int tr=0;
// for(int i=2;i<=m;i++)printf("%d ",al[i]);printf("\n");
// for(int i=2;i<=m;i++)printf("%d ",ar[i]);printf("\n");
// printf("nans=%d\n",nans);
for(int i=1;i<n;i++)
{
while(tl<qr[i].t1)incl(tl);while(qr[i].t1<tl)decl(tl);
while(tr<qr[i].t2)incr(tr);while(qr[i].t2<tr)decr(tr);
// for(int j=2;j<=m;j++)printf("%-3d",al[j]);printf("\n");
// for(int j=2;j<=m;j++)printf("%-3d",ar[j]);printf("\n");
ret+=pans*(qr[i].uc==qr[i].dc)+nans+ucnt[qr[i].uc]+dcnt[qr[i].dc];
// printf("%lld %lld %d %d [%d,%d] ans=%lld\n",pans,nans,ucnt[qr[i].uc],dcnt[qr[i].dc],qr[i].uc,qr[i].dc,
// pans*(qr[i].uc==qr[i].dc)+nans+ucnt[qr[i].uc]+dcnt[qr[i].dc]);
}return ret;
}
inline void clear()
{
g.clear();
for(int i=0;i<=q;i++)ucnt[i]=0;for(int i=0;i<=q;i++)dcnt[i]=0;
for(int i=0;i<=q;i++)cnt[i]=0;nans=0;pans=0;
}
struct mqry{int tp;int l;int r;int c;}quy[N];map <int,int> mp;
int main()
{
scanf("%d%d%d%d",&n,&m,&q,&typ);
for(int i=1;i<=q;i++)
scanf("%d%d%d%d",&quy[i].tp,&quy[i].l,&quy[i].r,&quy[i].c);
for(int i=1;i<=q;i++)mp[quy[i].c]=1;mp[0]=0;
map <int,int> :: iterator it1,it;
for(it=mp.begin(),it1=it,++it1;it!=mp.end();++it,++it1)it1->second+=it->second;
for(int i=1;i<=q;i++)quy[i].c=mp[quy[i].c];
for(int i=1;i<=q;i++)
if(quy[i].tp==0)lt.setv(1,0,n,quy[i].l-1,quy[i].r,(data){i,quy[i].c});
lt.dfs(1,0,n,arw);lt.clr(n);
// for(int i=1;i<=n;i++)printf("(%d,%d),",arw[i].c,arw[i].tim);printf("\n");
for(int i=1;i<=q;i++)
if(quy[i].tp==1)lt.setv(1,0,m,quy[i].l-1,quy[i].r,(data){i,quy[i].c});
lt.dfs(1,0,m,ac);
// for(int i=1;i<=m;i++)printf("(%d,%d),",ac[i].c,ac[i].tim);printf("\n");
for(int i=1;i<=m;i++)ac[i].tim++;for(int i=1;i<=n;i++)arw[i].tim++;
ll ans=0;ans+=solve();clear();
// printf("%lld\n",ans);
reverse(ac+1,ac+m+1);
for(int i=1;i<=max(n,m);i++)swap(arw[i],ac[i]);swap(n,m);
ans+=solve();clear();
printf("%lld",ans);return 0;
}
```
### 12/24
#### t2:path
给你一张图，每天会有一条边开放，如果你恰好在这条边的一个端点那么就可以走过去求从1到n的最少期望时间
大力设期望
$$E(u)=\frac{\sum_{v \in u.alist}\min(E(u),E(v))+m}{d(u)}$$
然后我们记一下分子和分母重新写个松弛跑dij就行了
```C
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=1e5+10;typedef double db;
int n;int m;int dg[N];db dis[N];db sig[N];bool book[N];
int v[2*N];int x[2*N];int ct;int al[N];
struct data
{
int u;db val;
friend bool operator <(data a,data b){return a.val>b.val;}
};priority_queue <data> pq;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void rlx(int u,int V)
{
// printf("rlx %d %d\n",u,V);
sig[u]+=dis[V],dg[u]++,dis[u]=min(sig[u]/(db)dg[u],dis[u]),pq.push((data){u,dis[u]});
// printf("dis [%d]=(%lf,%lf/%lf)\n",u,dis[u],sig[u],(db)dg[u]);
}
inline void solve()
{
dis[n]=0;for(int i=1;i<n;i++)dis[i]=0x3f3f3f3f;
for(int i=1;i<n;i++)sig[i]=m;
for(pq.push((data){n,0});!pq.empty();)
{
data nw=pq.top();pq.pop();if(book[nw.u])continue;book[nw.u]=true;
for(int i=al[nw.u];i;i=x[i])rlx(v[i],nw.u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
solve();
// for(int i=1;i<=n;i++)printf("%lf ",dis[i]);printf("\n");
printf("%lf",dis[1]);return 0;
}
```
#### t3 tree
给定一个树，设$f(k)$表示在树上放置k关键点之后离关键点最远点距离的最小值，输出$f(1)...f(n)$
显然我们可以贪心的求出对偶问题，并且观察到答案是$O(n)$级别并且f数组单调，那么我们可以暴力枚举答案对于最后的$O(\sqrt{N})$段跑整体二分，唯一需要注意的事情是贪心的时候用后序遍历来卡常
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;const int N=1e5+10;typedef long long ll;int n;
int ni[N];int ot[N];int ve_bas[N];int* ve[N];int d[N];int dfn[N];int df;
struct gr
{
int v[N<<1];int x[N<<1];int ct;int al[N];int fa[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs(int u,int f)
{fa[u]=f;for(int i=al[u];i;i=x[i])if(v[i]!=f)dfs(v[i],u),d[u]++;dfn[++df]=u;}
inline void cbuild()
{
dfs(1,0);int* tp=ve_bas;
for(int k=1;k<=n;k++)
{
ve[k]=tp;int ct=-1;
for(int i=al[k];i;i=x[i])if(v[i]!=fa[k])ve[k][++ct]=v[i];
tp=tp+d[k];
}
}
}g;int lim;int nans;int dp[N];
inline void dfs()
{
for(int k=1;k<=n;k++)
{
int u=dfn[k];int mxo=0;int mxi=-1;int* p=ve[u];
for(int i=0;i<d[u];i++)mxo=max(mxo,ot[p[i]]);
for(int i=0;i<d[u];i++)if(ni[p[i]]+2>mxo)mxi=max(mxi,ni[p[i]]);
ot[u]=max(mxo-1,0);ni[u]=(mxi==-1)?-1:mxi+1;
if(mxo<=0)ni[u]=max(ni[u],0);
if(ni[u]>=lim)ni[u]=-1,ot[u]=lim,nans++;
}if(ni[1]!=-1)nans++;
}
inline int calc(int k,int l,int r)
{
while(l!=r){lim=(l+r)>>1;nans=0;dfs();if(nans<=k)r=lim;else l=lim+1;}
return l;
}
inline void solve(int l,int r,int dl,int dr)
{
if(l>r)return;if(l==r){dp[r]=calc(r,dl,dr);return;}
if(dl==dr){for(int i=l;i<=r;i++)dp[i]=dl;return;}
int mid=(l+r)/2;dp[mid]=calc(mid,dl,dr);
solve(l,mid-1,dp[mid],dr);solve(mid+1,r,dl,dp[mid]);
}
int mxr;
int main()
{
scanf("%d",&n);
for(int i=2,u,v;i<=n;i++)scanf("%d%d",&u,&v),g.add(u,v),g.add(v,u);
g.cbuild();int ans=sqrt(n)+1;
for(int i=1;i<=n;i++)dp[i]=-1;
for(int i=0;i<=ans;i++)
{
lim=i;nans=0;dfs();mxr=nans;
for(int j=mxr;dp[j]<0;j++)dp[j]=i;
}
if(2<=mxr-1)solve(2,mxr-1,dp[mxr-1]=calc(mxr-1,0,n),dp[1]=calc(1,0,n));
//solve(2,n-1,dp[n]=calc(n,0,n),dp[1]=calc(1,0,n));
for(int i=1;i<=n;i++)printf("%d ",dp[i]);return 0;
}
```
### 12/25
~~都说了lca题做不来的告辞~~