【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