Mex
题目大意：给出一个序列\(a\)，定义\(f(l,r)\)为集合{\(a_l, a_{l+1}, …, a_r\)}的sg值，求\(\sum_i \sum_{j(i\leq j)} f(i,j)\)的值。
问题的关键（突破口）：假设对于一个固定的\(p\)，我们求出了对于所有\(j\)的\(f(p,j)\)，现在考虑\(p\)增加一，思考对于所有\(j\)的\(f(p+1,j)\)的值与\(f(p,j)\)有什么变化。
兔子与寿司
据说这题是原创题？以至于我找不到提交的地方。
这题很容易想到枚举第一只兔子的吃的最大的美味值x，然后显然把a小于等于x的篮子分给第一只兔子，现在考虑剩下的篮子。
我们可以用线段树维护，线段树的下标y是篮子的b值，存的值表示第二只兔子吃的最大美味小于等于y时，后面两只兔子最大的美味值的和最小是多少。
modseq
这题当时我记得旁边的人都刷刷地秒了，我这个逗比不会做。。。。
其实这个关系到鸽巢原理，当序列的长度大于\(p\)时，显然答案就是0嘛！我记得我以前看过！
忍不住贴个代码（事实上并没有多大意义）。
#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = (int) 2e5 + 3;
int n;
int a[MAXN];
struct s_node {
long long sum;
int mini, maxi;
int mark;
};
s_node t[1 << 19];
void update(int idx) {
int idxl = idx << 1;
int idxr = idxl | 1;
t[idx].sum = t[idxl].sum + t[idxr].sum;
t[idx].mini = min(t[idxl].mini, t[idxr].mini);
t[idx].maxi = max(t[idxl].maxi, t[idxr].maxi);
}
void build(int idx, int L, int R, int sg[]) {
t[idx].mark = -1;
if (L == R) {
t[idx].mini = t[idx].maxi = sg[L];
t[idx].sum = sg[L];
return;
}
int M = (L + R) >> 1;
build(idx << 1, L, M, sg);
build(idx << 1 | 1, M + 1, R, sg);
update(idx);
}
int posi[MAXN];
void analyse() {
static int next[MAXN];
fill(next, next + 1 + n, -1);
for (int i = n - 1; i >= 0; i--) {
if (next[a[i]] == -1) posi[i] = -1;
else posi[i] = next[a[i]];
next[a[i]] = i;
}
static int sg[MAXN], cnt[MAXN];
fill(cnt, cnt + n + 1, 0);
int num = 0;
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
while (cnt[num]) num++;
sg[i] = num;
}
build(1, 0, n - 1, sg);
}
void setLazy(int idx, int L, int R, int x) {
t[idx].mini = t[idx].maxi = x;
t[idx].sum = (long long) x * (R - L + 1);
t[idx].mark = x;
}
void modify(int idx, int L, int R, int l, int r, int x) {
if (t[idx].maxi <= x) return;
if (t[idx].mini >= x && l <= L && r >= R) {
setLazy(idx, L, R, x);
return;
}
int M = (L + R) >> 1;
if (-1 != t[idx].mark) {
setLazy(idx << 1, L, M, t[idx].mark);
setLazy(idx << 1 | 1, M + 1, R, t[idx].mark);
t[idx].mark = -1;
}
if (l <= M) modify(idx << 1, L, M, l, r, x);
if (r > M) modify(idx << 1 | 1, M + 1, R, l, r, x);
update(idx);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
while (scanf("%d", &n) == 1) {
if (n == 0) break;
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
a[i] = min(a[i], n);
}
analyse();
long long ans = t[1].sum;
for (int i = 0; i + 1 < n; i++) {
int p = a[i];
modify(1, 0, n - 1, i, i, 0);
if (posi[i] == -1) {
modify(1, 0, n - 1, i + 1, n - 1, p);
}
else {
if (i + 1 <= posi[i] - 1)
modify(1, 0, n - 1, i + 1, posi[i] - 1, p);
}
ans += t[1].sum;
}
cout << ans << endl;
}
return 0;
}
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = (int) 1e5 + 3;
struct s_blanket {
int a, b, c;
};
int n;
s_blanket x[MAXN];
int idx_value[MAXN];
bool cmp(const s_blanket &p, const s_blanket &q) {
return p.a < q.a;
}
struct s_node {
int maxi, lazy;
int value;
};
s_node t[1 << 18];
void setLazy(int idx, int v, int L) {
t[idx].maxi = v;
t[idx].lazy = v;
t[idx].value = v + idx_value[L];
}
void build(int idx, int L, int R) {
if (L == R) {
t[idx].value = idx_value[L];
return;
}
int M = (L + R) >> 1;
build(idx << 1, L, M);
build(idx << 1 | 1, M + 1, R);
t[idx].value = min(
t[idx << 1].value,
t[idx << 1 | 1].value);
}
void dfs(int idx, int L, int R, int y, int v, bool ok) {
if (L > y) return;
if (t[idx].maxi >= v) return;
if (L == R) {
if (v > t[idx].maxi) {
t[idx].maxi = v;
t[idx].value = idx_value[L] + v;
}
return;
}
int M = (L + R) >> 1;
int idxl = idx << 1;
int idxr = idxl | 1;
if (t[idx].lazy) {
setLazy(idxl, t[idx].lazy, L);
setLazy(idxr, t[idx].lazy, M + 1);
t[idx].lazy = 0;
}
if (ok && R <= y) {
setLazy(idx, v, L);
return;
}
if (ok) {
dfs(idxl, L, M, y, v, ok);
dfs(idxr, M + 1, R, y, v, ok);
}
else {
if (t[idxl].maxi < v) {
dfs(idxl, L, M, y, v, false);
dfs(idxr, M + 1, R, y, v, true);
}
else {
dfs(idxr, M + 1, R, y, v, false);
}
}
t[idx].maxi = min(t[idxl].maxi, t[idxr].maxi);
t[idx].value = min(t[idxl].value, t[idxr].value);
}
void insert(s_blanket item) {
int posi = lower_bound(idx_value, idx_value + n, item.b) - idx_value;
dfs(1, 0, n - 1, posi - 1, item.c, false);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 0; i <= n; i++) {
if (i < n)
scanf("%d%d%d", &x[i].a, &x[i].b, &x[i].c);
idx_value[i] = x[i].b;
}
n++;
sort(idx_value, idx_value + n);
sort(x, x + n, cmp);
int ans = 0x3f3f3f3f;
build(1, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
ans = min(ans, x[i].a + t[1].value);
insert(x[i]);
}
printf("%d\n", ans);
return 0;
}
#include <cstdio>
int main() {
int n, m;
static int a[100001];
while (scanf("%d%d", &n, &m) == 2) {
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 0; i < m; i++) {
int l, r, p;
scanf("%d%d%d", &l, &r, &p);
if (r - l + 1 > p) {
printf("0\n");
continue;
}
int ans = 0x3f3f3f3f;
for (int x = l; x <= r; x++) {
int sum = 0;
for (int y = x; y <= r; y++) {
sum = (sum + a[y]) % p;
if (sum < ans) ans = sum;
}
}
printf("%d\n", ans);
}
}
return 0;
}