## 代码

/*
* Try to have as good a life as you can under the circumstances.
*/

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

static int const N = 100005;
static int const NM = 5000000;
int rt[N], top, buf[NM];
struct Interval {
int l, r, ord;
bool operator<(Interval const &a) const { return l < a.l; }
};
std::set<Interval> st;
struct SegmentTree {
int ch[2], val, sum;
} nd[NM];

void update(int rt) {
nd[rt].sum = nd[nd[rt].ch[0]].sum + nd[rt].val + nd[nd[rt].ch[1]].sum;
}

void insert(int &rt, int nl, int nr, int p) {
if (!rt)
nd[rt = buf[--top]] = nd[0];
if (nl == nr) {
nd[rt].val = nd[rt].sum = 1;
return;
}
int mid = nl + nr >> 1;
if (p <= mid)
insert(nd[rt].ch[0], nl, mid, p);
else
insert(nd[rt].ch[1], mid + 1, nr, p);
update(rt);
}

void merge(int &p, int &q) {
if (!p || !q) {
p = p + q, q = 0;
return;
}
merge(nd[p].ch[0], nd[q].ch[0]), merge(nd[p].ch[1], nd[q].ch[1]);
buf[top++] = q, q = 0, update(p);
}

int split(int &rt, int k) {
if (!rt || nd[rt].sum == k)
return 0;
if (!k) {
int rec = rt;
return rt = 0, rec;
}
if (nd[nd[rt].ch[0]].sum >= k) {
int sp = buf[--top];
nd[sp].ch[0] = split(nd[rt].ch[0], k), nd[sp].ch[1] = nd[rt].ch[1],
nd[rt].ch[1] = 0;
return update(rt), update(sp), sp;
}
int sp = buf[--top];
nd[sp].ch[0] = 0,
nd[sp].ch[1] = split(nd[rt].ch[1], k - nd[nd[rt].ch[0]].sum);
return update(rt), update(sp), sp;
}

int query(int rt, int nl, int nr, int k) {
if (nl == nr)
return nl;
int mid = nl + nr >> 1;
if (nd[nd[rt].ch[0]].sum >= k)
return query(nd[rt].ch[0], nl, mid, k);
else
return query(nd[rt].ch[1], mid + 1, nr, k - nd[nd[rt].ch[0]].sum);
}

int main() {
for (int i = 1; i < NM; ++i)
buf[top++] = i;
int n, m, q;
scanf("%d%d", &n, &m);
for (int i = 1, t; i <= n; ++i)
scanf("%d", &t), insert(rt[i], 1, n, t), st.insert((Interval){i, i, 0});
for (; m--;) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
std::set<Interval>::iterator L = st.upper_bound((Interval){l}),
R = st.upper_bound((Interval){r});
Interval recl = *(--L), recr = *(--R);
if (L->l < l)
if (L->ord == 0)
rt[l] = split(rt[L->l], l - L->l);
else
rt[l] = split(rt[L->l], L->r - l + 1), std::swap(rt[l], rt[L->l]);
if (L != R) {
st.erase(L++);
for (; L != R; st.erase(L++))
merge(rt[l], rt[L->l]);
if (r < R->r)
if (R->ord == 0)
rt[r + 1] = split(rt[R->l], r - R->l + 1);
else
rt[r + 1] = split(rt[R->l], R->r - r), std::swap(rt[r + 1], rt[R->l]);
merge(rt[l], rt[R->l]);
} else if (r < R->r)
if (R->ord == 0)
rt[r + 1] = split(rt[l], r - l + 1);
else
rt[r + 1] = split(rt[l], R->r - r), std::swap(rt[r + 1], rt[l]);
st.erase(R), st.insert((Interval){l, r, op});
if (recl.l < l)
st.insert((Interval){recl.l, l - 1, recl.ord});
if (r < recr.r)
st.insert((Interval){r + 1, recr.r, recr.ord});
}
scanf("%d", &q);
for (std::set<Interval>::iterator it = st.begin(); it != st.end(); ++it)
if (q <= nd[rt[it->l]].sum) {
if (it->ord == 0)
printf("%d\n", query(rt[it->l], 1, n, q));
else
printf("%d\n", query(rt[it->l], 1, n, nd[rt[it->l]].sum - q + 1));
break;
} else
q -= nd[rt[it->l]].sum;
return 0;
}

