[LibreOJ 2249][NOI2014]购票

在紧张刺激的等待之后终于肝掉了这道题……

本题的DP方程长成这样(其中\(a\)指\(v\)的某个满足距离限制的祖先,\(d_v\)指\(v\)到根的路径长):

\[f_v = min(f_a + p_v(d_v - d_a) + q_v)\]

化简之后发现:

\[f_v = q_v + p_v d_v + min(f_a - p_v d_a)\]

利用\(min\)中那一块很容易发现是截距式……但是问题在于,我们的转移来源是树上的连续一段祖先,怎样维护他们的凸包?

答案很狂暴啊……用树链剖分套上向量集那题的线段树套凸包,然后完了……

(注意一点细节:本题因为数据范围过大,故可能存在两个向量叉乘爆long long,所以在求凸包时如果直接用叉积判断是否需要删点会炸掉,建议用斜率判断)

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <climits>
using ll = long long;
using T = ll;
using R = long double;
const R eps = 1e-8;
int sign(R x) {
  if(fabsl(x) < eps) {
    return 0;
  } else {
    if(x > (R(0.00))) {
      return 1;
    } else {
      return -1;
    }
  }
}

struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
  if(a.x == b.x) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
inline R slope(const Vector &a) {
  R dx = a.x, dy = a.y;
  return (dy / dx);
}

inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
  std::sort(P + 1, P + 1 + L, cmp);
  for(int i = 1; i <= L; i ++) {
    if(i != 1 && (P[i].x == P[i - 1].x)) continue;
    while(bot.size() > 1 && sign(slope(P[i] - bot.back()) - slope(bot.back() - bot[bot.size() - 2])) <= 0) {
      bot.pop_back();
    }
    bot.push_back(P[i]);
  }
  for(int i = L; i >= 1; i --) {
    if(i != L && (P[i].x == P[i + 1].x)) continue;
    while(top.size() > 1 && sign(slope(P[i] - top.back()) - slope(top.back() - top[top.size() - 2])) <= 0) {
      top.pop_back();
    }
    top.push_back(P[i]);
  }
  std::reverse(top.begin(), top.end());
}

const int maxn = 200005;
const int maxno = maxn << 2;
const int N = 200000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
  static Point tmp[maxn];
  const int lc = o << 1, rc = o << 1 | 1;
  const bool used = zen[o];
  zen[o] = (zen[lc] && zen[rc]);
  if(zen[o] != used) {
    std::copy(P + L, P + R + 1, tmp + 1);
    int len = R - L + 1;
    andrew(tmp, len, bot[o], top[o]);
  }
}
void modify(int o, int L, int R, const int &p, const Point &v) {
  if(L == R) {
    zen[o] = true;
    P[L] = v;
    bot[o].push_back(v); top[o].push_back(v);
  } else {
    const int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o, L, R);
  }
}
inline T calc_ans(T k, const Point &v) {
  return v.y - k * v.x;
}
inline T search(const std::vector<Point> &vec, const T &k) {
  int l = 0, r = vec.size() - 1;
  while(r - l > 2) {
    int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
    if((calc_ans(k, vec[lm]) > calc_ans(k, vec[rm]))) {
      l = lm;
    } else {
      r = rm;
    }
  }
  T ans = LLONG_MAX;
  for(int i = l; i <= r; i ++) {
    ans = std::min(ans, calc_ans(k, vec[i]));
  }
  return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const T &k) {
  if(ql <= L && R <= qr) {
    return search(bot[o], k);
  } else {
    int M = (L + R) / 2;
    T ans = LLONG_MAX;
    if(ql <= M) {
      ans = std::min(ans, query(o << 1, L, M, ql, qr, k));
    }
    if(qr > M) {
      ans = std::min(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
    }
    return ans;
  }
}

int first[maxn];
int next[maxn << 1], to[maxn << 1];
ll dist[maxn << 1];
void add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
  dist[cnt] = d;
}

