## 题目描述

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.
Your task is to write a program for this computer, which

• 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
bit_add(q[i].i, mp[a[q[i].i]], -1),
bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1);
}
}
return 0;
}


## 题目描述

I won’t feel lonely, nor will I be sorrowful… not before everything is buried.
A string of $n$ beads is left as the message of leaving. The beads are numbered from $1$ to $n$ from left to right, each having a shape numbered by integers between $1$ and $n$ inclusive. Some beads may have the same shapes.
The memory of a shape $x$ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $x$ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.
From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

## 代码

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

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

struct IOManager {
template <typename T>
inline bool read(T &x) {
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);
}
inline bool read(char &c) {
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
inline int read(char s[]) {
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 operator > (T &x) {
read(x); return *this;
}
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 operator < (T x) {
write(x); return *this;
}
} io;

struct BinaryIndexedTree {
private:
static const int N = 200000;
int n, a[N];

public:
void init(int t) {
n = t, memset(a, 0, sizeof a);
}
void add(int p, int v) {
for (; p <= n; p += p & -p) a[p] += v;
}
int get(int p) {
int ret = 0;
for (; p; p -= p & -p) ret += a[p];
return ret;
}
};

struct Set {
private:
static const int N = 200000;
int a[N];
set <int> s[N];
set <int> :: iterator it;

public:
void modify(int p, int v) {
if (a[p]) s[a[p]].erase(p);
a[p] = v;
s[a[p]].insert(p);
}
int prev(int p) {
it = s[a[p]].find(p);
return it == s[a[p]].begin() ? *it : *(-- it);
}
int next(int p) {
it = ++ s[a[p]].find(p);
return it == s[a[p]].end() ? *(-- it) : *it;
}
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
static const int N = 200000;
int n, m, numq, top, pos[N], pre[N], ans[N];
BinaryIndexedTree tree;
Set s;
struct Query {
int type, x, y, w, id;
bool operator < (const Query &q) const {
return x == q.x ? type < q.type : x < q.x;
}
} q[N << 2], tmp[N << 2];
void add_query(int type, int x, int y, int w, int id) {
q[++ numq] = (Query) { type, x, y, w, id };
}
void input() {
io > n > m;
for (int i = 2; i <= n + 1; ++ i) {
int t; io > t, s.modify(i, t);
int prev = s.prev(i);
add_query(MODIFY, prev, i, i - prev, 0);
}
for (int i = 1; i <= m; ++ i) {
int o; io > o;
if (o == 1) {
int p, x; io > p > x; ++ p;
int prev = s.prev(p), next = s.next(p);
if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
if (next > p) add_query(MODIFY, p, next, p - next, 0);
if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
s.modify(p, x);
prev = s.prev(p), next = s.next(p);
if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
if (next > p) add_query(MODIFY, p, next, next - p, 0);
} else {
int l, r; io > l > r, ++ l, ++ r, ++ top;
add_query(QUERY, r, r, 1, top);
add_query(QUERY, r, l - 1, -1, top);
add_query(QUERY, l - 1, r, -1, top);
add_query(QUERY, l - 1, l - 1, 1, top);
}
}
}
void process(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
process(l, mid), process(mid + 1, r);
int s = l, t = mid + 1, pnt = l;
while (s <= mid && t <= r) {
if (q[s] < q[t]) {
if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
tmp[pnt ++] = q[s ++];
} else {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
}
while (t <= r) {
if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
tmp[pnt ++] = q[t ++];
}
for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
while (s <= mid) tmp[pnt ++] = q[s ++];
for (int i = l; i <= r; ++ i) q[i] = tmp[i];
}

public:
void solve() {
input(), tree.init(n + 1), process(1, numq);
for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
}
} solver;

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


## 题目描述

Sereja has a sequence that consists of $n$ positive integers, $a_1, a_2, \ldots, a_n$.
First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence $a$. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.
A sequence of positive integers $x=x_1, x_2, \ldots, x_r$ doesn’t exceed a sequence of positive integers $y=y_1, y_2, \ldots, y_r$, if the following inequation holds: $x_1 \le y_1, x_2 \le y_2, \ldots, x_r \le y_r$.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $1000000007$ ($10^9+7$).

## 算法分析

$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$

## 代码

<?php
const MAX_NUM = 1000000;
const MOD = 1000000007;

$tree = array(); for ($i = 0; $i <= MAX_NUM; ++$i) array_push($tree, 0); function add($pos, $val) { global$tree;
for (; $pos <= MAX_NUM;$pos += $pos & -$pos) {
$tree[$pos] += $val;$tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD; } } function get($pos) {
global $tree;$ret = 0;
for (; $pos;$pos -= $pos & -$pos) {
$ret +=$tree[$pos];$ret -= (int) ($ret / MOD) * MOD; } return$ret;
}

$n = fgets(STDIN);$a = explode(' ', trim(fgets(STDIN)));
for ($i = 0;$i < $n; ++$i) {
$sum = get($a[$i]); add($a[$i],$sum * $a[$i] + $a[$i] - $sum + get($a[$i] - 1)); }$ans = get(MAX_NUM);
$ans -= (int) ($ans / MOD) * MOD;

## 代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct edge {
int v, nxt;
} e[200001];
struct binary_indexed_tree {
int n;
vector<int> a;
void init(int size) { n = size + 10, a.clear(), a.resize(n); }
void add(int p, int t) {
if (p) for (int i = p; i < n; i += i & -i) a[i] += t;
}
int sum(int p) {
if (p <= 0) return 0;
int ret = 0;
for (int i = min(p, n - 1); i; i -= i & -i) ret += a[i];
return ret;
}
} tree[200001];
int n, q, nume, tot, top, root, h[100001], w[100001];
int size[100001], f[100001], up[100001], id[100001][2];
bool vis[100001];
vector<int> dist[100001];
void add_edge(int u, int v) {
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
size[t] = 1, f[t] = 0;
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v] && e[i].v != fa) {
get_root(e[i].v, t);
size[t] += size[e[i].v], f[t] = max(f[t], size[e[i].v]);
}
}
f[t] = max(f[t], tot - size[t]);
if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int depth, int flag) {
if (flag) dist[t].push_back(depth);
else {
tree[id[root][0]].add(depth, w[t]);
if (dist[t].size() > 1) tree[id[root][1]].add(dist[t][dist[t].size() - 2], w[t]);
}
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v] && e[i].v != fa) get_dist(e[i].v, t, depth + 1, flag);
}
}
void solve(int t) {
vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v]) get_dist(e[i].v, t, 1, 0);
for (int i = h[t]; i; i = e[i].nxt) {
if (!vis[e[i].v]) {
root = 0, tot = size[e[i].v], get_root(e[i].v, t), up[root] = t;
tree[id[root][0] = ++top].init(size[e[i].v]);
tree[id[root][1] = ++top].init(size[e[i].v]);
tree[id[root][1]].add(dist[root][dist[root].size() - 1], w[root]);
get_dist(root, 0, 0, 1);
solve(root);
}
}
}
void modify(int t, int d) {
int p = t, top = dist[t].size() - 1;
while (p) {
if (top >= 0) tree[id[p][0]].add(dist[t][top], d);
if (top > 0) tree[id[p][1]].add(dist[t][top - 1], d);
p = up[p], --top;
}
}
int ask(int t, int d) {
int p = t, ret = 0, top = dist[t].size() - 1;
while (p) {
int len;
if (top >= 0) len = d - dist[t][top];
if (top >= 0 && len >= 0) ret += tree[id[p][0]].sum(len) + w[p];
if (top > 0) len = d - dist[t][top - 1];
if (top > 0 && len >= 0 && up[p]) ret -= tree[id[p][1]].sum(len);
p = up[p], --top;
}
return ret;
}
int main()
{
while (scanf("%d%d", &n, &q) != EOF) {
nume = top = 0;
memset(up, 0, sizeof(up));
memset(h, 0, sizeof(h));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i) {
scanf("%d", &w[i]);
dist[i].clear();
}
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d%d", &u, &v), add_edge(u, v);
}
root = 0, tot = f[0] = n, get_root(1, 0);
tree[id[root][0] = ++top].init(size[1]);
tree[id[root][1] = ++top].init(size[1]);
get_dist(root, 0, 0, 1);
solve(root);
while (q--) {
char oper = ' ';
while (oper != '!' && oper != '?') scanf("%c", &oper);
int v, d;
scanf("%d%d", &v, &d);
if (oper == '!') modify(v, d - w[v]), w[v] = d;
else printf("%d\n", ask(v, d));
}
}
return 0;
}