盖一个五层的教学楼真是智障

教室放在五楼还没电梯就更智障了

懵逼的题目

Peaks

第900个A的有点真实

Peaks加强版

加强版过的比普通版还多就更真实了

扯淡的题解

Peaks

好像上个寒假Rivendell学长讲过这题来着(好像还是我回答的来着, 然而过了一年就变得啥都不会了可真是太真实了)

从小到大枚举边 然后权值线段树合并就完事了

Peaks加强版

被教育了一种新的玩具叫kruskal重构树

kruskal重构树越靠上边权越大

所以要找边权不超过某个值的区间我们只需要找他的子树所在的区间就行了

在重构树的DFS序上建主席树就完事了

沙茶的 代码

Peaks

数组开小了 身败名裂

合并的时候没有判断是不是已经在一个集合里了 身败名裂

被卡常了 身败名裂

快读写错了 身败名裂

/**************************************************************
    Problem: 3545
    User: Cansult
    Language: C++
    Result: Accepted
    Time:8312 ms
    Memory:72120 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (500000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define pii pair<int, int>
using namespace std;
struct bcj {
    int fa, size;
} fa[MAXN];
struct node {
    int le, ri, zh, ls, rs;
} b[MAXN << 2];
struct edg {
    int from, to, cost;
} tb[MAXN];
struct ques {
    int from, cap, k, bh;
} que[MAXN];
int root[MAXN], n, m, q, cntb, h[MAXN], sorh[MAXN], ans[MAXN];
queue<int> trash;
int find(int x) { return (fa[x].fa == x) ? x : (fa[x].fa = find(fa[x].fa)); }
inline int newnode() {
    int re;
    if (trash.size())   re = trash.front(), trash.pop();
    else    re = ++cntb;
    return re;
}
void xg(int& dq, int le, int ri, int wz, int zh) {
    if (!dq)    dq = newnode(), b[dq].le = le, b[dq].ri = ri, b[dq].zh = 0;
    b[dq].zh += zh;
    if (le == ri)   return ;
    int mi = (le + ri) >> 1;
    if (wz > mi) xg(b[dq].rs, mi + 1, ri, wz, zh);
    else    xg(b[dq].ls, le, mi, wz, zh);
}
void GG(int& fa, int dq) {
    if (!fa)    fa = newnode(), b[fa] = b[dq], b[dq].ls = b[dq].rs = 0;
    else    b[fa].zh += b[dq].zh;
    if (b[dq].le == b[dq].ri) {
        trash.push(dq);
        return ;
    }
    if (b[dq].ls)   GG(b[fa].ls, b[dq].ls);
    if (b[dq].rs)   GG(b[fa].rs, b[dq].rs);
    trash.push(dq);
}
void uni(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fa[fx].size < fa[fy].size)   swap(fx, fy);
    fa[fy].fa = fx, fa[fx].size += fa[fy].size;
    GG(root[fx], root[fy]);
}
bool cmpq(ques x, ques y) { return x.cap < y.cap; }
bool cmpe(edg x, edg y) { return x.cost < y.cost; }
int cx(int dq, int k) {
    if (b[dq].zh < k)    return -1;
    if (b[dq].le == b[dq].ri)   return b[dq].le;
    if (b[dq].rs && b[b[dq].rs].zh >= k) return cx(b[dq].rs, k);
    else    return cx(b[dq].ls, k - b[b[dq].rs].zh);
}
void solve() {
    sort(que + 1, que + q + 1, cmpq);
    sort(tb + 1, tb + m + 1, cmpe);
    for (int i = 1; i <= n; i++) xg(root[i], 1, n, h[i], 1), fa[i].fa = i, fa[i].size = 1;
    int dqe = 1;
    for (int i = 1; i <= q; i++) {
        while (dqe <= m && tb[dqe].cost <= que[i].cap) {
            if (find(tb[dqe].from) != find(tb[dqe].to))
                uni(tb[dqe].from, tb[dqe].to);
            ++dqe;
        }
        ans[que[i].bh] = cx(root[find(que[i].from)], que[i].k);
    }
    for (int i = 1; i <= q; i++)
        if (~ans[i])    printf("%d\n", sorh[ans[i]]);
        else    puts("-1");
}
inline int read() {
    int re = 0;
    char x = 0;
    while (x < '0' || x > '9')    x = getchar();
    while (x <= '9' && x >= '0')  re = (re << 1) + (re << 3) + x - '0', x = getchar();
    return re;
}
int main () {
    n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++) h[i] = read(), sorh[++sorh[0]] = h[i];
    sort(sorh + 1, sorh + sorh[0] + 1);
    sorh[0] = unique(sorh + 1, sorh + sorh[0] + 1) - sorh - 1;
    for (int i = 1; i <= n; i++) h[i] = lower_bound(sorh + 1, sorh + sorh[0] + 1, h[i]) - sorh;
    for (int i = 1; i <= m; i++) tb[i].from = read(), tb[i].to = read(), tb[i].cost = read();
    for (int i = 1; i <= q; i++) que[i].from = read(), que[i].cap = read(), que[i].k = read(), que[i].bh = i;
    solve();    
    return 0;
}

Peaks加强版

主席树递归的时候pre写的rs, dq写成了ls… 丢人

居然把重构树中新加入的点也给放进主席树里了… 丢人

卡空间让人想吐…

/**************************************************************
    Problem: 3551
    User: Cansult
    Language: C++
    Result: Accepted
    Time:15264 ms
    Memory:112160 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (300000 + 1)
#define MAXM (500000 + 5)
#define MAXT (100000 + 1)
#define MAXL (20 + 1)
#define LL long long
#define pii pair<int, int>
using namespace std;
struct node {
    int le, ri, ls, rs, zh;
} b[MAXN * 9];
struct edg {
    int from, to, cost, next;
} te[MAXM], tb[MAXN << 1];
int n, m, a[MAXN], cnta, fat[MAXN], fak[MAXN], d[MAXN][MAXL], tn, cntb, g[MAXN], di[MAXN], lgn, root[MAXN], cntn, h[MAXT], sorh[MAXT];
pii son[MAXN];
bool cmp(edg x, edg y) { return x.cost < y.cost; }
int find(int* fa, int x) { return (fa[x] == x) ? x : (fa[x] = find(fa, fa[x])); }
void uni(int* fa, int x, int y) { fa[find(fa, x)] = find(fa, y); }
int lg(int x) {
    int re = 0;
    while ((1 << re) < x)  ++re;
    return re;
}
void adn(int from, int to) {
    tb[++cntb].next = g[from];
    tb[cntb].from = from, tb[cntb].to = to;
    g[from] = cntb;
}
void kruskal() {
    sort(te + 1, te + m + 1, cmp);
    for (int i = 1; i < MAXN; i++)   fat[i] = fak[i] = i;
    int cnte = 0;
    tn = n;
    for (int i = 1; i <= m; i++)
        if (find(fat, te[i].from) != find(fat, te[i].to))   {
            if (!di[te[i].from])    di[te[i].from] = te[i].cost;
            if (!di[te[i].to])  di[te[i].to] = te[i].cost;
            di[++tn] = te[i].cost;
            adn(tn, find(fak, te[i].from)), adn(find(fak, te[i].from), tn);
            adn(tn, find(fak, te[i].to)), adn(find(fak, te[i].to), tn);
            uni(fat, te[i].from, te[i].to);
            uni(fak, te[i].from, tn), uni(fak, te[i].to, tn);
            ++cnte;
            if (cnte == n - 1)  break;
        }
}
void dfs(int dq) {
    a[son[dq].first = ++cnta] = dq;
    for (int i = 1; i <= lgn; i++)   d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = g[dq]; i; i = tb[i].next)
        if (tb[i].to != d[dq][0])
            d[tb[i].to][0] = dq, dfs(tb[i].to);
    son[dq].second = cnta;
}
int cxroot(int x, int cap) {
    for (int i = lgn; i >= 0; i--)
        if (di[d[x][i]] <= cap)
            x = d[x][i];
    return x;
}
void ins(int pre, int& dq, int le, int ri, int wz, int zh) {
    dq = ++cntn;
    b[dq].le = le, b[dq].ri = ri, b[dq].zh = b[pre].zh + zh;
    if (le == ri)   return ;
    int mi = (le + ri) >> 1;
    if (wz <= mi)    b[dq].rs = b[pre].rs, ins(b[pre].ls, b[dq].ls, le, mi, wz, zh);
    else    b[dq].ls = b[pre].ls, ins(b[pre].rs, b[dq].rs, mi + 1, ri, wz, zh);
}
int cx(int pre, int dq, int k) {
    if (b[dq].zh - b[pre].zh < k)    return -1;
    if (b[dq].le == b[dq].ri)   return b[dq].le;
    if (b[b[dq].rs].zh - b[b[pre].rs].zh >= k)   return cx(b[pre].rs, b[dq].rs, k);
    else    return cx(b[pre].ls, b[dq].ls, k - b[b[dq].rs].zh + b[b[pre].rs].zh);
}
inline int read() {
    int re = 0;
    char x = 0;
    while (x < '0' || x > '9')    x = getchar();
    while (x >= '0' && x <= '9')  re = (re << 1) + (re << 3) + x - '0', x = getchar();
    return re;
}
int main() {
    int q;
    n = read(), m = read(), q = read();
    lgn = lg(n);
    for (int i = 1; i <= n; i++) h[i] = read(), sorh[++sorh[0]] = h[i];
    sort(sorh + 1, sorh + sorh[0] + 1);
    sorh[0] = unique(sorh + 1, sorh + sorh[0] + 1) - sorh - 1;
    for (int i = 1; i <= n; i++) h[i] = lower_bound(sorh + 1, sorh + sorh[0] + 1, h[i]) - sorh;
    for (int i = 1; i <= m; i++) te[i].from = read(), te[i].to = read(), te[i].cost = read();
    kruskal();
    d[tn][0] = tn;
    dfs(tn);
    for (int i = 1; i <= cnta; i++)  ins(root[i - 1], root[i], 1, sorh[0], (a[i] <= n) ? h[a[i]] : 1, a[i] <= n);
    for (int i = 1, lastans = 0, srf, src, srk; i <= q; i++) {
        srf = read(), src = read(), srk = read();
        if (lastans == -1)  lastans = 0;
        srf ^= lastans, src ^= lastans, srk ^= lastans;
        int mindn = cxroot(srf, src);
        lastans = cx(root[son[mindn].first - 1], root[son[mindn].second], srk);
        if (~lastans)   lastans = sorh[lastans];
        printf("%d\n", lastans);
    }
    return 0;
}

By 准备退役旅游的 Cansult