- 学到了维护子树信息的时候用dfsdfsdfs序套主席树节省线段树空间.
- 学到了怎么用指针写可持久化线段树…emmm…
CODE
只贴上3551加强版带强制在线的代码
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; for(;!isdigit(ch=getc());)if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 200005;
const int MAXM = 500005;
struct edge{ int u, v, w; }e[MAXM];
inline bool cmp(const edge &A, const edge &B) { return A.w < B.w; }
int n, m, q, tot, w[MAXN], b[MAXN], bel[MAXN], in[MAXN], out[MAXN], id[MAXN], tmr;
int fir[MAXN], to[MAXN], nxt[MAXN], f[MAXN][18], g[MAXN][18], cnt;
struct seg {
seg *ls, *rs;
int sum;
inline void* operator new (size_t, seg *l, seg *r, int _) {
seg *re;
static seg *mempool, *C;
if(C == mempool) mempool = (C = new seg[1<<15]) + (1<<15);
re = C++;
re->ls = l;
re->rs = r;
re->sum = _;
return re;
}
}*rt[MAXN];
inline void Add(int u, int v) {
to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;
}
int find(int x) {
if(bel[x] == x || !bel[x]) return bel[x] = x;
else return bel[x] = find(bel[x]);
}
inline void Kruskal() {
sort(e + 1, e + m + 1, cmp);
for(int i = 1; i <= m; ++i) {
int x = find(e[i].u), y = find(e[i].v);
if(x != y) { ++n;
Add(n, x), Add(n, y);
f[x][0] = f[y][0] = n;
g[x][0] = g[y][0] = e[i].w;
bel[x] = bel[y] = n;
}
}
}
void dfs(int x) {
id[in[x] = ++tmr] = x;
for(int i = fir[x]; i; i = nxt[i])
dfs(to[i]);
out[x] = tmr;
}
inline int Get_rt(int x, int lim) {
for(int j = 17; ~j; --j)
if(f[x][j] && g[x][j] <= lim)
x = f[x][j];
return x;
}
seg* insert(seg *p, int l, int r, int x) {
if(l == r) return new(0x0, 0x0, p->sum+1) seg;
int mid = (l + r) >> 1;
if(x <= mid) return new(insert(p->ls, l, mid, x), p->rs, p->sum+1) seg;
else return new(p->ls, insert(p->rs, mid+1, r, x), p->sum+1) seg;
}
int query(seg *x, seg *y, int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) >> 1;
if(y->rs->sum - x->rs->sum >= k) return query(x->rs, y->rs, mid+1, r, k);
else return query(x->ls, y->ls, l, mid, k - y->rs->sum + x->rs->sum);
};
int main () {
read(n), read(m), read(q);
for(int i = 1; i <= n; ++i)
read(w[i]), b[++tot] = w[i];
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
for(int i = 1; i <= n; ++i)
w[i] = lower_bound(b + 1, b + tot + 1, w[i]) - b;
for(int i = 1; i <= m; ++i)
read(e[i].u), read(e[i].v), read(e[i].w);
Kruskal();
dfs(n);
for(int j = 1; j < 18; ++j)
for(int i = 1; i <= n; ++i) if(f[i][j-1])
f[i][j] = f[f[i][j-1]][j-1],
g[i][j] = max(g[i][j-1], g[f[i][j-1]][j-1]);
rt[0] = new(0x0, 0x0, 0) seg; //init
rt[0]->ls = rt[0]->rs = rt[0];
for(int i = 1; i <= n; ++i)
if(w[id[i]]) rt[i] = insert(rt[i-1], 0, tot, w[id[i]]);
else rt[i] = rt[i-1];
int ans = 0, v, x, k; b[0] = -1;
while(q--) {
read(v), read(x), read(k);
v ^= ans, x ^= ans, k ^= ans;
int root = Get_rt(v, x);
if(out[root]-in[root]+1 < k) printf("%d\n", ans = -1);
else printf("%d\n", ans = b[query(rt[in[root]-1], rt[out[root]], 0, tot, k)]);
if(!~ans) ans = 0;
}
}