题意：

科学家有一个容量为N的书架，书里有元素，每个元素有一个污染值。

有两种操作，

实习生拿了一本新书替换了x位置的书,新书对应元素的污染值为y。

大科学家得到了新的结果，如果x位置的书对应的元素加入了实验，那么[l,r]区间内的书对应的元素都必须拿来做实验。

大科学家希望在完成一次科学实验的前提下（不能不选任何元素），这次实验的总污染值最小。问这个最小的总污染值是多少。

保证大科学家的书籍总数$(N+ 新书数量)≤10^5$ 。

每个元素的污染值$0\leq(a_i,y)\leq10^9$ 。

保证$1\leq x\leq N$，$1\leq l\leq r\leq N,M\leq 10^5$ 。

保证$\sum(r-l+1)\leq 10^5$ 。

思路：

这道题在写简单的时候就已经筋疲力尽了…题意描述不清楚啊…

看题目的时候范围又看错了…以为挨个建边会TLE…没看到求和符号啊相当于直接就想下一题（困难）了？

延续上一题的思路，上一题建完图之后对于每个点跑dfs然后找出总污染值最小的那个点，但是这里就不能这么做了，考虑到总污染值最小的总是出度为0的那个点。

但是如果存在环呢？那不就没有出度为0的点了吗？所以这里就要用到tarjan缩点啦。

缩点之后找出度为0的强连通分量，找出强连通分量里总污染值里最小的那个即可。

其实这题还是很简单的啊…做的时候真的傻了…题目数据范围都没看清楚…还是要仔细读题啊…

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll val[100010];
int a[100010];//当前书架上放的元素
vector<int>v[100010];
vector<int>scc[100010];
int dfn[100010];//在DFS中该节点被搜索的次序
int low[100010];//i或i的子树能够追溯到的最早的栈中节点的次序号
int sccn[100010];//缩点数组，表示某个点对应的强连通分量编号
int ot[100010];//每个强连通分量的出度
bool vis[100010];//是否在栈中
int step;
int cnt;//强连通分量编号
stack<int>s;
void tarjan(int u)
{
    dfn[u]=low[u]=++step;
    vis[u]=true;
    s.push(u);
    for(int i=0;i<v[u].size();i++)
    {
        int temp=v[u][i];
        if(!dfn[temp])//没有被访问过
        {
            tarjan(temp);
            low[u]=min(low[u],low[temp]);
        }
        else if(vis[temp])//在栈中
            low[u]=min(low[u],dfn[temp]);
    }
    if(low[u]==dfn[u])//构成强连通分量
    {
        cnt++;
        while(1)
        {
            int temp=s.top();
            s.pop();//此点以上的点全部出栈，构成一个强连通分量
            vis[temp]=false;
            sccn[temp]=cnt;//cnt是强连通分量的序号
            scc[cnt].push_back(temp);
            if(temp==u)break;
        }
    }
}
int main()
{
    int n,m,op;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&val[i]);
        a[i]=i;
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&op);
        if(op==0)
        {
            int x;
            ll y;
            scanf("%d%lld",&x,&y);
            val[++n]=y;
            a[x]=n;
        }
        else if(op==1)
        {
            int x,l,r;
            scanf("%d%d%d",&x,&l,&r);
            for(int i=l;i<=r;i++)
                v[a[x]].push_back(a[i]);
        }
    }
    step=cnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(sccn,0,sizeof(sccn));
    fill(vis+1,vis+n,false);
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    memset(ot,0,sizeof(ot));
    for(int i=1;i<=n;i++)
    for(int j=0;j<v[i].size();j++)
    {
        int temp=v[i][j];
        if(sccn[i]!=sccn[temp])//如果i点与他指向的点不在同一个强连通分量中
            ot[sccn[i]]++;//i点所在的强连通分量的出度+1
    }
    ll ans=INF;
    for(int i=1;i<=cnt;i++)
    {
        if(ot[i]==0)
        {
            ll sum=0;
            for(int j=0;j<scc[i].size();j++)
                sum+=val[scc[i][j]];
            ans=min(ans,sum);
        }
    }
    printf("%lld\n",ans);
    return 0;
}