NAIVE-02

1.手写heap

直接上代码了吧，2333.

struct heap//大根堆
{
    int q[1000000],now;
    heap() {now=0;}
    void down(int x)//下沉
    {
        while((x<<1|1)<=now&&(q[x]<q[x<<1]||q[x]<q[x<<1|1]))
        {
            x=q[x<<1] > q[x<<1|1] ? x<<1 : x<<1|1;
            swap(q[x],q[x>>1]);
        }
        if((x<<1)<=now&&q[x<<1]>q[x]) swap(q[x],q[x<<1]);
    }
    void up(int x)//上浮
    {
        while(x>1&&q[x]>q[x>>1])
            swap(q[x],q[x>>1]),x>>=1;
    }
    void pop() {q[1]=q[now];now--;down(1);}
    int top(){return q[1];}
    void push(int x){q[++now]=x;up(now);}
    bool empty(){return now==0;}
    int size(){return now;}
}q;

手写堆，讲真有时候挺有用的，比如说NOIP2016 蚯蚓 手写堆A掉80分。不错啦。

2.话树状数组

树状数组的功能原来并不只是维护动态前缀和&后缀和。它还可以维护只能改大的前缀最大值和只能改小的前缀最小值。（后缀也可以）。
比如说二维的（带不同优化值的）最长不下降子序列，就可以用树状数组前缀最大值，一直改大就行。。。

另外还要注意，0+=-0&0=0；进入死循环。

然后呢？？？

树状数组值神奇妙用：

1.区间修改，单点查询

将原数组差分，每个单点就是一段前缀和。然后区间修改时直接左端点加上权值，右端点减去权值就好了。查询每次只需要差一个前缀和。

2.单点修改，区间查询

嘻嘻嘻，就是前缀和相减啊。

3.区间修改，区间查询

将原数组差分，然后我们发现，每次要求的就是一个

sigma^r_i=l [ sigmaⁱ_j=1(b[j]) ]

可以化简成：（查询区间为[l,r]）
(r+1)*sigma^r_i=1(b[i]) - sigma^r_i=1(i*b[i])-l*sigma^l-1_i=1(b[i]) + sigma^l-1_i=1(i*b[i]);

开两个树状数组，直接维护b[i]和i*b[i]就好了。

3.树之dfs爆栈？？？

那就bfs呗。首先搞出来一个bfs倒序，保证每个节点的儿子进行完了再进行fa。

比如说BZOJ-2435: [Noi2011]道路修建

自行看代码2333

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1001000
typedef long long ll;
int n,tot,rank[N],fa[N],ans[N];
int head[N],to[N<<1],nxt[N<<1],data[N<<1],cnt,siz[N];
ll fna;
void add(int x,int y,int z)
{
    to[++cnt]=y;
    data[cnt]=z;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int ABS(int x)
{
    return x>0 ? x: -x;
}
void bfs()
{
    rank[++tot]=1;fa[1]=0;ans[1]=0;
    int x,now=1;
    while(tot<n)
    {
        x=rank[now++];
        for(int i=head[x];i;i=nxt[i])
            if(to[i]!=fa[x])
                rank[++tot]=to[i],fa[to[i]]=x,ans[to[i]]=data[i];
    }
    for(int i=n;i;i--)
    {
        int x=rank[i];
        for(int j=head[x];j;j=nxt[j])
            if(to[j]!=fa[x])
                siz[x]+=siz[to[j]];
        siz[x]++;
        fna+=1ll*ans[x]*ABS(n-(siz[x]<<1));
    }
}
int main()
{
    scanf("%d",&n);
    for(int x,y,z,i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    bfs();
    printf("%lld",fna);
    return 0;
}

原谅我太NAIVE