一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 SP6779 【GSS7 - Can you answer these queries VII】

posted on 2018-11-24 11:26:33 | under 题解 |

NOIP之后无心刷DP题,就又来水数据结构了= =

本题可以用树剖+珂朵莉树水过

如果不了解珂朵莉树的话可以到CF896C的题解区看一下

具体做法就是先用树剖处理一下,然后区间修改就用珂朵莉树暴力推平,区间最大子段和直接暴力去求就好啦qwq

注意一下在树剖求区间最大子段和,每次统计的时候要加上之前剩余数值(前一条链上的与当前链相连的最大子段和,因为是x, y两边同时向上跳,所以要用两个变量去保存),交换x, y的时候要同时交换对应的剩余数值,当最后x, y在同一条链上的时候要再交换一下x,y对应的剩余数值。(WA了好几次QAQ)

如果有什么问题或者对题解有什么意见和建议的话欢迎私信小蒟蒻qwqwq。

那么代码如下:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio> 
#include <cmath>
#include <set>
#define re register
#define ll long long
#define maxn 200010
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
#define IT set<node>::iterator
using namespace std;

int n, m, c, r, t, x, y, z, num, cnt, sss, fir1, fir2;
int a[maxn], ans[maxn], tag[maxn], depth[maxn], fa[maxn], top[maxn], id[maxn], dd[maxn];
int son[maxn], head[maxn], siz[maxn];

struct hz {
    int next;
    int to;
}h[maxn];

inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c==-1) return;
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x=x*f;
}

inline void out(int a){
    if(a<0){
        a*=-1;
        putchar('-');
    } 
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

struct node{
    int l;
    int r;
    mutable int v;
    node(int L, int R = -1, int V = 0):l(L), r(R), v(V){}
    bool operator <(const node &o)const {
        return l < o.l;
    }
};

set<node> s;

IT split(int pos) { 
    IT it = s.lower_bound(node(pos));
    if(it != s.end() && it->l == pos)
      return it;
    --it;
    int L = it->l;
    int R = it->r;
    int V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
}

void assign_val(int l, int r, int val = 0) { //推平
    IT itr = split(r+1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

int query(int l, int r) { //暴力统计
    IT itr = split(r+1), itl = split(l);
    int anss = fir1;
    int res = fir1;
    --itr;
    --itl;
    for(; itl != itr; --itr) {
        res += (itr->r-itr->l+1)*itr->v;
        if(res > anss)
          anss = res;
        if(res < 0)
          res = 0;
    }
    fir1 = res;
    return anss;
}

void add(int from, int to) { 
    h[++num].next = head[from];
    h[num].to = to;
    head[from] = num;
}

void dfs1(int f, int ff) { //树剖预处理
    fa[f] = ff;
    depth[f] = depth[ff]+1;
    siz[f] = 1;
    for(re int i = head[f]; i != 0; i = h[i].next) {
        if(h[i].to == ff)
          continue;
        dfs1(h[i].to, f);
        siz[f] += siz[h[i].to];
        if(siz[h[i].to] > siz[son[f]])
          son[f] = h[i].to;
    } 
}

void dfs2(int x, int topf) { //同上
    top[x] = topf;
    id[x] = ++cnt;
    dd[cnt] = a[x];
    if(!son[x])
      return;
    dfs2(son[x], topf);
    for(re int i = head[x]; i != 0; i = h[i].next) {
        if(h[i].to == fa[x] || h[i].to == son[x])
          continue;
        dfs2(h[i].to, h[i].to);
    }
}

void updrange(int x, int y, int k) { //推平
    while(top[x] != top[y]) {
        if(depth[top[x]] < depth[top[y]])
          swap(x, y);
        assign_val(id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y])
      swap(x, y);
    assign_val(id[x], id[y], k);
}

int qrange(int x, int y) { //区间最大子段和
    int anss = 0;
    while(top[x] != top[y]) {
        if(depth[top[x]] < depth[top[y]]) {
            swap(x, y);
            swap(fir1, fir2); //注意
        }  
        anss = max(anss, query(id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) {
        swap(x, y);
        swap(fir1, fir2); //注意
    }
    swap(fir1, fir2); //最后要再交换一下
    anss = max(anss, query(id[x], id[y]));
    anss = max(anss, fir1+fir2);
    return anss;
}

//void ts(int l, int r) { //用于调试
//  cout << endl;
//  IT itr = split(r+1), itl = split(l);
//  for(; itl != itr; ++itl)
//    FOR(i, 1, itl->r-itl->l+1)
//      cout << itl->v << " ";
//  cout << endl;
//  return;
//}

int main() {
    in(n);
    FOR(i, 1, n)
      in(a[i]);
    FOR(i, 1, n-1) {
        in(x), in(y);
        add(x, y);
        add(y, x);
    }   
    dfs1(1, 0);
    dfs2(1, 1);
    FOR(i, 1, n)
      s.insert(node(i, i, dd[i]));
    s.insert(node(1, n+233, 0));
    in(m);
    FOR(i, 1, m) {
        in(t);
        if(t == 1) {
            in(x), in(y);
            fir1 = 0;
            fir2 = 0;
            out(qrange(x, y));
            putchar(10);
        }
        else {
            in(x), in(y), in(z);
            updrange(x, y, z);
        }
    }
}