## 题目描述

Vasya has a set of $4n$ strings of equal length, consisting of lowercase English letters “a”, “b”, “c”, “d” and “e”. Moreover, the set is split into $n$ groups of $4$ equal strings each. Vasya also has one special string $a$ of the same length, consisting of letters “a” only.
Vasya wants to obtain from string $a$ some fixed string $b$, in order to do this, he can use the strings from his set in any order. When he uses some string $x$, each of the letters in string $a$ replaces with the next letter in alphabet as many times as the alphabet position, counting from zero, of the corresponding letter in string $x$. Within this process the next letter in alphabet after “e” is “a”.
For example, if some letter in $a$ equals “b”, and the letter on the same position in $x$ equals “c”, then the letter in $a$ becomes equal “d”, because “c” is the second alphabet letter, counting from zero. If some letter in $a$ equals “e”, and on the same position in $x$ is “d”, then the letter in $a$ becomes “c”. For example, if the string $a$ equals “abcde”, and string $x$ equals “baddc”, then $a$ becomes “bbabb”.
A used string disappears, but Vasya can use equal strings several times.
Vasya wants to know for $q$ given strings $b$, how many ways there are to obtain from the string $a$ string $b$ using the given set of $4n$ strings? Two ways are different if the number of strings used from some group of $4$ strings is different. Help Vasya compute the answers for these questions modulo $10^9+7$.

## 代码

#include <iostream>
#include <cstring>
using namespace std;
const long long mod = 1000000007ll;
long long n, m, q, a[501][501], b[501][501], r[501], p[501], t, ans = 1;
bool vis[501];
string s;
void gauss() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j])
if (!vis[j]) {
vis[j] = true, ++t;
for (int k = 1; k <= m; ++k) b[j][k] = a[i][k];
break;
} else {
int t = 0;
while (a[i][j]) (a[i][j] += b[j][j]) %= 5, ++t;
for (int k = 1; k <= m; ++k)
if (j != k) (a[i][k] += b[j][k] * t) %= 5;
}
}
int main()
{
cin >> n >> m, ans = 1;
for (int i = 1; i <= n; ++i) {
cin >> s;
for (int j = 1; j <= m; ++j) a[i][j] = s[j - 1] - 'a';
}
cin >> q, gauss();
for (int i = t; i < n; ++i) (ans *= 5) %= mod;
while (q--) {
cin >> s, memset(p, 0, sizeof p);
for (int i = 1; i <= m; ++i) r[i] = s[i - 1] - 'a';
bool flag = false;
for (int i = 1; i <= m; ++i) {
if (p[i] != r[i]) {
if (!b[i][i]) { flag = true; break; }
int t = 0;
while (p[i] != r[i]) (p[i] += b[i][i]) %= 5, ++t;
for (int j = 1; j <= m; ++j)
if (i != j) (p[j] += b[i][j] * t) %= 5;
}
}
if (flag) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}

## 题目描述

$n$ people are standing on a coordinate axis in points with positive integer coordinates strictly less than $10^6$. For each person we know in which direction (left or right) he is facing, and his maximum speed.
You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed $s$: one to the right, and one to the left. Of course, the speed $s$ is strictly greater than people’s maximum speed.
The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.
You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point $0$, and there is a person that has run through point $10^6$, is as small as possible. In other words, find the minimum time moment $t$ such that there is a point you can place the bomb to so that at time moment $t$ some person has run through $0$, and some person has run through point $10^6$.

## 代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps = 1e-10;
long long n, s;
long long x[100001], v[100001], t[100001];
double l, r;
bool check(double p) {
bool flag1 = false, flag2 = false;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] <= p) flag1 = true;
else if (t[i] == 2 && (1e6 - x[i]) / v[i] <= p) flag2 = true;
if (flag1 && flag2) return true;
if (flag1) {
for (int i = 1; i <= n; ++i)
if (t[i] == 2 && (1e6 - x[i]) / (s + v[i]) <= p) return true;
return false;
}
if (flag2) {
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / (s + v[i]) <= p) return true;
return false;
}
long long before = 0, after = 1e6;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p) after = min(after, x[i]);
else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p) before = max(before, x[i]);
if (before < after) return false;
long long ma = -1e18, mi = 1e18;
for (int i = 1; i <= n; ++i)
if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p)
ma = max(ma, (long long) floor((x[i] * v[i] + p * (s + v[i]) * (s - v[i])) / s));
else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p)
mi = min(mi, (long long) ceil((1e6 * (s - v[i]) + x[i] * v[i] - p * (s + v[i]) * (s - v[i])) / s));
return mi <= ma;
}
int main()
{
cin >> n >> s;
for (int i = 1; i <= n; ++i)
cin >> x[i] >> v[i] >> t[i];
l = 0, r = 1e6;
while (r - l > eps) {
double mid = (l + r) / 2;
if (!check(mid)) l = mid; else r = mid;
}
cout << setprecision(10) << fixed << l << endl;
return 0;
}

