hdu 5861最大最小値セグメントツリーの維持

标题:nの村がある道路では、2つの村の間の道には使用と使用の2つの状態があり、使用時には毎日wi元を消費し、各道の初期には使用されず、m日の中で、私たちは全部で1回開くことができ、閉じることができ、初日からm日目まで、毎日ai、biを与え、aiからbiまでの道が通さなければならないことを示しています.毎日n-1段の道の総費用の最小はいくらですかを聞きます.
考え方:
各セグメントは1回しか開くことができず、1回閉じることができ、第iセグメントが最も早くt 1を使用するか、最も遅くt 2を使用するかを求めることができ、日数t 1で開くことができ、t 2+1で閉じることができます.
オフライン+セグメントツリーは、各セグメントのパラメータt 1,t 2を処理することができる.たとえば、i日目にaiからbiを使用する場合は、aiからbiにiを割り当て、最大値と最小値を維持すればよい.
次にvector v[N];を使用して、i日目に開くパスを保存し、i日目に閉じるパスを保存します.道iを開くと点iがwiに割り当てられ、閉じると0に割り当てられます.
m日を巡って、毎日について、開いたり閉じたりした後、合計を出力すればいいです.クエリi番目のパスの最大最小値

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define N 200020
#define M 100010
#define Mod 1000000007
#define LL long long
#define INF 0x7fffffff
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--)
#define MEM(x,i) memset(x,i,sizeof(x))

struct Node
{
  int Max;
  int Min;
  int w;
  int l,r;
  int mid()
  {
    return (l+r)/2;
  }
};
Node v[N<<2];
void build(int l,int r,int rt)
{
  v[rt].Min=INF;
  v[rt].Max=0;
  v[rt].w=0;
  v[rt].l=l;
  v[rt].r=r;
  if(l==r-1) return ;
  build(l,v[rt].mid(),lson);
  build(v[rt].mid(),r,rson);
}
void push_day(int rt)
{
  if(v[rt].Min!=INF)
  {
    v[lson].Min=min(v[lson].Min,v[rt].Min);
    v[rson].Min=min(v[rson].Min,v[rt].Min);
    v[rt].Min=INF;
  }
  if(v[rt].Max!=0)
  {
    v[lson].Max=max(v[lson].Max,v[rt].Max);
    v[rson].Max=max(v[rson].Max,v[rt].Max);
    v[rt].Max=0;
  }
}
void update_day(int l,int r,int g,int rt)
{
  if(v[rt].l==l && v[rt].r==r)
  {
    v[rt].Max=max(v[rt].Max,g);
    v[rt].Min=min(v[rt].Min,g);
    return ;
  }
  push_day(rt);

  int mid=v[rt].mid();
  if(l>=mid) update_day(l,r,g,rson);
  else if(r<=mid) update_day(l,r,g,lson);
  else
  {
    update_day(l,mid,g,lson);
    update_day(mid,r,g,rson);
  }
}
void look_day(int x,int &Max,int &Min,int rt)
{
  if(v[rt].l==v[rt].r-1)
  {
    Max=v[rt].Max+1;
    Min=v[rt].Min;
    return ;
  }
  push_day(rt);
  int mid=v[rt].mid();
  if(xelse if(x>=mid) look_day(x,Max,Min,rson);
}
vector<int> vv[N];
vector<int> u[N];
int w[N];
void up(int rt)
{
  v[rt].w=v[lson].w+v[rson].w;
}
void update(int x,int w,int rt)
{
  if(v[rt].l==v[rt].r-1)
  {
    v[rt].w=w;
    return ;
  }
  int mid=v[rt].mid();
  if(xelse if(x>=mid) update(x,w,rson);
  up(rt);
}
void update(int x,int rt)
{
  if(v[rt].l==v[rt].r-1)
  {
    v[rt].w=0;
    return ;
  }
  int mid=v[rt].mid();
  if(xelse if(x>=mid) update(x,rson);
  up(rt);
}
int main()
{
  int n,m,x,y;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    build(1,n,1);

    FOR(i,1,n-1){
      scanf("%d",&w[i]);
    }
    FOR(i,1,m){
      scanf("%d%d",&x,&y);
      if(x>y) x^=y^=x^=y;
      update_day(x,y,i,1);
    }
    FOR(i,1,n-1){
      int Max,Min;
      look_day(i,Max,Min,1);
      if(Min!=INF) vv[Min].push_back(i);
      if(Max!=0) u[Max].push_back(i);
    }

    FOR(i,1,m){
      for(int j=0;j1);
      }
      for(int j=0;j1);
      }
      printf("%d
",v[1].w);
    }
    FOR(i,1,m+1)
    {
      vv[i].clear();
      u[i].clear();
    }
  }
  return 0;
}