头像

Crescent




离线:4小时前


最近来访(16)
用户头像
captainDDL
用户头像
M._9
用户头像
Grey啊
用户头像
KS阿杰
用户头像
2w1c1y1x
用户头像
赤旗
用户头像
zombotany
用户头像
王小强
用户头像
千山
用户头像
zeda
用户头像
endinggy
用户头像
iloveyyo
用户头像
凌乱之风
用户头像
zadkiel
用户头像
wzj
用户头像
Gtwff

分享 splay笔记

1.P2584 [ZJOI2006]GameZ游戏排名系统

const int N = 2.5e5 + 10;

int n, K, w[N], A[N];
string m[N];

typedef map <string, int> msi;
msi M;
msi::iterator it;

namespace Splay{
    #define lc(u) tr[u].s[0]
    #define rc(u) tr[u].s[1]
    #define p(u) tr[u].p
    #define sz(u) tr[u].sz
    #define v(u) tr[u].v
    #define root lc(0)
    struct node {int v, sz, p, s[2];} tr[N];

    inline int dir(int x) {return x == rc(p(x));}

    inline void pushup(int u) {
        sz(u) = sz(lc(u)) + sz(rc(u)) + 1;
    }

    void rotate(int x) {
        int y = p(x), z = p(y), k = dir(x);
        tr[z].s[dir(y)] = x, p(x) = z;
        int &b = tr[x].s[k ^ 1];
        p(tr[y].s[k] = b) = y;
        b = y, p(y) = x;
        pushup(y);
    }

    void splay(int x, int k = 0) {
        for (; p(x) != k; rotate(x))
            if (p(p(x)) != k) rotate(dir(x) ^ dir(p(x)) ? x : p(x));
        pushup(x);
    }


    void insert(int x, int v) {
        int y = 0, k = 0;
        if (root) for (y = root; k = (v <= v(y)), tr[y].s[k]; y = tr[y].s[k]); 
        tr[y].s[k] = x; v(x) = v, sz(x) = 1, p(x) = y, lc(x) = rc(x) = 0;
        splay(x);
    }

    void erase(int x) {
        if (p(x)) splay(x);
        if (lc(x) && rc(x))  {
            int y;
            for (y = rc(x); lc(y); y = lc(y));
            splay(y, x);
            p(lc(y) = lc(x)) = y;
            p(y) = 0; root = y;
            pushup(y);
        } else { 
            int k = (rc(x) > 0), b = tr[x].s[k];
            p(b) = 0; root = b;
        }
    }

    inline int rank(int x) { 
        splay(x);
        return sz(lc(x)) + 1;
    }

    int kth(int k) {
        int x = root;
        if (sz(x) < k) return -1;
        while (1) {
            int j = sz(lc(x));
            if (j >= k) x = lc(x);
            else if (k == j + 1) return x;
            else x = rc(x), k -= j + 1;
        }
    }

    int succ(int x) { 
        int y;
        splay(x); if (!(y = rc(x))) return -1;
        for (; lc(y); y = lc(y));
        return y;
    }

}
int main() {
    cin >> n;
    string op;
    for (int i = 1; i <= n; i ++ ) {
        if (cin >> op, op[0] == '+') {
            LL x; read(x);
            m[i] = op.erase(0, 1);
            if ((it = M.find(op)) == M.end()) M.insert({op, i});
            else {
                Splay::erase(it->se); it->se = i;
            }
            Splay::insert(i, x);
        } else if (op[1] >= '0' && op[1] <= '9') {
            int x = strtol(op.erase(0, 1).c_str(), NULL, 10);
            int k = 10, id = Splay::kth(x);
            for (; ;) {
                cout << m[id];
                id = Splay::succ(id);
                if ( -- k && ~id) cout << ' '; else break;
            }
            cout << "\n";
        } else {
            cout << Splay::rank(M[op.erase(0, 1)]) << '\n';
        }
    }
    return 0;
}


分享 stl笔记

Crescent
12天前

multiset s

tips:
*s.end()返回的是这个multiset s的元素个数