int fa[maxn], dep[maxn], hson[maxn];
ll d[maxn];
int siz[maxn];
int bs[maxn][18];
void dfs_1(int x, int f = -1, int depth = 1) {
  fa[x] = bs[x][0] = f; dep[x] = depth;
  siz[x] = 1;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != f) {
      d[v] = d[x] + dist[i];
      dfs_1(v, x, depth + 1);
      siz[x] += siz[v];
      if(siz[v] > max_siz) {
        hson[x] = v; max_siz = siz[v];
      }
    }
  }
}
int dfn[maxn], tid[maxn], up[maxn];
void dfs_2(int x, int a = 1, int f = 0) {
  static int cnt = 0;
  dfn[x] = ++ cnt; tid[cnt] = x;
  up[x] = a;
  if(hson[x]) {
    dfs_2(hson[x], a, x);
  } else {
    return;
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != f && v != hson[x]) {
      dfs_2(v, v, x);
    }
  }
}
int k_anc(int x, ll k) {
  int yx = x;
  for(int j = 17; j >= 0; j --) {
    int a = bs[x][j];
    if(a != -1 && d[yx] - d[a] <= k) {
      x = a;
    }
  }
#ifdef LOCAL
  printf("%d's %lld-th anc : %d\n", yx, k, x);
#endif
  return x;
}
int n;
ll get_up(int x, int anc, ll k) {
  ll ans = LLONG_MAX;
  while(up[x] != up[anc]) {
    ans = std::min(ans, query(1, 1, n, dfn[up[x]], dfn[x], k));
    x = fa[up[x]];
  }
  return std::min(ans, query(1, 1, n, dfn[anc], dfn[x], k));
}

ll p[maxn], q[maxn], l[maxn];
ll f[maxn];
void dp(int x) {
#ifdef LOCAL
  printf("processing %d...\n", x);
  printf("d : %lld\n", d[x]);
#endif
  if(x != 1) {
#ifdef LOCAL
    printf("b : %lld\n", get_up(fa[x], k_anc(x, l[x]), p[x]));
#endif
    f[x] = get_up(fa[x], k_anc(x, l[x]), p[x]) + d[x] * p[x] + q[x];
  } else {
    f[x] = 0;
  }
#ifdef LOCAL
  printf("ans : %lld\n", f[x]);
#endif
  modify(1, 1, n, dfn[x], Point(d[x], f[x]));
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    dp(v);
  }
}

int main() {
  int t; scanf("%d%d", &n, &t);
  for(int i = 2; i <= n; i ++) {
    int father; T s;
    scanf("%d%lld%lld%lld%lld", &father, &s, &p[i], &q[i], &l[i]);
    add_edge(father, i, s);
  }
  memset(bs, -1, sizeof(bs));
  dfs_1(1); dfs_2(1);
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = bs[i][j - 1];
      if(a != -1) {
        bs[i][j] = bs[a][j - 1];
      }
    }
  }
  dp(1);
  for(int i = 2; i <= n; i ++) {
    printf("%lld\n", f[i]);
  }
  return 0;
}

[BZOJ 3252]攻略

