2018计蒜之道初赛第一场 D.百度科学家(困难)(主席树优化tarjan建图)

题解

  比赛的时候这题死活RE调不出来,于是一直在MLE和RE的边缘试探…赛后对拍感觉错误原因没道理导致RE,有毒…
  发现这个题和GDSOI D1T1很像,于是非常会写
  这个题显然就是每次一个点向一个区间的点连边求最后每个点能到哪些点
  有一个很好的性质就是每次连边是一个区间,那么我们可以考虑用线段树来优化建图,这样可以把O(L)O(L)的连边数量改为O(logL)O(logL)的。
  因为带修改,所以可持久化一下就完了。
  比赛时的错误原因:
   1.1.线段树上节点没有往左右儿子连边(样例是真的水QAQ
   2.2.11得边表要开3倍…
   3.3.主席树是动态开点的,左右儿子不是x2x*2x2+1x*2+1(样例有毒…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=2000010;
const ll inf=1e18;
struct sgt{int lt, rt;}tree[maxn];
struct edge{int x, too, pre;}e[maxn*3];
int n, m, ty, l, r, x, sum, tot, tot2, color, sz, root;
int a[maxn], pos[100010], chu[maxn], last[maxn], dfn[maxn], low[maxn], tott, st[maxn], top, lack[maxn], col[maxn];
ll cnt[maxn];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void add(int x, int y){e[++tot]=(edge){x, y, last[x]}; last[x]=tot;}

void update(int &x, int l, int r, int cx)
{
	tree[++sz]=tree[x]; x=sz;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(cx<=mid) update(tree[x].lt,l,mid,cx);
	else update(tree[x].rt,mid+1,r,cx);
	if(tree[x].lt) add(x, tree[x].lt); 
	if(tree[x].rt) add(x, tree[x].rt);
}

void Link(int x, int l, int r, int cl, int cr, int pos)
{
	if(cl<=l && r<=cr){add(pos, x); return;}
	int mid=(l+r)>>1;
	if(cl<=mid) Link(tree[x].lt, l, mid, cl, cr, pos);
	if(cr>mid) Link(tree[x].rt, mid+1, r, cl, cr, pos);
}

void tarjan(int x)
{
	dfn[x]=low[x]=++tott; st[++top]=x; lack[x]=top;
	for(int i=last[x], too;i;i=e[i].pre)
	if(!dfn[too=e[i].too]) tarjan(too), low[x]=min(low[x], low[too]);
	else if(!col[too]) low[x]=min(low[x], dfn[too]);
	if(dfn[x]==low[x]) for(++color;top>=lack[x];top--) 
	col[st[top]]=color, cnt[color]+=a[st[top]];
}

int main()
{
	read(n);
	for(int i=1;i<=n;i++) update(root, 1, n, i), pos[i]=sz, read(a[sz]);
	read(m);
	for(int i=1;i<=m;i++)
	{
		read(ty);
		if(ty==1)
		{
			read(x); read(l); read(r); 
			Link(root, 1, n, l, r, pos[x]);
		}
		else
		{
			read(x); 
			update(root, 1, n, x); pos[x]=sz;
			read(a[sz]);
		}
	}
	for(int i=1;i<=sz;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=tot;i++)
	if(col[e[i].x]!=col[e[i].too]) chu[col[e[i].x]]++;
	ll ans=inf;
	for(int i=1;i<=color;i++) if(!chu[i]) ans=min(ans, cnt[i]);
	printf("%lld\n", ans);
}