1.P1110 [ZJOI2007]报表统计
每次添加操作可以看成[a1…][a2..][an…]后面添加元素
对于MIN_GAP, 记录每个块的首尾值l[i],r[i],用multiset维护相邻两项的差值,则在第i块后加入k
需要加入两个新的值k-r[i],l[i+1]-k,删除原来的l[i+1]-r[i],并且更新r[i]=k
对于MIN_SORT_GAP,用一个multiset记录所有数,加入数时更新这个数的前后两个数与这个数的绝对值差即可
注意迭代器的边界问题,可以特判,也可以加入-INF,INF

const int N = 5e5 + 10;

int n, m, K, w[N], A[N], l[N], r[N];
int res = INT_MAX;

typedef multiset<int> mset;

mset s, d;
mset::iterator it;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) read(w[i]), l[i] = r[i] = w[i], s.insert(w[i]);
    int pre = 1e9;
    for (auto t : s) {
        if (pre != 1e9) chkmin(res, t - pre);
        pre = t;
    }
    for (int i = 1; i < n; i ++ ) {
        d.insert(abs(w[i + 1] - w[i]));
    }
    char op[20];
    while (m -- ) {
        scanf("%s", op);
        if (op[4] == 'R') {
            int a, b; read(a), read(b);
            if (a < n) {
                it = d.find(abs(l[a + 1] - r[a]));
                if (it != d.end()) d.erase(it);
                d.insert(abs(l[a + 1] - b));
            }
            d.insert(abs(b - r[a]));
            r[a] = b;
            it = s.lower_bound(b);
            if (it != s.end()) chkmin(res, abs(*it - b));
            if (it != s.begin()) chkmin(res, abs(* -- it - b));
            s.insert(b);
        } else if (op[4] == 'G') {
            cout << *d.begin() << '\n';
        } else {
            cout << res << '\n';
        }
    }
    return 0;
}

string s

s = s.erase(l, r) 即从s中删去[l, r)这一段
比如删除首字符 s = s.erase(0, 1)

c_str():生成一个const char*指针,指向以空字符终止的数组
strtoll(s.erase(0,1).c_str(), NULL, 10) 可以将s字符串去首字符后转化为long long



活动打卡代码 AcWing 1010. 拦截导弹

Crescent
1个月前

需要查询[1, i - 1]中w[j]>w[i]的f[j]的最大值 值域分块O(nsqrt(K))

// Problem: P1020 [NOIP1999 普及组] 导弹拦截
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1020
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10;

int n, m, K, A[N], len, L[N], R[N], lz[N], pos[N], S;
int f[N], h[N], w[N];

int query(int l) {
    int res = 0;
    for (int i = l; i <= R[pos[l]]; i ++ ) chkmax(res, A[i]);
    for (int i = pos[l] + 1; i <= S; i ++ ) chkmax(res, lz[i]);
    return res;
}

void add(int x, int v) {
    chkmax(A[x], v);
    chkmax(lz[pos[x]], v);
}

