## 题目描述

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.

• Reads $N$ numbers from the input.
• Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.

## 代码

/*
* Beware of Bigfoot!
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>

static int const N = 60005;
static int const NM = 2000000;
int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N];
struct Query {
int o, i, j, k;
} q[N];
struct SegmentTree {
int ch[2], sum;
} nd[NM];

int create(int rt = 0) { return nd[++nn] = nd[rt], nn; }

int arr_insert(int rt, int p) {
rt = create(rt), ++nd[rt].sum;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum,
cur = nd[cur].ch[b];
b ? L = MID + 1 : R = MID;
}
return rt;
}

void bit_insert(int &rt, int p, int v) {
if (rt == 0)
rt = create();
nd[rt].sum += v;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
if (nd[cur].ch[b] == 0)
nd[cur].ch[b] = create();
nd[nd[cur].ch[b]].sum += v;
int tmp = nd[cur].ch[b];
cur = tmp, b ? L = MID + 1 : R = MID;
}
}

int bit_add(int p, int v, int c) {
for (; p <= n; p += p & -p)
bit_insert(bit_rt[p], v, c);
}

int main() {
int T;
scanf("%d", &T);
for (; T--;) {
std::map<int, int> mp;
memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), mp[a[i]] = 0;
for (int i = 1; i <= m; ++i) {
char c;
scanf(" %c", &c);
if (c == 'Q')
q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
else
q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0;
}
int cnt = 0;
for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
rec[cnt] = it->first, it->second = cnt++;
for (int i = 1; i <= n; ++i)
arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]);
for (int i = 1; i <= m; ++i) {
if (q[i].o == 0) {
std::vector<int> a, b;
a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]);
for (int p = q[i].i - 1; p; p -= p & -p)
a.push_back(bit_rt[p]);
for (int p = q[i].j; p; p -= p & -p)
b.push_back(bit_rt[p]);
int L = 0, R = N;
for (; L < R;) {
int sum = 0;
for (int i = 0; i < a.size(); ++i)
sum -= nd[nd[a[i]].ch[0]].sum;
for (int i = 0; i < b.size(); ++i)
sum += nd[nd[b[i]].ch[0]].sum;
int MID = L + R >> 1;
if (sum < q[i].k) {
L = MID + 1, q[i].k -= sum;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[1];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[1];
} else {
R = MID;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[0];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[0];
}
}
printf("%d\n", rec[L]);
} else
}
}
return 0;
}


## 题目描述

Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.
The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.
Now to simplify the problem, assume you have $n$ ponies (numbered from $1$ to $n$). Each pony has three attributes:

• $s_i$: amount of mana that the pony has at time $0$;
• $m_i$: maximum mana that the pony can have;
• $r_i$: mana regeneration per unit time.

Lord Tirek will do $m$ instructions, each of them can be described with three integers: $t_i, l_i, r_i$. The instruction means that at time $t_i$, Tirek will use Absorb Mana on ponies with numbers from $l_i$ to $r_i$ (both borders inclusive). We’ll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

## 代码

/*
* So, is the glass half empty, half full, or just twice as large as it needs to
* be?
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

template <typename T> void read(T &n) {
char c;
for (; (c = getchar()) < '0' || c > '9';)
;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
;
}

typedef long long ll;
typedef int const ic;

static ic N = 100005;
int numn, root[N << 1];
struct Pony {
int s, m, r;
} p[N];
struct Event {
int t, p, b;
} e[N];
struct Query {
int t, l, r;
bool operator<(Query const &a) const { return l < a.l; }
} q[N];
struct SegmentTree {
int child[2];
ll a, b;
} node[N << 6];
std::set<Query> st;

void update(ic &root) {
if (!root)
return;
node[root].a = node[node[root].child[0]].a + node[node[root].child[1]].a;
node[root].b = node[node[root].child[0]].b + node[node[root].child[1]].b;
}

void modify(int &root, ic &nl, ic &nr, ic &p, ic &a, ic &b, ic &flag) {
if (p > nr || nl > p)
return;
if (flag)
node[++numn] = node[root], root = numn;
else if (!root)
root = ++numn;
if (nl == nr) {
node[root].a = a, node[root].b = b;
return;
}
ic mid = (nl + nr) >> 1;
modify(node[root].child[0], nl, mid, p, a, b, flag);
modify(node[root].child[1], mid + 1, nr, p, a, b, flag);
update(root);
}

ll query(ic &root, ic &nl, ic &nr, ic &t, ic &l, ic &r) {
if (!root || l > nr || nl > r)
return 0;
if (l <= nl && nr <= r)
return node[root].a * t + node[root].b;
ic mid = (nl + nr) >> 1;
return query(node[root].child[0], nl, mid, t, l, r) +
query(node[root].child[1], mid + 1, nr, t, l, r);
}

int main() {
int n, m;
for (int i = 0; i < n; ++i)
for (int i = 0; i < m; ++i)
for (int i = 0; i < n; ++i)
modify(root[0], 0, n - 1, i, p[i].r, 0, 0),
e[i] = (Event){p[i].r ? p[i].m / p[i].r + 1 : N, i, p[i].m};
std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
for (int i = 1, p = 0; i < N; ++i) {
root[i] = root[i - 1];
for (; p < n && e[p].t == i; ++p)
modify(root[i], 0, n - 1, e[p].p, 0, e[p].b, 1);
}
for (int i = 0; i < n; ++i)
modify(root[N], 0, n - 1, i, p[i].r, p[i].s, 0),
e[i] = (Event){p[i].r ? (p[i].m - p[i].s) / p[i].r + 1 : N, i, p[i].m};
std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
for (int i = 1, p = 0; i < N; ++i) {
root[N + i] = root[N + i - 1];
for (; p < n && e[p].t == i; ++p)
modify(root[N + i], 0, n - 1, e[p].p, 0, e[p].b, 1);
}
st.insert((Query){0, 0, n - 1});
for (int i = 0; i < m; ++i) {
auto rec = st.lower_bound((Query){q[i].t, q[i].l, q[i].r});
if (rec == st.end())
--rec;
for (; rec != st.begin() && rec->r >= q[i].l; --rec)
;
if (rec->r < q[i].l)
++rec;
auto tmp = rec;
Query l = (Query){rec->t, rec->l, q[i].l - 1};
ll ans = 0;
for (; rec != st.end() && rec->l <= q[i].r; ++rec)
ans += rec->t ? query(root[std::min(q[i].t - rec->t, N - 1)], 0, n - 1,
q[i].t - rec->t, std::max(rec->l, q[i].l),
std::min(rec->r, q[i].r))
: query(root[std::min(q[i].t - rec->t, N - 1) + N], 0,
n - 1, q[i].t - rec->t, std::max(rec->l, q[i].l),
std::min(rec->r, q[i].r));
printf("%lld\n", ans), --rec;
Query r = (Query){rec->t, q[i].r + 1, rec->r};
for (; tmp != st.end() && tmp->l <= q[i].r;)
st.erase(tmp++);
st.insert((Query){q[i].t, q[i].l, q[i].r});
if (l.l <= l.r)
st.insert(l);
if (r.l <= r.r)
st.insert(r);
}
return 0;
}


## 题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager r(T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager w(T x) {
write(x); return *this;
}
} io;

struct SegmentTree {
private:
static const int N = 9000000;
int tot;
struct Node {
int val, child[2];
} node[N];
int add_point(int root, int l, int r, int p) {
if (l == r) {
node[++ tot] = (Node) { node[root].val, 0, 0 };
}
int mid = l + r >> 1, rec = ++ tot;
node[rec] = (Node) { 0, 0, 0 };
if (p <= mid) {
node[rec].child[1] = node[root].child[1];
node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
} else {
node[rec].child[0] = node[root].child[0];
node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
}
node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
return rec;
}
int query_point(int root1, int root2, int l, int r, int p) {
if (node[root2].val - node[root1].val < p) return -1;
if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
int mid = l + r >> 1, res = -1;
if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
if (~ res) return res;
res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
return res;
}

public:
int n, cnt, root[N];
root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
}
int find(int l, int r, int p) {
return query_point(root[l - 1], root[r], 1, n, p);
}
void print() {
cout << cnt << endl;
for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
cout << endl << tot << endl;
for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
}
};

struct Solver {
private:
int n, q;
SegmentTree tree;
void input() {
io.r(n).r(q);
tree.n = n;
for (int i = 1; i <= n; ++ i) {
}
}
void process() {
int l, r, k; io.r(l).r(r).r(k);
int p = (r - l + 1) / k + 1;
io.w(tree.find(l, r, p)).w('\n');
}

public:
void solve() {
input(); while (q --) process();
}
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

## 代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
memset(c, 0, sizeof(c));
int p = 0, q = 1, ret = 0;
while (q <= n) {
int cnt = 1; c[a[q]] = 1;
while (q < n) {
if (cnt < t || c[a[q + 1]]) {
cnt += !c[a[++q]], ++c[a[q]];
} else break;
}
while (p < q) --c[a[++p]];
++q, ++ret;
}
return ret;
}
void solve(int l, int r) {
if (l > r) return;
ans[l] = get(l), ans[r] = get(r);
if (ans[l] == ans[r]) {
for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
return;
}
int mid = l + r >> 1;
solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
solve(1, n);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
printf("\n");
return 0;
}


## 代码2

#include <cstdio>
using namespace std;
struct node_type {
int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
if (l == r) {
node[++tot].val = node[root].val + val;
node[tot].child[0] = node[tot].child[1] = 0;
}
int mid = l + r >> 1, ch;
if (p <= mid) {
ch = insert_line(node[root].child[0], l, mid, p, val);
node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
} else {
ch = insert_line(node[root].child[1], mid + 1, r, p, val);
node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
}
node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
}
int query(int root, int l, int r, int p) {
if (l == r) if (p >= node[root].val) return l; else return l + 1;
int mid = l + r >> 1;
if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
for (int i = 2; i <= n; ++i) {
int rt = root[i - 1];
if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
}
for (int i = 1; i <= n; ++i) {
if (ans != 1) {
ans = 0;
int l = n, r;
while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
}
printf("%d ", ans);
}
printf("\n");
return 0;
}


## 题目描述

A little boy Pishty lives in Khust – an ancient town in Uzhlyandia with their medieval castles and smart bears.
The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom’s army. Pishty also like this castle because it hides old secrets in long halls and high towers…
The castle can be described as an undirected tree with $N$ vertices and $N-1$ edges. Each edge has a magic number $C$.
When a group of tourists visit the castle, they are interested in a path between vertices $U$ and $V$. They think that an edge is interesting if its magic number is less than or equal to $K$. The total attractivity of the path is the xor of all interesting edges on it.
The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor’s knight, he wants to know all of this information too. But he can’t do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.
Given $M$ groups of tourists, find the total attractivity of the path for each group.

## 代码1

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
long long u, v, c, nxt;
bool operator < (const edge &a) const { return c < a.c; }
} e[200001], r[100001];
long long u, v, k, id, ans;
bool operator < (const ask &a) const { return k < a.k; }
} a[100001];
struct binary_indexed_tree {
long long n;
vector<long long> a;
void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
void add(long long p, long long t) {
for (long long i = p; i < n; i += i & -i) a[i] ^= t;
}
long long sum(long long p) {
long long ret = 0;
for (long long i = p; i; i -= i & -i) ret ^= a[i];
return ret;
}
} tree[100001];
long long T, n, m, nume, tot, pnt, h[100001], size[100001];
long long up[100001], down[100001], father[100001], dist[100001];
long long id[100001], len[100001], cnt[100001];
void add_edge(long long u, long long v, long long c) {
e[++nume].u = u, e[nume].v = v, e[nume].c = c;
e[nume].nxt = h[u], h[u] = nume;
e[++nume].u = v, e[nume].v = u, e[nume].c = c;
e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa, long long depth) {
long long ma = 0;
size[t] = 1, father[t] = fa, dist[t] = depth;
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
dfs(e[i].v, t, e[i].c);
ma = max(ma, size[e[i].v]);
size[t] += size[e[i].v];
}
}
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa && ma == size[e[i].v]) { down[t] = e[i].v; break; }
}
}
void init(long long t, long long fa, long long rt) {
if (!up[t]) id[up[t] = t] = ++tot, ++cnt[t], len[t] = 1;
else ++cnt[up[t] = rt], len[t] = len[fa] + 1;
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
if (!up[e[i].v]) init(e[i].v, t, e[i].v);
else init(e[i].v, t, rt);
}
}
if (t == up[t]) tree[id[t]].init(cnt[t]);
}
void insert_line(edge e) {
if (up[e.u] == up[e.v] && len[e.u] < len[e.v]) {
}
}
long long query(long long u, long long k) {
long long ret = 0;
while (u != 1) {
ret ^= tree[id[up[u]]].sum(len[u] - 1);
u = up[u];
if (u != 1) {
if (dist[u] <= k) ret ^= dist[u];
u = father[u];
}
}
return ret;
}
int main()
{
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
nume = tot = 0, pnt = 1;
memset(h, 0, sizeof(h));
memset(up, 0, sizeof(up));
memset(down, 0, sizeof(down));
memset(cnt, 0, sizeof(cnt));
for (long long i = 1; i < n; ++i) {
r[i].nxt = 0;
scanf("%lld%lld%lld", &r[i].u, &r[i].v, &r[i].c);
}
sort(r + 1, r + n);
for (long long i = 1; i < n; ++i) add_edge(r[i].u, r[i].v, r[i].c);
dfs(1, 0, 0);
for (long long i = 1; i <= n; ++i) if (down[i]) up[down[i]] = i;
init(1, 0, 1);
scanf("%lld", &m);
for (long long i = 1; i <= m; ++i) {
a[i].id = i, a[i].ans = 0;
scanf("%lld%lld%lld", &a[i].u, &a[i].v, &a[i].k);
}
sort(a + 1, a + m + 1);
for (long long i = 1; i <= m; ++i) {
while (pnt <= nume && e[pnt].c <= a[i].k) insert_line(e[pnt++]);
a[i].ans = query(a[i].u, a[i].k) ^ query(a[i].v, a[i].k);
}
sort(a + 1, a + m + 1, cmp);
for (long long i = 1; i <= m; ++i) printf("%lld\n", a[i].ans);
}
return 0;
}


## 代码2

#include <cstdio>
#include <cstring>
using namespace std;
struct node_type {
long long val, child[2];
} node[4000001];
struct edge {
long long v, c, nxt;
} e[200001];
long long T, n, m, tot, nume, h[100001], root[100001];
void add_edge(long long u, long long v, long long c) {
e[++nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].c = c, e[nume].nxt = h[v], h[v] = nume;
}
long long insert_node(long long root, long long val, long long depth) {
if (depth < 0) {
node[++tot].val = node[root].val ^ val, node[tot].child[0] = node[tot].child[1] = 0;
}
long long t = (val >> depth) & 1;
long long ch = insert_node(node[root].child[t], val, depth - 1);
node[++tot].child[t] = ch, node[tot].child[!t] = node[root].child[!t];
node[tot].val = node[node[tot].child[t]].val ^ node[node[tot].child[!t]].val;
}
void dfs(long long t, long long fa) {
for (int i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
root[e[i].v] = insert_node(root[t], e[i].c, 30);
dfs(e[i].v, t);
}
}
}
long long get_dist(long long root, long long k, long long depth) {
if (depth < 0) return node[root].val;
long long t = (k >> depth) & 1;
if (t) return node[node[root].child[0]].val ^ get_dist(node[root].child[1], k, depth - 1);
else return get_dist(node[root].child[0], k, depth - 1);
}
int main()
{
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
nume = tot = 0;
memset(h, 0, sizeof(h));
for (int i = 1; i < n; ++i) {
long long u, v, c;
scanf("%lld%lld%lld", &u, &v, &c);