神奇的树状数组，写三个函数过了，这些函数理解也很容易，也可以选择背下来。。

但是，要提醒的是，cin最好全部换成scanf，然后还有RE的。。。

我自己就RE了数回，原因很鬼畜。。

1、不要把数组开太小。。

2、solve函数会把头元素x算进去，所以是solve(x-1)。。。

3、附上代码：

include

using namespace std;

int n,m,x,y,c[500010],a[500010],ch;

int lowbit(int x){

return x&(-x);

} void change(int x,int y){

while(x<=n){

    c[x]+=y;

    x+=lowbit(x);

}

}

int solve(int x){

int cnt=0;

while(x){

    cnt+=c[x];

    //cout<<c[x]<<endl;

    x-=lowbit(x);

}

return cnt;

}

int main(){

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)scanf("%d",&a[i]),change(i,a[i]);

for(int i=1;i<=m;i++){ 

    scanf("%d%d%d",&ch,&x,&y);

    if(ch==1) change(x,y);

    else{

    printf("%d",solve(y)-solve(x-1));

    if(i!=m) puts("");

    }

}

return 0;

}

用kruskal(prim不会。。。)。。

kruskal大概思路：首先找到一条权值最小的边，将他的两个点加入集合中，然后继续往下找小边，

用并查集算法判断一下是否在统一集合内，如果是的话，就不加入；

不是就加入集合并累计入答案。。。

include

include

using namespace std;

struct node{

int x,y,c;

}a[500010];

int n,m,fa[500010],ans,t;

int getfa(int x){//寻找祖先

if(fa[x]==x) return x;

else{

fa[x]=getfa(fa[x]);

return fa[x];

}

}

bool cmp(node a,node b){

return a.c<b.c;

}

int main(){

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++) fa[i]=i;//并查集初始化，刚开始所有点的父亲都是自己，单独成一个集合

for(int i=1;i<=m;i++){

    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);

}

sort(a+1,a+m+1,cmp);

for(int i=1;i<=m;i++){

    int fx,fy;

    fx=getfa(a[i].x);

    fy=getfa(a[i].y);

    if(fx!=fy){//不在同一集合内就累计入答案

        ans+=a[i].c;

        t++;

        fa[fy]=fx;//加入集合，认x的祖先点为父亲

        if(t==n-1) break;//招满了n-1条边，就已经完成任务了

    }

}

printf("%d",ans);

return 0;

}

因为这是一种中链式dp,为了方便起见，将环状的项链平坦开呈链状，并且多加一次，这样可以找到所有情况

设f[i][j]为从i到j所能获得的最大值，因此从l枚举到r，求出最大值

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];//在末尾多加一段

for(int i=2;i<n*2;i++){//枚举末尾

    for(int j=1;j+i-1<2*n;j++){//枚举起点       

        int r=j+i-1;  

        for(int k=j;k<r;k++)//每个点都合并试试

        f[j][r]=max(f[j][r],f[j][k]+f[k+1][r]+a[j]*a[k+1]*a[r+1]);      

    }

}

for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);//跑一遍求出最大值

printf("%d",ans)；

return 0;

这是一个关于SPFA的题解。。（Dijkstra不太会。。）

由于邻接表太烦（不会），所以就直接写个vector来存边的关系，

然后用v[f][i].first表示f点连出去的第i个点的编号，v[f][i].second表示

f点连出去的第i条边的权值。所以，每次判断一下是否经过点i更优，并且更新。

scanf("%lld%lld%lld",&n,&m,&s);

while(m--){

     scanf("%lld%lld%lld",&x,&y,&z);

     v[x].push_back(make_pair(y,z));//建图，将边的关系存入v数组 

}   

for(int i=1;i<=n;i++)d[i]=2147483647;

vis[s]=1;//将s点标为已入队 

d[s]=0;//s到自己的距离当然是0 

l[0]=s;//s点入队 

int h=0,t=1;//注意队列数组开大一些，因为每个点入队可能有好几次 

while(h<t){//当队列中还有点时继续循环 

    int f=l[h++];vis[f]=0;//初始化，将队头的点进行操作 

    for(int i=0;i<v[f].size();i++)//枚举每条边 

    if(d[v[f][i].first]>d[f]+v[f][i].second){//判断是否为更优 

        d[v[f][i].first]=d[f]+v[f][i].second;//更新 

        if(!vis[v[f][i].first]) vis[v[f][i].first]=1,l[t++]=v[f][i].first;//更新后标为已入队 

    }

}

for(int i=1;i<=n;i++)

printf("%lld ",d[i]);