int main() {
    int x;
    int K = 0;
    while (cin >> x) w[ ++ n] = x, chkmax(K, x);
    int cnt = 0;
    len = sqrt(K); S = (K + len - 1) / len;
    for (int i = 1; i <= S; i ++ ) L[i] = R[i - 1] + 1, R[i] = len * i; R[S] = K;
    for (int i = 1; i <= S; i ++ ) for (int j = L[i]; j <= R[i]; j ++ ) pos[j] = i;
    memset(h, 0x3f, sizeof h);
    for (int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        chkmax(f[i], query(w[i]) + 1);
        int c = 1;
        while (h[c] < w[i]) c ++ ;
        if (c > cnt) h[ ++ cnt] = w[i];
        else h[c] = w[i];
        add(w[i], f[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) chkmax(res, f[i]);
    cout << res << '\n' << cnt << '\n';
    return 0;
}


分享 图论笔记

Crescent
2个月前

1.P5905 【模板】Johnson 全源最短路

 const int N = 3e3 + 10, M = 2e4 + 10, INF = 1e9;

int n, m, dist[N], h[N], e[M], ne[M], w[M], idx, G[N], cnt[N];
int q[N];

bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa(int dist[]) {
    for (int i = 1; i <= n; i ++ ) dist[i] = INF;
    int hh = 0, tt = 0;
    q[tt ++ ] = 0; dist[0] = 0, st[0] = 1;
    while (hh != tt) {
        int u = q[hh ++ ];
        if (hh == N) hh = 0;
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (chkmin(dist[j], dist[u] + w[i])) {
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    st[j] = true;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return false;
}

priority_queue<pi, vector<pi>, greater<pi>> Q;

void dijkstra(int S) {
    for (int i = 1; i <= n; i ++ ) dist[i] = INF, st[i] = 0;
    dist[S] = 0;
    Q.push({0, S});
    while (Q.size()) {
        auto t = Q.top();
        Q.pop();
        if (st[t.se]) continue;
        st[t.se] = true;
        for (int i = h[t.se]; ~i; i = ne[i]) {
            int j = e[i];
            if (chkmin(dist[j], t.fi + w[i])) {
                if (!st[j]) {
                    Q.push({dist[j], j});
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c);
    }
    for (int i = 1; i <= n; i ++ ) add(0, i, 0);
    if (spfa(G)) {
        puts("-1"); 
    } else {
        for (int u = 1; u <= n; u ++ )
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                w[i] += G[u] - G[j];
            }
        for (int i = 1; i <= n; i ++ ) {
            dijkstra(i);
            LL res = 0;
            for (int j = 1; j <= n; j ++ ) {
                int dis = dist[j];
                if (i != j && dist[j] != INF) dis -= G[i] - G[j];
                res += 1ll * dis * j;
            }
            cout << res << '\n';
        }
    }
    return 0;
}

2.P2195 HXY造公园
题意:
给出一个 n 个点,m 条边组成的森林,有 q 组询问:
操作1.给出点 x,求点 x 所在的树的直径
操作2.给出点 x,y 要求将 x,y 所在的树之间连一条边并构成一棵新的树,满足这个新的树的直径最小

给定一颗树,显然当边权全为1时,这棵树的直径的中点到达其他所有点的最大距离一定是这棵树里面
的所有点里最小的,注意边权不全为1时不成立

那么这题中,要使连接新边后新树的直径最小,新边所在的两个点必然是原来的树的直径的中点,且原树
对新树的贡献为树的直径/2向上取整 用并查集维护集合

const int N = 3e5 + 10, M = N << 1;

int n, m, k, h[N], e[M], ne[M], idx, d[N], p[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

int f[N], val;
void dfs(int u, int fa, int rt) {
    st[u] = true, p[u] = rt;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        dfs(j, u, rt);
        chkmax(val, f[u] + f[j] +1);
        chkmax(f[u], f[j] + 1);
    }
}
int main() {

    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b; read(a), read(b);
        add(a, b), add(b, a);
    }   

    for (int i = 1; i <= n; i ++ ) {
        if (!st[i]) {
            val = 0;
            dfs(i, -1, i);
            d[i] = val;
        }
    }
    while (k -- ) {
        int op, x, y; read(op), read(x);
        if (op == 1) {
            cout << d[find(x)] << '\n';
        } else {
            read(y);
            int pa = find(x), pb = find(y);
            if (pa == pb) continue;
            int res = max(max(d[pa], d[pb]), (d[pa] + 1) / 2 + (d[pb] + 1) / 2 + 1);
            p[pa] = pb;
            d[pb] = res;
        }
    }
    return 0;
}


活动打卡代码 AcWing 2226. 开店

Crescent
2个月前
// Problem: 开店
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/2228/
// Memory Limit: 256 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1.5e5 + 10, M = N << 1, Q = 2e5 + 10;

int n, m, h[N], e[M], ne[M], w[M], K, idx, age[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

struct Son {
    int age;
    LL dist;
    bool inline operator< (const Son &b) const {
        return age < b.age;
    }
};
vector<Son> son[N][3];
struct Fa {
    int wc, id;
    LL dist;
};
vector<Fa> f[N];
void get_dist(int u, int fa, int k, LL dist, int &wc, vector<Son> &p) {
    if (st[u]) return ;
    p.pb({age[u], dist});
    f[u].pb({wc, k, dist});
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, k, dist + w[i], wc, p);
    }
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        chkmax(ms, t);
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    for (int i = h[u], k = 0; ~i; i = ne[i]) {
        int j = e[i];
        auto &p = son[u][k];
        get_dist(j, u, k, w[i], u, p);
        k ++ ;
        p.pb({-1, 0}), p.pb({K + 1, 0});
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r) {
    LL res = 0;
    for (auto &t : f[u]) { //枚举u所在的所有重心 再枚举这些重心的所有子树
        if (age[t.wc] >= l && age[t.wc] <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ ) {
            if (i == t.id) continue;
            auto &p = son[t.wc][i];
        //  if (p.size() == 2) continue;
            if (!p.size()) continue;
            int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
            int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist; //还要加上b-a个重心到u的距离
        }
    }
    //u作为重心时的答案
    for (int i = 0; i < 3; i ++ ) {
        auto &p = son[u][i];
        //if (p.size() == 2) continue;
        if (!p.size()) continue;
        int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
        int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }
    return res;
}

int main() { 
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i ++ ) read(age[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0, L, R;
    while (m -- ) {
        int u, a, b; read(u), read(a), read(b);
        L = min((a + res) % K, (b + res) % K), R = max((a + res) % K, (b + res) % K);
        if (L > R) swap(L, R);
        cout << (res = query(u, L, R)) << '\n';
    }
    return 0;
}



Crescent
2个月前

点分治

1.
求树上长度不超过 K 的路径有多少条

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = N << 1;

int n, K, e[M], h[N], idx, ne[M], w[M];
int q[N], p[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        ms = max(ms, t);
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int &qt) {
    if (st[u]) return ;
    q[ ++ qt] = dist;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, dist + w[i], qt);
    }
}
int get(int a[], int k) {
    sort(a + 1, a + 1 + k);
    int res = 0;
    for (int i = 1, j = k; j >= 1; j -- ) {
        while (i < j && a[i] + a[j] <= K) i ++ ;
        if (i < j) res += i - 1;
        else res += j - 1;
    }
    return res;
}

int calc(int u) {
    if (st[u]) return 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0, res = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt);
        for (int k = 1; k <= qt; k ++ ) {
            if (q[k] <= K) res ++ ;
            p[ ++ pt] = q[k];
        }
    }
    res += get(p, pt);
    for (int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main() {
    while (cin >> n >> K, n || K) {
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        idx = 0;
        for (int i = 1; i < n; i ++ ) {
            int a, b, c; cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        cout << calc(1) << '\n';
    }
}

2.P3714 [BJOI2017]树的难题
遍历到某棵子树的某条路径时 设经过的边数为c, 当前子树连向重心的边的颜色为cl,当前路径的权值为v
则为了更新答案 还需要知道所有经过边数属于[l - c, r - c]的不同子树的路径中 连向重心
的边的颜色不为cl的最大权值v1和颜色同为cl的最大权值v2,比较max(v+v1,v+v2-w[cl]) 更新答案
显然可以将边数作为下标 用线段树维护区间最大值, 对于颜色 可以对于每个点的所有边按照颜色排序
这样我们遍历一个重心的所有点时,对于相同颜色的初边一定是连续处理的,
开两个线段树维护其他颜色和当前颜色的权值即可 O(nlog^2)
单调队列按秩合并可以一个log

const int N = 2e5 + 10, M = N << 1, INF = 2e9;

int n, m, L, R, h[N], e[M], ne[M], w[M], v[N], sz[N], S, maxP, pos, idx;
int res = -INF, q[N];
bool st[N];
pi p[N];

struct Tree {
    #define ro tr[u]
    #define lc tr[u].l
    #define rc tr[u].r
    int rt0, rt1, idx;
    struct Node {
        int l, r, v;
    } tr[N * 40];
    void modify(int &u, int l, int r, int x, int c) {
        if (!u) tr[u = ++ idx] = {0, 0, -INF};
        chkmax(ro.v, c);
        if (l == r) return ;
        int mid = l + r >> 1;
        if (x <= mid) modify(lc, l, mid, x, c);
        else modify(rc, mid + 1, r, x, c);
    }
    int query(int u, int l, int r, int x, int y) {
        if (x > y) return -INF;
        if (!u) return -INF;
        if (l >= x && r <= y) return ro.v;
        int mid = l + r >> 1, res = -INF;
        if (x <= mid) res = query(lc, l, mid, x, y);
        if (y > mid) chkmax(res, query(rc, mid + 1, r, x, y));
        return res;
    }
    void merge(int &u, int &v, int l, int r) {
        if (!u) { u = v; return; }
        if (!v) return ;
        chkmax(tr[u].v, tr[v].v);
        if (l == r) return ;
        int mid = l + r >> 1;
        merge(lc, tr[v].l, l, mid); merge(rc, tr[v].r, mid + 1, r);
    }
}T;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void get_wc(int u, int fa, int &wc) {
    sz[u] = 1; int ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        get_wc(j, u, wc);
        chkmax(ms, sz[j]);
        sz[u] += sz[j];
    }
    chkmax(ms, S - sz[u]);
    if (ms < maxP) wc = u, maxP = ms;
}

void get_dist(int u, int fa, int now, int last, int dist, int cnt, int &qt) {
    if (cnt > R) return ;
    chkmax(qt, cnt);
    q[cnt] = max(q[cnt], dist);
    chkmax(res, dist + T.query(T.rt0, 1, n, max(1, L - cnt), min(n, R - cnt))); //其他颜色
    chkmax(res, dist + T.query(T.rt1, 1, n, max(1, L - cnt), min(n, R - cnt)) - v[now]);
    if (cnt >= L && cnt <= R) chkmax(res, dist);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], cl = w[i];
        if (j == fa || st[j]) continue; 
        get_dist(j, u, now, cl, dist + (cl == last ? 0 : v[cl]), cnt + 1, qt);
    }
}

void calc(int u) {
    if (S == 1) return ;
    maxP = N, get_wc(u, -1, u), st[u] = true;
    int pt = 0; T.idx = T.rt0 = T.rt1 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        p[ ++ pt] = {w[i], j};
    }
    sort(p + 1, p + 1 + pt);
    for (int i = 1; i <= pt; i ++ ) {
        int j = p[i].se, cl = p[i].fi, qt = 0;
        get_dist(j, u, cl, cl, v[cl], 1, qt);
        for (int k = 1; k <= qt; k ++ ) {
            T.modify(T.rt1, 1, n, k, q[k]);
            q[k] = -INF;
        }
        if (i < pt && cl != p[i + 1].fi) {
            T.merge(T.rt0, T.rt1, 1, n);
            T.rt1 = 0;
        }
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        S = sz[j]; calc(j);
    }
}