## 题目描述

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;
}

## 题目描述

In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it’s the third largest element for a group of five). To increase the algorithm’s performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.
A sum of medians of a sorted $k$-element set $S={a_1, a_2, \ldots, a_k}$, where $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_k$, will be understood by as $\sum_{i \bmod 5=3} a_i$.
The $\bmod$ operator stands for taking the remainder, that is $x \bmod y$ stands for the remainder of dividing $x$ by $y$.
To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

## 代码1

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long n, x;
string o;
struct treap {
int tot, root;
struct node_type {
int child[2], rank;
long long val, size, mod[5];
} node[100001];
void update(int t) {
node[t].size = node[node[t].child[0]].size + node[node[t].child[1]].size + 1;
for (int i = 0; i < 5; ++i)
node[t].mod[i] = node[node[t].child[0]].mod[i] + node[node[t].child[1]].mod[(i + 99999 - node[node[t].child[0]].size) % 5];
node[t].mod[(node[node[t].child[0]].size + 1) % 5] += node[t].val;
}
void rotate(int &t, int dire) {
int p = node[t].child[!dire];
node[t].child[!dire] = node[p].child[dire], node[p].child[dire] = t;
update(t), update(p), t = p;
}
void insert(int &t, long long val) {
if (!t) {
t = ++tot, node[t].rank = ((rand() & ((1 << 16) - 1)) << 10) ^ rand(), node[t].val = node[t].mod[1] = val, node[t].size = 1;
return;
}
++node[t].size;
if (val < node[t].val) {
insert(node[t].child[0], val);
if (node[node[t].child[0]].rank > node[t].rank) rotate(t, 1);
} else {
insert(node[t].child[1], val);
if (node[node[t].child[1]].rank > node[t].rank) rotate(t, 0);
}
update(t);
}
void remove(int &t, long long val) {
if (!node[t].child[0] && !node[t].child[1]) { t = 0; return; }
if (val == node[t].val) {
if (node[node[t].child[0]].rank > node[node[t].child[1]].rank) rotate(t, 1);
else rotate(t, 0);
}
if (val < node[t].val) remove(node[t].child[0], val);
else remove(node[t].child[1], val);
update(t);
}
long long query() { return node[root].mod[3]; }
} tree;
int main()
{
srand(time(NULL));
cin >> n;
while (n--) {
cin >> o;
if (o[0] == 'a') { cin >> x; tree.insert(tree.root, x); }
else if (o[0] == 'd') { cin >> x; tree.remove(tree.root, x); }
else cout << tree.query() << endl;
}
return 0;
}

## 题目描述

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:
$$F_1=1, \; F_2=1, \; F_n=F_{n-1}+F_{n-2} \; (n \gt 2)$$
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of $n$ integers: $a_1, a_2, \ldots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

• Format of the query “1 $l$ $r$”. In reply to the query, you need to add $F_{i-l+1}$ to each element $a_i$, where $l \le i \le r$.
• Format of the query “2 $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^r a_i$ modulo $1000000009$ ($10^9+9$).

Help DZY reply to all the queries.

## 代码

