hdu 5861 Road 两棵线段树

传送门：hdu 5861 Road

题意：

水平线上n个村子间有 n-1 条路. 每条路开放一天的价格为 Wi
有 m 天的操作，每天需要用到村子 Ai~Bi 间的道路
每条路只能开放或关闭一次. (不能重复开关)
求每天的最小花费.

思路：

第一次线段树：维护每条路第一次和最后一次被用到的天数.以下代码维护了 mn:第一次被用到，mx:最后一次被用到，lazy:被更新的最大值
若当前区间被lazy维护而没有更新到点，那么这个子节点的最小值就可能被改变.所以我这里的子节点更新是根据父节点的最大和最小来更新，因为没有pushup操作，所以父节点记录的就是这个区间的最大和最小值。而lazy的作用仅是为了判断是否需要更新子节点，以减少更新操作
第二次线段树：维护每天用了多少钱.
根据以上结果维护，对于每条路(被用到过的)区间更新第一次到最后一次这些天用的钱.

/**************************************************************

    Problem:hdu 5861 Road

    User: youmi

    Language: C++

    Result: Accepted

    Time:2714MS

    Memory:23936K

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 0x3fffffff

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    if (n == ) return ;

    if (n == ) return base % mo;

    ll tmp = Pow(base, n >> , mo);

    tmp = (ll)tmp * tmp % mo;

    if (n & ) tmp = (ll)tmp * base % mo;

    return tmp;

}

//***************************

int n,m;

const int maxn=+;

const ll mod=;

pii p[maxn];

int a[maxn];

ll ans[maxn];

struct tree

{

    int l,r;

    int mx,mn;

    int lz;

    tree(){}

    tree(int _l,int _r,int _mx,int _mn,int _lz)

    {

        l=_l,r=_r,mx=_mx,mn=_mn,lz=_lz;

    }

}seg[maxn<<];

struct tree1

{

    int l,r;

    ll val;

    tree1(){}

    tree1(int _l,int _r,ll _val)

    {

        l=_l,r=_r,val=_val;

    }

}seg1[maxn<<];

void build(int step,int l,int r)

{

    seg[step]=tree(l,r,-oo,oo,);

    if(l==r)

        return;

    int mid=(l+r)>>;

    build(lson,l,mid);

    build(rson,mid+,r);

}

void build1(int step,int l,int r)

{

    seg1[step]=tree1(l,r,);

    if(l==r)

        return;

    int mid=(l+r)>>;

    build1(lson,l,mid);

    build1(rson,mid+,r);

}

void pushdown(int step)

{

    seg[lson].mn=min(seg[lson].mn,seg[step].mn);

    seg[rson].mn=min(seg[rson].mn,seg[step].mn);

    seg[lson].mx=max(seg[lson].mx,seg[step].mx);

    seg[rson].mx=max(seg[rson].mx,seg[step].mx);

    seg[lson].lz=max(seg[lson].lz,seg[step].lz);

    seg[rson].lz=max(seg[rson].lz,seg[step].lz);

    seg[step].lz=;

}

void pushdown1(int step)

{

    seg1[lson].val+=seg1[step].val;

    seg1[rson].val+=seg1[step].val;

    seg1[step].val=;

}

void update(int step,int l,int r,int val)

{

    if(seg[step].l==l&&seg[step].r==r)

    {

        seg[step].mx=max(seg[step].mx,val);

        seg[step].mn=min(seg[step].mn,val);

        seg[step].lz=max(seg[step].lz,val);

        return ;

    }

    if(seg[step].lz)

        pushdown(step);

    int mid=(seg[step].l+seg[step].r)>>;

    if(mid>=r)

        update(lson,l,r,val);

    else if(mid<l)

        update(rson,l,r,val);

    else

    {

        update(lson,l,mid,val);

        update(rson,mid+,r,val);

    }

}

void update1(int step,int l,int r,int v)

{

    if(seg1[step].l==l&&seg1[step].r==r)

    {

        seg1[step].val+=v;

        return ;

    }

    if(seg1[step].val)

        pushdown1(step);

    int mid=(seg1[step].l+seg1[step].r)>>;

    if(mid>=r)

        update1(lson,l,r,v);

    else if(mid<l)

        update1(rson,l,r,v);

    else

    {

        update1(lson,l,mid,v);

        update1(rson,mid+,r,v);

    }

}

void query(int step)

{

    if(seg[step].l==seg[step].r)

    {

        p[seg[step].l]=make_pair(seg[step].mn,seg[step].mx);

        return ;

    }

    if(seg[step].lz)

        pushdown(step);

    query(lson);

    query(rson);

}

void query1(int step)

{

    if(seg1[step].l==seg1[step].r)

    {

        ans[seg1[step].l]=seg1[step].val;

        return ;

    }

    if(seg1[step].val)

        pushdown1(step);

    query1(lson);

    query1(rson);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    while(~sc2(n,m))

    {

        rep(i,,n-)

            sc(a[i]);

        build(,,n-);

        rep(i,,m)

        {

            int l,r;

            sc2(l,r);

            if(l>r)

                swap(l,r);

            update(,l,r-,i);

        }

        query();

        build1(,,m);

        rep(i,,n-)

            if(p[i].first!=oo&&p[i].second!=-oo)

            update1(,p[i].first,p[i].second,a[i]);

        query1();

        rep(i,,m)

            ptlld(ans[i]);

    }

}

hdu 5861 Road 两棵线段树的相关教程结束。