int main() {
    cin >> n >> m >> L >> R;
    for (int i = 1; i <= m; i ++ ) read(v[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    S = n;
    for (int i = 1; i <= n; i ++ ) q[i] = -INF;
    calc(1);
    cout << res;
    return 0;
}

动态点分治:

如果树的结构不变 且多组询问的点不同 可以先预处理出所有的重心与信息
1.开店
题意:一棵树,有点权有边权,统计点权在[l, r]之间的所有点到u的距离之和 u有多组询问,强制在线
对于u,答案为除u所在子树的所有子树中的点到u的距离贡献+u所在子树的所有贡献+重心到u的贡献
前一个贡献可以将所有距离和对应的年龄存下来,按年龄排序,二分出l, r 用前缀和统计贡献
后一个贡献可以递归处理u所在子树,不断减小u所在子树的大小,重复上面的操作,
直到u为重心为止,统计统计u的所有子树的贡献结束
动态点分治:如果树的结构不发生变化 先预处理出所有会用到的重心
将每个重心连接到的所有子树的信息存在重心里面,记录信息所在子树的编号
同时记录每个点在哪些重心的管辖中,枚举这些重心的信息,统计除u所在子树的所有距离对u产生的贡献

const int N = 1.5e5 + 10, M = N << 1, Q = 2e5 + 10;

int n, m, h[N], e[M], ne[M], w[M], K, idx, age[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

struct Son {
    int age;
    LL dist;
    bool inline operator< (const Son &b) const {
        return age < b.age;
    }
};
vector<Son> son[N][3];
struct Fa {
    int wc, id;
    LL dist;
};
vector<Fa> f[N];
void get_dist(int u, int fa, int k, LL dist, int &wc, vector<Son> &p) {
    if (st[u]) return ;
    p.pb({age[u], dist});
    f[u].pb({wc, k, dist});
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, k, dist + w[i], wc, p);
    }
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        sum += t;
        chkmax(ms, t);
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    for (int i = h[u], k = 0; ~i; i = ne[i]) {
        int j = e[i];
        auto &p = son[u][k];
        get_dist(j, u, k, w[i], u, p);
        k ++ ;
        p.pb({-1, 0}), p.pb({K + 1, 0});
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r) {
    LL res = 0;
    for (auto &t : f[u]) { //枚举u所在的所有重心 再枚举这些重心的所有子树
        if (age[t.wc] >= l && age[t.wc] <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ ) {
            if (i == t.id) continue;
            auto &p = son[t.wc][i];
        //  if (p.size() == 2) continue;
            if (!p.size()) continue;
            int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
            int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist; //还要加上b-a个重心到u的距离
        }
    }
    //u作为重心时的答案
    for (int i = 0; i < 3; i ++ ) {
        auto &p = son[u][i];
        //if (p.size() == 2) continue;
        if (!p.size()) continue;
        int a = lower_bound(p.begin(), p.end(), (Son){l, -1}) - p.begin();
        int b = lower_bound(p.begin(), p.end(), (Son){r + 1, -1}) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }
    return res;
}

int main() { 
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i ++ ) read(age[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0, L, R;
    while (m -- ) {
        int u, a, b; read(u), read(a), read(b);
        L = min((a + res) % K, (b + res) % K), R = max((a + res) % K, (b + res) % K);
        if (L > R) swap(L, R);
        cout << (res = query(u, L, R)) << '\n';
    }
    return 0;
}

wating
1.
容斥

// Problem: P5306 [COCI2019] Transport
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5306
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = N << 1;

int n, h[N], e[M], w[M], ne[M], sz[N], maxP, S, A[N], idx;
LL q1[N], q2[N], p1[N], p2[N], res, ans;
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void get_wc(int u, int fa, int &wc) {
    sz[u] = 1; int ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        get_wc(j, u, wc);
        sz[u] += sz[j];
        chkmax(ms, sz[j]);
    }
    chkmax(ms, S - sz[u]);
    if (ms < maxP) maxP = ms, wc = u;
}

void get_dist(int u, int fa, LL dist1, LL dist2, int &qt) {
    q1[ ++ qt] = dist1, q2[qt] = dist2;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa || st[j]) continue;
        LL c1 = dist1 + A[u] - w[i]; //out
        LL c2 = dist2 + A[j] - w[i]; //in
        get_dist(j, u, c1, c2, qt);
    }
}
void calc(int u) {
    if (S == 1) return ;
    maxP = N; get_wc(u, -1, u);
    st[u] = true;
    int pt = 0; LL ans = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0; if (st[j]) continue;
        get_dist(j, u, A[u] - w[i], A[j] - w[i], qt);
        sort(q1 + 1, q1 + 1 + qt);
        ans -= 1ll * qt * (qt - 1);
        for (int k = 1; k <= qt; k ++ ) { //q->p
            if (q2[k] < 0) ans -= pt + 1; //+1是只有一边的情况
            else {
                ans -= lower_bound(p1 + 1, p1 + 1 + pt, -q2[k]) - p1 - 1;
            }
        }
        for (int k = 1; k <= pt; k ++ ) { //p->q
            if (p2[k] < 0) ans -= qt;
            else {
                ans -= lower_bound(q1 + 1, q1 + 1 + qt, -p2[k]) - q1 - 1;
            }
        }
        // for (int k = 1; k <= pt; k ++ ) cout << p[k] << ' '; cout << endl;
        for (int k = 1; k <= qt; k ++ ) {
            ++ pt;
            p1[pt] = q1[k]; //out
            p2[pt] = q2[k];
        }
        sort(p1 + 1, p1 + 1 + pt);
    }
    res += max(0ll, 1ll * pt * (pt - 1) + ans);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (st[j]) continue;
        S = sz[j]; 
        calc(j);
    }
}
int main() {
    // 考虑点p作为重心 u->p->v 只要在u到v这条路径上任意两个点满足路径和>燃料和 这条路径就非法
    // 考虑容斥,所有可能的点对减去删去所有不符合的情况即可
    cin >> n;
    for (int i = 1; i <= n; i ++ ) read(A[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    S = n;
    calc(1);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 264. 权值

Crescent
2个月前
// Problem: 权值
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/266/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e5 + 10, S = 1e6 + 10, M = N << 1, INF = N;

int n, m, h[N], e[M], w[M], ne[M], idx, f[S];
int res = INF;
bool st[N];
pi q[N], p[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void get_dist(int u, int fa, int dist, int cnt, int &qt) {
    if (st[u] || dist > m) return ;
    q[ ++ qt] = {dist, cnt};
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        chkmax(ms, t);
        sum += t;
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, u, w[i], 1, qt);
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            if (t.fi == m) chkmin(res, t.se);
            chkmin(res, t.se + f[m - t.fi]);
            p[ ++ pt] = t;
        }
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            chkmin(f[t.fi], t.se);
        }
    }
    //回溯
    for (int i = 1; i <= pt; i ++ )
        f[p[i].fi] = INF;   
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}