#include <cstdio>
#include <iostream>
using namespace std;
const long long mod = 1000000009ll;
struct node_type {
long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
if (node[root].l == node[root].r) return; long long mid = node[root].l + node[root].r >> 1;
node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot, build_tree(tot);
node[++tot].l = mid + 1, node[tot].r = node[root].r, node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
if (node[root].l == node[root].r || node[root].val[0] == 0 && node[root].val[1] == 0) return;
if (node[node[root].child[0]].l == node[node[root].child[0]].r) node[node[root].child[0]].sum += node[root].val[0];
else {
(node[node[root].child[0]].val[0] += node[root].val[0]) %= mod, (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] * node[root].val[0] % mod;
node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] * node[root].val[1] % mod;
}
long long p = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] * node[root].val[1]) % mod;
long long q = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] * node[root].val[1]) % mod;
if (node[node[root].child[1]].l == node[node[root].child[1]].r) node[node[root].child[1]].sum += p;
else {
(node[node[root].child[1]].val[0] += p) %= mod, (node[node[root].child[1]].val[1] += q) %= mod;
node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p % mod;
node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q % mod;
}
node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
if (node[root].l == node[root].r) return;
node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
}
void insert_line(int root, int l, int r, int val) {
if (node[root].r < l || node[root].l > r) return;
if (node[root].l >= l && node[root].r <= r) {
if (node[root].l == node[root].r) node[root].sum += x[val][0] + x[val][1];
else {
(node[root].val[0] += x[val][0] + x[val][1]) %= mod;
(node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
node[root].sum += y[node[root].r - node[root].l + 1][0] * (x[val][0] + x[val][1]) % mod;
node[root].sum += y[node[root].r - node[root].l + 1][1] * (x[val + 1][0] + x[val + 1][1]) % mod;
}
return;
}
push_down(root);
insert_line(node[root].child[0], l, r, val);
insert_line(node[root].child[1], l, r, max(1ll, val + node[node[root].child[1]].l - max((long long) l, node[node[root].child[0]].l)));
push_up(root);
}
long long get_sum(int root, int l, int r) {
if (node[root].r < l || node[root].l > r) return 0;
if (node[root].l >= l && node[root].r <= r) return node[root].sum;
long long ret;
push_down(root);
ret = get_sum(node[root].child[0], l, r) + get_sum(node[root].child[1], l, r);
push_up(root);
return ret;
}
int main()
{
scanf("%lld%lld", &n, &m);
x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
for (int i = 3; i <= n; ++i) {
x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
}
node[1].l = 1, node[1].r = n, build_tree(1);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1];
while (m--) {
scanf("%lld%lld%lld", &o, &l, &r);
if (o == 1) insert_line(1, l, r, 1);
else printf("%lld\n", ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
}
return 0;
}

## 代码

#include <cstdio>
#include <iomanip>
#include <cstring>
using namespace std;
struct node_type {
int l, r, child[2];
} node[300001];
struct edge {
int v, c, nxt;
} e[600001];
int n, tot, nume, id, h[300001], que[600001], dfn[300001], low[300001];
int top, sta[300001], cnt, belong[300001], pnt[300001];
long double ans;
bool vis[300001];
void add_edge(int u, int v) {
if (u == v) return;
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(int root) {
int mid = node[root].l + node[root].r >> 1;
if (node[root].l == mid) {
} else {
node[++tot].l = node[root].l, node[tot].r = mid;
node[root].child[0] = tot, add_edge(root, tot), build_tree(tot);
}
if (mid + 1 == node[root].r) {
node[root].child[1] = mid + 1, add_edge(root, mid + 1);
} else {
node[++tot].l = mid + 1, node[tot].r = node[root].r;
node[root].child[1] = tot, add_edge(root, tot), build_tree(tot);
}
}
void insert_line(int root, int l, int r, int t) {
if (node[root].l == l && node[root].r == r) {
}
int mid = node[root].l + node[root].r >> 1;
if (r <= mid) insert_line(node[root].child[0], l, r, t);
else if (l > mid) insert_line(node[root].child[1], l, r, t);
else {
insert_line(node[root].child[0], l, mid, t);
insert_line(node[root].child[1], mid + 1, r, t);
}
}
void dfs(int t) {
dfn[t] = low[t] = ++id;
sta[++top] = t, vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt) {
if (!dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]);
else if (vis[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
}
if (dfn[t] == low[t]) {
int v; ++cnt;
do belong[v = sta[top--]] = cnt, vis[v] = false; while (v != t);
}
}
int bfs(int u) {
memset(vis, false, sizeof(vis));
int s = 0, t = 0, ret = 1;
vis[que[++t] = u] = true;
while (s < t) {
int v = que[++s];
for (int i = h[v]; i; i = e[i].nxt) {
if (!vis[e[i].v]) {
vis[que[++t] = e[i].v] = true;
if (e[i].v && e[i].v <= n) ++ret;
}
}
}
return ret;
}
int main()
{
scanf("%d", &n); tot = n + 1;
for (int i = 1; i <= n; ++i) node[i].l = node[i].r = i;
node[tot].l = 1, node[tot].r = n, build_tree(tot);
for (int i = 1; i <= n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
insert_line(n + 1, l, r, i);
}
for (int i = 1; i <= tot; ++i) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; ++i) {
if (!pnt[belong[i]]) pnt[belong[i]] = bfs(i);
ans += pnt[belong[i]];
}
printf("%.6llf\n", ans / n);
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;
}

## 题目描述

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.
There are n planets in their universe numbered from $1$ to $n$. Rick is in planet number $s$ (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.
By default he can not open any portal by this gun. There are $q$ plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.
Plans on the website have three types:

1. With a plan of this type you can open a portal from planet $v$ to planet $u$.
2. With a plan of this type you can open a portal from planet $v$ to any planet with index in range $[l, r]$.
3. With a plan of this type you can open a portal from any planet with index in range $[l, r]$ to planet $v$.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

## 代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct node_type {
long long l, r, child[2];
} node[2000001];
struct edge {
long long v, w, nxt;
} e[2000001];
long long n, q, s, dist[2000001], tot, nume, h[2000001];
bool in[2000001];
queue<long long> que;
void add_edge(long long u, long long v, long long w) {
if (u == v) return;
e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(long long root, int mode) {
long long mid = node[root].l + node[root].r >> 1;
if (node[root].l == mid) node[root].child[0] = node[root].l;
else {
node[++tot].l = node[root].l, node[tot].r = mid;
node[root].child[0] = tot, build_tree(tot, mode);
}
if (mid + 1 == node[root].r) node[root].child[1] = node[root].r;
else {
node[++tot].l = mid + 1, node[tot].r = node[root].r;
node[root].child[1] = tot, build_tree(tot, mode);
}
if (mode) {
} else {
}
}
void insert_line(long long root, long long l, long long r, long long v, long long w, int mode) {
if (l == node[root].l && r == node[root].r) {
return;
}
if (r < node[node[root].child[1]].l) insert_line(node[root].child[0], l, r, v, w, mode);
else if (l > node[node[root].child[0]].r) insert_line(node[root].child[1], l, r, v, w, mode);
else {
insert_line(node[root].child[0], l, node[node[root].child[0]].r, v, w, mode);
insert_line(node[root].child[1], node[node[root].child[1]].l, r, v, w, mode);
}
}
void spfa() {
memset(dist, 0x1f, sizeof(dist));
while (!que.empty()) que.pop();
que.push(s), in[s] = true, dist[s] = 0;
while (!que.empty()) {
long long t = que.front(); que.pop(); in[t] = false;
for (long long i = h[t]; i; i = e[i].nxt) {
if (dist[e[i].v] > dist[t] + e[i].w) {
dist[e[i].v] = dist[t] + e[i].w;
if (!in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
}
}
}
}
int main()
{
scanf("%lld%lld%lld", &n, &q, &s);
for (int i = 1; i <= n; ++i) {
node[i].l = node[i].r = i;
}
tot = n + 2;
node[n + 1].l = node[n + 2].l = 1;
node[n + 1].r = node[n + 2].r = n;
if (n > 1) build_tree(n + 1, 0), build_tree(n + 2, 1);
for (long long i = 1, t, v, u, l, r, w; i <= q; ++i) {
scanf("%lld", &t);
if (t == 1) {
scanf("%lld%lld%lld", &v, &u, &w);
} else {
scanf("%lld%lld%lld%lld", &v, &l, &r, &w);
insert_line(n + t - 1, l, r, v, w, t - 2);
}
}
spfa();
for (int i = 1; i <= n; ++i) {
if (dist[i] != dist[0]) printf("%lld ", dist[i]);
else printf("-1 ");
}
printf("\n");
return 0;
}

## 题目描述

Karen just got home from the supermarket, and is getting ready to go to sleep.
After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: strength, defense and speed. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is $p$, the maximum possible defense is $q$ and the maximum possible speed is $r$.
There are $n$ cards in her collection. The $i$-th card has a strength $a_i$, defense $b_i$ and speed $c_i$, respectively.
A card beats another card if at least two of its characteristics are strictly greater than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.

## 代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct card {
long long a, b, c;
} c[500002];
bool operator < (card a, card b) {
return a.a < b.a;
}
long long n, p, q, r, pnt = 1, ans, s[500002], t[500002];
struct segment_tree {
struct node_type {
long long l, r, val, max, sum, tag;
node_type *child[2];
} *root;
void build_tree(node_type *root) {
if (root->l == root->r) return;
long long mid = root->l + root->r >> 1;
node_type *p, *q;
p = new node_type;
p->l = root->l, p->r = mid, p->val = p->max = p->sum = p->tag = 0;
q = new node_type;
q->l = mid + 1, q->r = root->r, q->val = q->max = q->sum = q->tag = 0;
build_tree(p), build_tree(q);
root->child[0] = p, root->child[1] = q;
}
void push_up(node_type *root) {
if (root->l != root->r) {
root->sum = root->child[0]->sum + root->child[1]->sum;
root->max = max(root->child[0]->max, root->child[1]->max);
}
}
void push_down(node_type *root) {
if (root->tag && root->l != root->r) {
root->child[0]->tag = root->child[0]->max = root->child[1]->tag = root->child[1]->max = root->tag;
root->child[0]->sum = (root->child[1]->l - root->child[0]->l) * root->tag;
root->child[1]->sum = (root->child[1]->r - root->child[0]->r) * root->tag;
}
root->tag = 0;
}
void insert_line(node_type *root, long long l, long long r, long long t) {
if (l == root->l && r == root->r) {
root->tag = root->max = t;
root->sum = (r - l + 1) * t;
return;
}
push_down(root);
if (r < root->child[1]->l) insert_line(root->child[0], l, r, t);
else if (l > root->child[0]->r) insert_line(root->child[1], l, r, t);
else {
insert_line(root->child[0], l, root->child[0]->r, t);
insert_line(root->child[1], root->child[1]->l, r, t);
}
push_up(root);
}
long long get(node_type *root, long long t) {
if (root->l == root->r) return root->l;
push_down(root);
if (root->child[1]->max < t) return get(root->child[0], t);
else return get(root->child[1], t);
}
long long get_sum(node_type *root, int l, int r) {
if (l == root->l && r == root->r) return root->sum;
push_down(root);
if (r < root->child[1]->l) return get_sum(root->child[0], l, r);
else if (l > root->child[0]->r) return get_sum(root->child[1], l, r);
else return get_sum(root->child[0], l, root->child[0]->r) + get_sum(root->child[1], root->child[1]->l, r);
}
} tree;
int main()
{
scanf("%lld%lld%lld%lld", &n, &p, &q, &r);
tree.root = new segment_tree::node_type;
tree.root->l = 0, tree.root->r = q, tree.root->val = tree.root->max = tree.root->sum = tree.root->tag = 0;
tree.build_tree(tree.root);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", &c[i].a, &c[i].b, &c[i].c);
}
sort(c + 1, c + n + 1);
s[n] = c[n].b, t[n] = c[n].c;
for (int i = n - 1; i; --i) {
s[i] = max(s[i + 1], c[i].b);
t[i] = max(t[i + 1], c[i].c);
}
tree.insert_line(tree.root, 0, 0, q + 1);
long long tmp;
for (int i = 1, j = 1; i <= p; ++i) {
for (; j <= n && c[j].a < i; ++j) {
tmp = tree.get(tree.root, c[j].c);
if (tmp >= c[j].b) continue;
tree.insert_line(tree.root, tmp + 1, c[j].b, c[j].c);
}
tmp = max(s[j], tree.get(tree.root, t[j] + 1));
ans += (tmp - s[j]) * r + (q - tmp) * (r - t[j]);
if (tmp > s[j]) ans -= tree.get_sum(tree.root, s[j] + 1, tmp);
}
printf("%lld\n", ans);
return 0;
}