## 题目描述

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


## 题目描述

Arpa has found a list containing $n$ numbers. He calls a list bad if and only if it is not empty and gcd of numbers in the list is $1$.
Arpa can perform two types of operations:

• Choose a number and delete it with cost $x$.
• Choose a number and increase it by $1$ with cost $y$.

Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.
Help Arpa to find the minimum possible cost to make the list good.

## 代码

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

using namespace std;

void minify(long long &a, long long b) { b < a && (a = b); }

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 operator > (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 operator < (T x) {
write(x); return *this;
}
} io;

struct Solver {
private:
static const int N = 1000000;
static const int M = 1000000;
int n, x, y, a[N + 1], cnt[N + 1 << 1];
long long sum[N + 1 << 1];
int top, prime[N];
bool vis[N + 1 << 1];
void input() {
io > n > x > y;
for (int i = 1; i <= n; ++ i) io > a[i], ++ cnt[a[i]], sum[a[i]] += a[i];
}
void init() {
for (int i = 1; i <= M << 1; ++ i) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
for (int i = 2; i <= M; ++ i) {
if (! vis[i]) prime[++ top] = i;
for (int j = 1; j <= top && i * prime[j] <= M; ++ j) {
vis[i * prime[j]] = true;
if (! (i % prime[j])) break;
}
}
}
void process() {
int p = x / y;
long long ans = 1000000000000000000ll;;
for (int i = 1; i <= top; ++ i) {
long long tmp = 0;
int delta = prime[i] - p - 1;
for (int j = 0; j <= N; j += prime[i]) {
if (delta < 0) {
tmp += (((long long) cnt[j + prime[i]] - cnt[j]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j])) * y;
} else {
tmp += ((long long) cnt[j + delta] - cnt[j]) * x + (((long long) cnt[j + prime[i]] - cnt[j + delta]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j + delta])) * y;
}
}
minify(ans, tmp);
}
io < ans < '\n';
}

public:
void solve() {
input(), init(), process();
}
} solver;

int main() {
solver.solve();
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;
}


## 题目描述

Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score $a$ and Lexa starts with score $b$. In a single turn, both Memory and Lexa get some integer in the range $[-k, k]$ (i.e. one integer among $-k, -k+1, -k+2, …, -2, -1, 0, 1, 2, …, k-1, k$) and add them to their current scores. The game has exactly $t$ turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.
Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are $(2k+1)^{2t}$ games in total. Since the answer can be very large, you should print it modulo $10^9+7$. Please solve this problem for Memory.

## 算法分析

$$f_{i, j} = \sum_{|j-l| \le 2k} (2k+1-|j-l|)f_{i-1, l}$$
$j$的范围是$[-200000, 200000]$，暴力求$f_{i, j}$会超时。

## 代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long a, b, k, t, p, now, ans, f[2][500002], sign[2][500002];
int main()
{
cin >> a >> b >> k >> t;
sign[0][a - b + 250000] = 1;
sign[0][a - b + 250001] = -2;
sign[0][a - b + 250002] = 1;
for (int i = 0; i <= t; ++i, now ^= 1) {
p = f[now][0] = 0;
for (int j = 0; j < 500002; ++j) {
p += sign[now][j];
f[now][j] = p;
if (j) f[now][j] += f[now][j - 1];
f[now][j] %= MOD;
if (f[now][j] < 0) f[now][j] += MOD;
if (f[now][j]) {
sign[now ^ 1][j - (k << 1)] += f[now][j];
sign[now ^ 1][j + 1] -= f[now][j] << 1;
sign[now ^ 1][j + (k + 1 << 1)] += f[now][j];
}
sign[now][j] = f[now ^ 1][j] = 0;
}
}
for (int i = 250001; i < 500001; ++i) {
ans += f[now ^ 1][i];
}
cout << ans % MOD << endl;
return 0;
}