int main() {
    //f[i]=j表示距离重心长度为i的点最少经过j条边到达
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    memset(f, 0x3f, sizeof f);
    calc(1);
    if (res == INF) res = -1;
    cout << res;
    return 0;
}


活动打卡代码 AcWing 252. 树

Crescent
2个月前
// Problem: 树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/254/
// Memory Limit: 10 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 10, M = N << 1;

int n, K, q[N], p[N], idx, h[N], e[M], ne[M], w[M];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        chkmax(ms, t);
        sum += t;
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int &qt) {
    if (st[u]) return ; //防止往回搜到重心
    q[ ++ qt] = dist;
    for (int i = h[u]; ~i; i = ne[i]) 
        if (e[i] != fa) get_dist(e[i], u, dist + w[i], qt);
}

int get(int a[], int k) {
    sort(a + 1, a + k + 1);
    int res = 0;
    for (int i = 1, j = k; j >= 1; j -- ) {
        while (a[i] + a[j] <= K && i < j) i ++ ;
        if (i < j) res += i - 1;
        else res += j - 1;
    }
    return res;
}

int calc(int u) {
    if (st[u]) return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;

    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt); //第3类路径
        for (int k = 1; k <= qt; k ++ ) {
            if (q[k] <= K) res ++ ; //处理第1类路径
            p[ ++ pt] = q[k];
        } 
    }
    res += get(p, pt); 
    for (int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main() {
    // 点分治+容斥 将路径分为3种 1.树内与重心 2.跨过重心在两棵子树内 3.在同一棵子树内
    // 第3种递归查询 第1种获得每科子树的所有距离时记录 对于第2种:考虑容斥 将除了重心之外
    // 的所有子树中的点加入一个数组 求该数组的任意两点可以组成的答案再减去两点处于同一棵
    // 子树的答案就是该答案
    while (cin >> n >> K, n || K) {
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        idx = 0;
        for (int i = 1; i < n; i ++) {
            int a, b, c; read(a), read(b), read(c);
            add(a, b, c), add(b, a, c);
        }
        cout << calc(1) << '\n';
    }
    return 0;
}


活动打卡代码 AcWing 2847. 老C的任务

Crescent
3个月前
// Problem: 老C的任务
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2849/
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5e5 + 10;

int n, m;
LL res[N];

struct E {
    int x, y, z, v, sign, id;
    LL ans;
    inline bool operator< (const E &t) {
        if (x != t.x) return x < t.x;
        if (y != t.y) return y < t.y;
        return z < t.z;
    }
}e[N], d[N];

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    LL sv = 0;
    for (int j = mid + 1, i = l, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[i].y <= e[j].y)) {
            sv += e[i].v; d[k] = e[i ++ ];
        } else {
            e[j].ans += e[j].sign * e[j].z * sv; d[k] = e[j ++ ];
        }
    }
    for (int j = l; j <= r; j ++ ) e[j] = d[j];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        int x, y, p;
        read(x), read(y), read(p);
        e[i] = {x, y, 0, p};
    }
    int idx = n;
    for (int i = 1; i <= m; i ++ ) {
        int a, b, c, d;
        read(a), read(b), read(c), read(d);
        e[ ++ idx] = {a - 1, b - 1, 1, 0, 1, i};
        e[ ++ idx] = {a - 1, d, 1, 0, -1, i};
        e[ ++ idx] = {c, b - 1, 1, 0, -1, i};
        e[ ++ idx] = {c, d, 1, 0, 1, i};
    }   
    sort(e + 1, e + 1 + idx);
    cdq(1, idx);
    for (int i = 1; i <= idx; i ++ ) 
        res[e[i].id] += e[i].ans;
    for (int i = 1; i <= m; i ++ ) 
        cout << res[i] << '\n';
    return 0;
}