## 题目描述

In the Isle of Guernsey there are $n$ different types of coins. For each $i \; (1 \le i \le n)$, coin of type $i$ is worth $a_i$ cents. It is possible that $a_i=a_j$ for some $i$ and $j \; (i \neq j)$.
Bessie has some set of these coins totaling $t$ cents. She tells Jessie $q$ pairs of integers. For each $i \; (1 \le i \le q)$, the pair $b_i, c_i$ tells Jessie that Bessie has a strictly greater number of coins of type $b_i$ than coins of type $c_i$. It is known that all $b_i$ are distinct and all $c_i$ are distinct.
Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some $i \; (1 \le i \le n)$, such that the number of coins Bessie has of type $i$ is different in the two combinations. Since the answer can be very large, output it modulo $1000000007$ ($10^9+7$).
If there are no possible combinations of coins totaling $t$ cents that satisfy Bessie’s conditions, output $0$.

## 代码

#include <iostream>
using namespace std;
const long long mod = 1000000007ll;
long long n, q, t, ma, a[301], to[301], f[100001];
bool m[301], in[301], vis[301];
void dfs(long long u, long long d, long long s) {
ma = d, vis[u] = true;
if (to[u]) dfs(to[u], d + 1, s + a[u]);
t -= (ma - d) * a[u], a[u] += s;
}
int main()
{
cin >> n >> q >> t, f[0] = 1;
for (int i = 1; i <= n; cin >> a[i], ++i);
for (int i = 1; i <= q; ++i) {
long long b, c; cin >> b >> c;
m[b] = m[c] = true, in[c] = true, to[b] = c;
}
for (int i = 1; i <= n; ++i)
if (m[i] && !in[i]) ma = 0, dfs(i, 0, 0);
if (t < 0) { cout << 0 << endl; return 0; }
for (int i = 1; i <= n; ++i)
if (m[i] && !vis[i]) { cout << 0 << endl; return 0; }
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= t - a[i]; ++j)
(f[j + a[i]] += f[j]) %= mod;
cout << f[t] << endl;
return 0;
}

## 题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

## 题意概述

while (!(x <= 0 || x > n)) {
y += a[x], x += a[x];
if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}