近期心情不顺,坑了一堆没写的题解……(嗯我反演等回来再填坑吧(逃

好了还是说说这题吧,私以为鄙人的做法还是蛮妙的:

定义\(d(x)\)表示\(x\)到根上所有点的权值和,\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点,他的所有儿子中\(d_{max}(x)\)最大的称为重儿子,其他作为轻儿子,然后做一遍树剖。然后将所有重链的权值和扔到一个数组里,降序排序,选前\(k\)大求和即可(不够的话全选)。

为什么?

显然,尽可能选叶子是划算的。然后,任意一条重链链顶的父亲所在的重链的权值和必定大于该重链,所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并,恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的,所以答案是最优的。

继续阅读

[BZOJ 3531]旅行

发现自己好久没写树链剖分了……唉……

言归正传,这道题很容易想到的做法就是每种宗教开一个线段树,到各个宗教的线段树里面操作即可。

很可惜,直接开线段树的话肯定会MLE。我们可以考虑动态开点,对于不需要的点一律不开。这样内存消耗量就大减了。

注意一些细节:

  1. 查询时判断当前结点是不是NULL。
  2. 删除前最好判断一下这个结点是不是NULL吧,以防万一。
  3. 删除操作时,如果结点没有用了,就删。但是注意,记得delete前要把原指针设为NULL,直接delete会引起悬垂指针问题导致爆炸!

代码:

/**************************************************************
    Problem: 3531
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10404 ms
    Memory:34872 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
    struct Node{
        int sumv,maxv;
        Node *lc,*rc;
        Node(){
            sumv=maxv=0;
            lc=rc=NULL;
        }
        void maintain(){
            if(lc!=NULL){
                if(rc!=NULL){
                    sumv=lc->sumv+rc->sumv;
                    maxv=max(lc->maxv,rc->maxv);
                }else{
                    sumv=lc->sumv;
                    maxv=lc->maxv;
                }
            }else{
                if(rc!=NULL){
                    sumv=rc->sumv;
                    maxv=rc->maxv;
                }
            }
        }
    };
    Node* T[maxn];
    int p,v;
    void _Delete(Node* &o,int L,int R){
        if(o==NULL)
            return;
        if(L==R){
            Node *temp=o;
            o=NULL;
            delete temp;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Delete(o->lc,L,M);
            else
                _Delete(o->rc,M+1,R);
            if(o->lc==NULL && o->rc==NULL){
                Node *temp=o;
                o=NULL;
                delete temp;
            }else{
                o->maintain();
            }
        }
    }
    inline void Delete(int c,int pos){
        p=pos;
        _Delete(T[c],1,n);
    }
    void _Insert(Node* &o,int L,int R){
        if(o==NULL)
            o=new Node();
        if(L==R){
            o->sumv=o->maxv=v;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Insert(o->lc,L,M);
            else
                _Insert(o->rc,M+1,R);
        }
        o->maintain();
    }
    inline void Insert(int c,int pos,int value){
        p=pos;
        v=value;
        _Insert(T[c],1,n);
    }
    int ql,qr;
    int _query_max(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->maxv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans=max(ans,_query_max(o->lc,L,M));
        if(qr>M)
            ans=max(ans,_query_max(o->rc,M+1,R));
        return ans;
    }
    inline int query_max(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_max(T[c],1,n);
    }
    int _query_sum(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->sumv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans+=_query_sum(o->lc,L,M);
        if(qr>M)
            ans+=_query_sum(o->rc,M+1,R);
        return ans;
    }
    inline int query_sum(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_sum(T[c],1,n);
    }
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}
 
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hld_cnt;
    SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
int query_max(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_max(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_sum(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
    int c=rlg[pos];
    SegmentTree::Delete(c,tid[pos]);
    SegmentTree::Insert(direction,tid[pos],d[pos]);
    rlg[pos]=direction;
}
inline void Update(int pos,int v){
    d[pos]=v;
    SegmentTree::Insert(rlg[pos],tid[pos],v);
}
 
int main(){
    register int i;
    int q,u,v;
    char buf[5];
    scanf("%d%d",&n,&q);
    REP_B(i,n){
        scanf("%d%d",&d[i],&rlg[i]);
    }
    REP_B(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    while(q--){
        memset(buf,0,sizeof(buf));
        scanf("%s%d%d",buf,&u,&v);
        if(buf[0]=='C'){
            if(buf[1]=='W'){
                Update(u,v);
            }else{
                Replace(u,v);
            }
        }else{
            if(buf[1]=='M'){
                printf("%d\n",query_max(rlg[u],u,v));
            }else{
                printf("%d\n",query_sum(rlg[u],u,v));
            }
        }
    }
    return 0;
}

[BZOJ 2243]染色

树剖好题……

2243记录

这能说明几个问题:

  1. 人傻自带大常数
  2. 不看题解难AC

继续阅读

[BZOJ 4034]T2

这个题名字也真是……

思路和我以前提到过的NOI2015 D1T2的做法是相似的,不过这题貌似int会爆精度……我这SB开始没发现,后来改了还慢慢出错……然后慢慢改……终于AC了……

我本来以为这个YY思路只有我和诸位读者知道,结果发现是貌似是ydc发明的……比我早的高明的不知哪里去了……

代码:

继续阅读

[BZOJ 4390]Max Flow

这明明不是道网络流题。

这就是道树剖题……

没有什么太难的地方,然而还是调试了几遍才过。

代码:

继续阅读

[BZOJ 4196]软件包管理器

终于A了!

在CodeVS,洛谷甚至UOJ上各种A

但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?

这题处理安装很简单,一直溯到根。

删除……注意一下树剖的一些神奇性质。

继续阅读

[BZOJ 1036]树的统计

终于A了这题了!

树剖大水题~

然而zzs这种蒟蒻还是要交很多次才过:

继续阅读