Crescent
3个月前

1.P3157 [CQOI2011]动态逆序对
一维为编号(自带) 二维为权值(排序) 三维为时间(BIT)
[l, r]区间中 [l, mid]的逆序对为[mid+1, r]中权值小于且时间大于他的数
对于[mid+1, r]中的数,逆序对为[l,mid]中权值大于且时间大于他的数 又权值
升序排序故对于[l,mid] i从l开始r从mid+1开始 对于[mid+1,r] i从mid开始 j从r开始
这题用分块套bit也可以

const int N = 1e5 + 10, M = 5e4 + 10;

int n, m, K, pos[N], c[N], ans[M];

struct E {
    int v, t;
    bool operator< (const E &t) const {
        return v < t.v;
    }
}e[N], d[N];

void inline add(int x, int k) {
    for (; x <= K; x += x & -x) c[x] += k;
}

int inline ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}

void inline del(int x) {
    for (; x <= K; x += x & -x) c[x] = 0;
}

void cdq(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    for (int i = l, j = mid + 1; i <= mid; i ++ ) {
        while (j <= r && e[j].v < e[i].v) add(e[j ++ ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }   
    for (int j = mid + 1; j <= r; j ++ ) del(e[j].t);
    for (int i = r, j = mid; i >= mid + 1; i -- ) {
        while (j >= l && e[j].v > e[i].v) add(e[j -- ].t, 1);
        ans[e[i].t] += ask(m + 1) - ask(e[i].t);
    }
    for (int j = l; j <= mid; j ++ ) del(e[j].t);
    for (int i = l, j = mid + 1, k = l; k <= r; k ++ ) {
        if (j > r || (i <= mid && e[j].v > e[i].v)) d[k] = e[i ++ ];
        else d[k] = e[j ++ ];
    }
    for (int i = l; i <= r; i ++ ) e[i] = d[i];
    //sort(e + l, e + r + 1);  //不开O2的话sort比临时数组慢很多
}

int main() {
     cin >> n >> m;
     for (int i = 1; i <= n; i ++ ) {
        int x;
        read(x);
        e[i] = {x, m + 1};
        pos[x] = i;
     }
     for (int i = 1; i <= m; i ++ ) {
        int x;
        read(x);
        e[pos[x]].t = i;
     }
     K = n;
     LL res = 0;
     for (int i = n; i; i -- ) {
        res += ask(e[i].v);
        add(e[i].v, 1);
     }
     memset(c, 0, sizeof c);
     K = m + 1;
     cdq(1, n);
     cout << res << '\n';
     for (int i = 1; i < m; i ++ ) {
        res -= ans[i];
        cout << res << '\n';
     }
     return 0;
}