## 代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
if (ans[t][m]) return ans[t][m];
if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
long long ret = dfs(to[t][m], !m);
if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
return ans[t][m];
}
int main()
{
cin >> n, vis[1][1] = true;
for (int i = 2; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
for (int i = 1; i < n; ++i)
if (ans[i + 1][0] == -1) cout << -1 << endl;
else cout << i + ans[i + 1][0] << endl;
return 0;
}

## 题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

## 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
long long u, v, c, id; bool mst;
bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) {
depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
}
}
long long get_max(long long u, long long v) {
long long ret = 0;
if (depth[u] < depth[v]) u ^= v ^= u ^= v;
for (int i = 19; i >= 0; --i)
if (depth[u] - depth[v] >= (1 << i))
ret = max(ret, ma[u][i]), u = up[u][i];
if (u == v) return ret;
for (int i = 19; i >= 0; --i)
if (up[u][i] != up[v][i])
ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
if (depth[u] < depth[v]) u ^= v ^= u ^= v;
long long p = u, q = v;
for (int i = 19; i >= 0; --i)
if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
if (p != q) {
for (int i = 19; i >= 0; --i)
if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
p = up[p][0];
}
u = get_fa(u), v = get_fa(v);
while (depth[u] > depth[p])
ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
while (depth[v] > depth[p])
ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
cin >> n >> m, memset(ans, -1, sizeof ans);
if (n == m + 1) {
for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
}
for (int i = 1; i <= n; fa[i] = i, ++i);
for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
sort(l + 1, l + m + 1);
for (int i = 1; i <= m; ++i) {
long long u = get_fa(l[i].u), v = get_fa(l[i].v);
if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
}
depth[1] = 1, dfs(1, 0);
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= n; ++j) {
up[j][i] = up[up[j][i - 1]][i - 1];
ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
}
for (int i = 1; i <= n; fa[i] = i, ++i);
for (int i = 1; i <= m; ++i)
if (!l[i].mst) {
ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
update(l[i].u, l[i].v, l[i].c);
}
for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
cout << endl;
return 0;
}

## 题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

## 代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
if (!node[t].child[0]) {
node[t].min = node[t].max = node[t].val; return;
}
dfs(node[t].child[0]), dfs(node[t].child[1]);
node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
if (!node[t].child[0]) {
id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
}
cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
long long a; scanf("%lld%lld", &a, &node[i].val);
if (a == -1) root = i;
else if (!node[a].child[0]) node[a].child[0] = i;
else {
node[a].child[1] = i;
if (node[node[a].child[0]].val > node[node[a].child[1]].val)
node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
}
}
dfs(root), find(root), scanf("%lld", &k);
for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
while (k--) {
long long a, l = 0, r = top; scanf("%lld", &a);
while (l + 1 < r) {
long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
}
printf("%.10lf\n", ans[l]);
}
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;
}

## 题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

## 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
long long u, v, w;
bool operator < (const line &a) const {
return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
}
} l[200001];
void add_edge(long long u, long long v, long long w) {
e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
queue<long long> que;
while (!que.empty()) que.pop();
for (int i = 1; i <= n; ++i)
if (!d[i]) in[i] = true, que.push(i);
while (!que.empty()) {
int u = que.front(); in[u] = false, que.pop();
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
}
}
}
long long get_fa(long long t) {
return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
}
memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
for (int i = 1; i <= k; ++i) {
cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
}
ans = mi, memset(d, 0x1f, sizeof d);
for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
for (int i = 1; i <= n; ++i)
for (int j = h[i]; j; j = e[j].nxt)
l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
sort(l + 1, l + tot + 1);
for (int i = 1; i <= tot; ++i) {
long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
}
cout << ans << 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;
}

## 题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

• Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
• Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

## 代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
cin >> n >> m >> k >> p;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cin >> a[i][j];
for (int i = 1; i <= n; ++i) {
long long s = 0;
for (int j = 1; j <= m; ++j) s += a[i][j];
r.push(s);
}
for (int j = 1; j <= m; ++j) {
long long s = 0;
for (int i = 1; i <= n; ++i) s += a[i][j];
c.push(s);
}
for (int i = 1; i <= k; ++i) {
long long u = r.top(); r.pop();
rr[i] = rr[i - 1] + u;
r.push(u - p * m);
u = c.top(); c.pop();
cc[i] = cc[i - 1] + u;
c.push(u - p * n);
}
for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
cout << ans << endl;
return 0;
}