2019.08.16 日常总结
洛谷P3071：
题意：
有一排n个座位，m次操作。A操作：将a名客人安置到最左的连续a个空位中，没有则不操作。L操作：[a,b]的客人离开。
求A操作的失败次数
思路：线段树的题目，就是复杂了点，要跨左右区间处理，具体看代码吧
#include
using namespace std;
const int N=5e5+1e2;
typedef long long ll;
ll s[N<<2],sl[N<<2],sr[N<<2];
int n,m,x,y,i;short tag[N<<2];
inline void pushup(int o,int l,int r){s[o]=max(max(s[o<<1],s[o<<1|1]),sr[o<<1]+sl[o<<1|1]);sl[o]=sl[o<<1]+(sl[o<<1]==l)*sl[o<<1|1];sr[o]=sr[o<<1|1]+(sr[o<<1|1]==r)*sr[o<<1];
}
inline void pushdown(int o,int l,int r){if (!tag[o]||(!l&&!r)) return;s[o<<1]=sl[o<<1]=sr[o<<1]=(tag[o]>0)*l;s[o<<1|1]=sl[o<<1|1]=sr[o<<1|1]=(tag[o]>0)*r;tag[o<<1]=tag[o<<1|1]=tag[o];tag[o]=0;
}
void build(int o,int l,int r){s[o]=sl[o]=r-l+1;sr[o]=r-l+1;if (l>=r) return;int mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);return;
}
void update(int o,int l,int r,int p,int q,int v){if (p<=l&&r<=q){s[o]=(v>0)*(r-l+1);sl[o]=(v>0)*(r-l+1);sr[o]=(v>0)*(r-l+1);tag[o]=v;return;}if (l>q||r>1;pushdown(o,mid-l+1,r-mid);update(o<<1,l,mid,p,q,v);update(o<<1|1,mid+1,r,p,q,v);pushup(o,mid-l+1,r-mid);return;
}
int query(int o,int l,int r,int c){register int mid=(l+r)>>1;pushdown(o,mid-l+1,r-mid);if (s[o<<1]>=c) return query(o<<1,l,mid,c);else if (sr[o<<1]+sl[o<<1|1]>=c) return mid-sr[o<<1]+1;else return query(o<<1|1,mid+1,r,c);
}
int ans,pos;char opt;
int main(){
// freopen("t1.in","r",stdin);scanf("%d%d",&n,&m);build(1,1,n);for(i=1;i<=m;i++){cin>>opt;switch(opt){case 'A':cin>>x;if (s[1]>x>>y;update(1,1,n,x,y,1);}}printf("%d",ans);return 0;
}
//被o，o<<1，o<<1|1坑了大半小时…… 洛谷P2746:
题意：
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
思路：缩点，对于子任务A，统计入度为0的点即可，对于子任务B，输出入度为0的点的个数和出度为0的点的个数的较大值即可
#include
using namespace std;
const int N=10100;
struct node{int next,to;
}e[N];int h[N],tot;
void add_edge_in_e(int a,int b){e[++tot]=(node){h[a],b};h[a]=tot;
}
int dfscnt,Stack[N],stack_top;
int dfn[N],low[N],belong[N],col;
void tarjan(int u){dfn[u]=low[u]=++dfscnt;Stack[++stack_top]=u;for(int i=h[u];i;i=e[i].next){register int v=e[i].to;if (!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if (!belong[v])low[u]=min(low[u],dfn[v]);}if (low[u]==dfn[u]){belong[u]=++col;while (Stack[stack_top]!=u){belong[Stack[stack_top]]=col;--stack_top;}--stack_top;}return;
}
int ind[N],out[N],i,j,x,n,m;
int ind_number,out_number,ans;
int main(){
// freopen("t1.in","r",stdin);scanf("%d",&n);for(i=1;i<=n;i++)do{scanf("%d",&x);if (x==0) break;add_edge_in_e(i,x);}while (x!=0);for(i=1;i<=n;i++)if (!dfn[i]) tarjan(i);for(i=n;i;i--)for(j=h[i];j;j=e[j].next){register int v=e[j].to;if (belong[i]!=belong[v]){++out[belong[i]];++ind[belong[v]];}}if (col==1) printf("1\n0");else{for(i=1;i<=col;i++){if (out[i]==0) out_number++;if (ind[i]==0) ind_number++;}ans=max(ind_number,out_number);printf("%d\n%d",ind_number,ans);}return 0;
} 洛谷P2860
题意：
为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．
每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．
思路：还是缩点，然后统计叶节点的个数ans，输出
即可
#include
using namespace std;
const int N=10100;
struct node{int from,next,to;
}e[N];int h[N],tot;
void add_edge_in_e(int a,int b){e[++tot]=(node){a,h[a],b};h[a]=tot;
}
int dfscnt,belong[N];
int dfn[N],low[N];
bool bridge[N];
void tarjan(int u,int edge){dfn[u]=low[u]=++dfscnt;
// Stack[++stack_top]=u;for(int i=h[u];i;i=e[i].next){register int v=e[i].to;if (!dfn[v]){tarjan(v,i);low[u]=min(low[u],low[v]);if (dfn[u]>1);return 0;
} 
