[CF 1000F]One Occurrence
好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io。然后因为我回学校了所以接下来很长时间可能会继续用这个博客？
我谔谔，还是说这题……
对于询问\([l, r]\)，考虑所有数在其中第一次出现的位置，如果说这个数在整个区间里只出现了一次，那么这个数下一次出现的位置一定大于\(r\)。
因此我们用扫描线搞一下就好啦……
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
if(L == R) {
maxv[o] = std::make_pair(-1, -1);
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
void modify(int o, int L, int R, const int &p, const pii &v) {
if(L == R) {
maxv[o] = v;
} else {
int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o);
}
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
if(ql <= L && R <= qr) {
return maxv[o];
} else {
int M = (L + R) / 2;
pii ret = std::make_pair(-100, -100);
if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
return ret;
}
}
int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
int n; scanf("%d", &n);
std::fill(rec, rec + maxn, n + 1);
for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
for(int i = n; i >= 1; i --) {
next[i] = rec[A[i]];
rec[A[i]] = i;
}
int q; scanf("%d", &q);
for(int i = 1; i <= q; i ++) {
int l, r; scanf("%d%d", &l, &r);
que[l].push_back({r, i});
}
build_tree(1, 1, n);
for(int i = 1; i <= 500000; i ++) {
if(rec[i] <= n) {
modify(1, 1, n, rec[i], {next[rec[i]], i});
}
}
for(int i = 1; i <= n; i ++) {
for(const pii &g : que[i]) {
int r = g.first, id = g.second;
pii tmp = query(1, 1, n, i, r);
if(tmp.first <= r) {
ans[id] = 0;
} else {
ans[id] = tmp.second;
}
}
int nx = next[i];
if(nx <= n) {
modify(1, 1, n, nx, {next[nx], A[i]});
}
}
for(int i = 1; i <= q; i ++) {
printf("%d\n", ans[i]);
}
return 0;
}
[LibreOJ 2472][九省联考2018]IIIDX
一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解
还有样例过于草（出题人钦点淫梦运营）
考虑从小到大枚举序列的每一位置\(p\)，然后我们发现每一位置的值的合法性事单调的（小的合法，大了就不合法），这样可以对每一个位置二分答案。
然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)（表示当前还没有被预定的大于等于\(i\)的数有多少个），然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响，然后每次一个点确定是什么值了也要修改对应的前缀区间。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
int lc = o << 1, rc = o << 1 | 1;
minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
if(addv[o] != 0) {
int lc = o << 1, rc = o << 1 | 1;
paint(lc, addv[o]); paint(rc, addv[o]);
addv[o] = 0;
}
}
int left[maxn];
void build_tree(int o, int L, int R) {
// addv[o] = 0;
if(L == R) {
minv[o] = left[L];
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
void update(int o, int L, int R, int ql, int qr, int v) {
if(ql <= L && R <= qr) {
paint(o, v);
} else {
pushdown(o);
int M = (L + R) / 2;
if(ql <= M) update(o << 1, L, M, ql, qr, v);
if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
maintain(o);
}
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
if(ql <= L && R <= qr) {
return minv[o];
} else {
pushdown(o);
int M = (L + R) / 2, ans = INF;
if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
return ans;
}
}
int d[maxn], d2[maxn];
int lsiz;
void process() {
std::sort(d + 1, d + 1 + n);
std::sort(d2 + 1, d2 + 1 + n);
lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
for(int i = 1; i <= n; i ++) {
d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
left[d[i]] ++;
}
for(int i = lsiz - 1; i >= 1; i --) {
left[i] += left[i + 1];
}
build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
for(int i = n; i >= 1; i --) {
siz[i] ++;
int f = (int)floor((R(i)) / k);
siz[f] += siz[i];
}
for(int i = 1; i <= n; i ++) {
int f = (int)floor((R(i)) / k);
if(f > 0) {
update(1, 1, lsiz, 1, A[f], siz[i]);
}
int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
while(true) {
if(R - L <= 3) {
for(int j = R; j >= L; j --) {
if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
ret = j; break;
}
}
break;
}
int M = L + (R - L) / 2;
if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
L = M;
} else {
R = M;
}
}
A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
}
}
int main() {
scanf("%d%Lf", &n, &k);
for(int i = 1; i <= n; i ++) {
scanf("%d", &d[i]); d2[i] = d[i];
}
process(); solve();
for(int i = 1; i <= n; i ++) {
if(i > 1) putchar(' ');
printf("%d", d2[A[i]]);
}
puts(""); return 0;
}
[LibreOJ 2249][NOI2014]购票
在紧张刺激的等待之后终于肝掉了这道题……
本题的DP方程长成这样（其中\(a\)指\(v\)的某个满足距离限制的祖先，\(d_v\)指\(v\)到根的路径长）：
\[f_v = min(f_a + p_v(d_v - d_a) + q_v)\]
化简之后发现：
\[f_v = q_v + p_v d_v + min(f_a - p_v d_a)\]
利用\(min\)中那一块很容易发现是截距式……但是问题在于，我们的转移来源是树上的连续一段祖先，怎样维护他们的凸包？
答案很狂暴啊……用树链剖分套上向量集那题的线段树套凸包，然后完了……
（注意一点细节：本题因为数据范围过大，故可能存在两个向量叉乘爆long long，所以在求凸包时如果直接用叉积判断是否需要删点会炸掉，建议用斜率判断）
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <climits>
using ll = long long;
using T = ll;
using R = long double;
const R eps = 1e-8;
int sign(R x) {
if(fabsl(x) < eps) {
return 0;
} else {
if(x > (R(0.00))) {
return 1;
} else {
return -1;
}
}
}
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if(a.x == b.x) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline R slope(const Vector &a) {
R dx = a.x, dy = a.y;
return (dy / dx);
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && (P[i].x == P[i - 1].x)) continue;
while(bot.size() > 1 && sign(slope(P[i] - bot.back()) - slope(bot.back() - bot[bot.size() - 2])) <= 0) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && (P[i].x == P[i + 1].x)) continue;
while(top.size() > 1 && sign(slope(P[i] - top.back()) - slope(top.back() - top[top.size() - 2])) <= 0) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 200005;
const int maxno = maxn << 2;
const int N = 200000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline T calc_ans(T k, const Point &v) {
return v.y - k * v.x;
}
inline T search(const std::vector<Point> &vec, const T &k) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if((calc_ans(k, vec[lm]) > calc_ans(k, vec[rm]))) {
l = lm;
} else {
r = rm;
}
}
T ans = LLONG_MAX;
for(int i = l; i <= r; i ++) {
ans = std::min(ans, calc_ans(k, vec[i]));
}
return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const T &k) {
if(ql <= L && R <= qr) {
return search(bot[o], k);
} else {
int M = (L + R) / 2;
T ans = LLONG_MAX;
if(ql <= M) {
ans = std::min(ans, query(o << 1, L, M, ql, qr, k));
}
if(qr > M) {
ans = std::min(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
}
return ans;
}
}
int first[maxn];
int next[maxn << 1], to[maxn << 1];
ll dist[maxn << 1];
void add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
dist[cnt] = d;
}
int fa[maxn], dep[maxn], hson[maxn];
ll d[maxn];
int siz[maxn];
int bs[maxn][18];
void dfs_1(int x, int f = -1, int depth = 1) {
fa[x] = bs[x][0] = f; dep[x] = depth;
siz[x] = 1;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != f) {
d[v] = d[x] + dist[i];
dfs_1(v, x, depth + 1);
siz[x] += siz[v];
if(siz[v] > max_siz) {
hson[x] = v; max_siz = siz[v];
}
}
}
}
int dfn[maxn], tid[maxn], up[maxn];
void dfs_2(int x, int a = 1, int f = 0) {
static int cnt = 0;
dfn[x] = ++ cnt; tid[cnt] = x;
up[x] = a;
if(hson[x]) {
dfs_2(hson[x], a, x);
} else {
return;
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != f && v != hson[x]) {
dfs_2(v, v, x);
}
}
}
int k_anc(int x, ll k) {
int yx = x;
for(int j = 17; j >= 0; j --) {
int a = bs[x][j];
if(a != -1 && d[yx] - d[a] <= k) {
x = a;
}
}
#ifdef LOCAL
printf("%d's %lld-th anc : %d\n", yx, k, x);
#endif
return x;
}
int n;
ll get_up(int x, int anc, ll k) {
ll ans = LLONG_MAX;
while(up[x] != up[anc]) {
ans = std::min(ans, query(1, 1, n, dfn[up[x]], dfn[x], k));
x = fa[up[x]];
}
return std::min(ans, query(1, 1, n, dfn[anc], dfn[x], k));
}
ll p[maxn], q[maxn], l[maxn];
ll f[maxn];
void dp(int x) {
#ifdef LOCAL
printf("processing %d...\n", x);
printf("d : %lld\n", d[x]);
#endif
if(x != 1) {
#ifdef LOCAL
printf("b : %lld\n", get_up(fa[x], k_anc(x, l[x]), p[x]));
#endif
f[x] = get_up(fa[x], k_anc(x, l[x]), p[x]) + d[x] * p[x] + q[x];
} else {
f[x] = 0;
}
#ifdef LOCAL
printf("ans : %lld\n", f[x]);
#endif
modify(1, 1, n, dfn[x], Point(d[x], f[x]));
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
dp(v);
}
}
int main() {
int t; scanf("%d%d", &n, &t);
for(int i = 2; i <= n; i ++) {
int father; T s;
scanf("%d%lld%lld%lld%lld", &father, &s, &p[i], &q[i], &l[i]);
add_edge(father, i, s);
}
memset(bs, -1, sizeof(bs));
dfs_1(1); dfs_2(1);
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = bs[i][j - 1];
if(a != -1) {
bs[i][j] = bs[a][j - 1];
}
}
}
dp(1);
for(int i = 2; i <= n; i ++) {
printf("%lld\n", f[i]);
}
return 0;
}
[LibreOJ 2353][NOI2007]货币兑换
emmm做了一下这道神题……（我可能是少有的用动态凸包苟的？）
首先DP方程长这样：
\[f_i = max(f_{i - 1}, f_j\cdot\frac{A_iR_j+B_i}{A_jR_j+B_j})\]
然后这个方程炒鸡复杂……首先\(f_{i - 1}\)不要管了，然后设\(a_i = \frac{f_i}{A_iR_i + B_i}\)。在xjb推了一番之后我们终于得到了截距式……
\[-a_j R_j \frac{A_i}{B_i} + \frac{f_i}{B_i} = a_j\]
但是这玩意太毒瘤了……斜率不可能单调的，这还好，在凸壳上二分/三分一下即可。但问题在于，横坐标也不单调……
这个时候就需要动态维护凸包了（其实是我不会CDQ），我直接把我向量集那题的二进制分组线段树搬了过来……（逃
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <climits>
#include <deque>
#include <cassert>
using R = double;
const R eps = 1e-8;
int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x > 0.00) {
return 1;
} else {
return -1;
}
}
}
struct Point {
R x, y;
Point(R qx = 0, R qy = 0) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(b.x - a.x, b.y - a.y);
}
Vector operator *(const Vector &a, R lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(R lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline R dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline R times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if(sign(a.x - b.x) == 0) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && sign(P[i].x - P[i - 1].x) == 0) continue;
while(bot.size() > 1 && sign(times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && sign(P[i].x - P[i + 1].x) == 0) continue;
while(top.size() > 1 && sign(times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 1000005;
const int N = 1000000;
const int maxno = maxn << 2;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline R calc_ans(R k, const Point &v) {
return v.y - k * v.x;
}
inline R search(const std::vector<Point> &vec, const R &k) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if(sign(calc_ans(k, vec[lm]) - calc_ans(k, vec[rm])) == 1) {
r = rm;
} else {
l = lm;
}
}
R ans = INT_MIN;
for(int i = l; i <= r; i ++) {
ans = std::max(ans, calc_ans(k, vec[i]));
}
return ans;
}
R query(int o, int L, int R, const int &ql, const int &qr, const double &k) {
if(ql <= L && R <= qr) {
return search(top[o], k);
} else {
int M = (L + R) / 2;
double ans = INT_MIN;
if(ql <= M) {
ans = std::max(ans, query(o << 1, L, M, ql, qr, k));
}
if(qr > M) {
ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
}
return ans;
}
}
int n, s;
R A[maxn], B[maxn], Rate[maxn];
R f[maxn];
R dp() {
static double a[maxn];
f[0] = s; f[1] = s; a[1] = f[1] / (A[1] * Rate[1] + B[1]);
modify(1, 1, n, 1, Point(a[1] * Rate[1], a[1]));
for(int i = 2; i <= n; i ++) {
f[i] = query(1, 1, n, 1, i - 1, -A[i] / B[i]) * B[i];
f[i] = std::max(f[i], f[i - 1]);
a[i] = f[i] / (A[i] * Rate[i] + B[i]);
if(i < n) modify(1, 1, n, i, Point(a[i] * Rate[i], a[i]));
}
return f[n];
}
int main() {
scanf("%d%d", &n, &s);
for(int i = 1; i <= n; i ++) {
scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);
}
printf("%.3lf\n", dp());
return 0;
}
[LibreOJ 2197][SDOI2014]向量集
xjb写了写……我评测时候心脏跳得贼快（逃
考虑如果知道了那一段区间的凸包那么怎么做。首先如果向量是往上指的话，一定在上凸壳上找点比较好，反之则在下凸壳上找点比较好（放到坐标系里脑补一下？）。然后我们观察一点，在上凸壳上的最优解往两边的点会越来越劣，所以这玩意是个上凸函数，可以三分答案（我才学的整数三分啊）。
但区间凸包求起来复杂度很爆炸啊……考虑用线段树搞？观察到一点，我们区间查询所使用的线段树节点一定是只包含了已经加进来的点。所以说，一个线段树节点的凸包需要被求的情况只有一种，那就是这个节点完全已加入点被覆盖了。那每次修改之后看是否一个节点完全被已加入点覆盖，如果被完全覆盖的话才去求它的凸包。
这样一来，线段树上每个节点之多会被求一次凸包。线段树有\(\log n\)层，每一层所有节点的大小加起来是\(n\)，所以求凸包耗费的总复杂度是\(n\log^2 n\)级别的。
其实这就是用线段树模拟二进制分组？
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <climits>
#include <cassert>
using ll = long long;
using T = ll;
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if((a.x - b.x) == 0LL) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && (P[i].x - P[i - 1].x) == 0LL) continue;
while(bot.size() > 1 && (times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0LL) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && (P[i].x - P[i + 1].x) == 0LL) continue;
while(top.size() > 1 && (times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0LL) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 400005;
const int maxno = maxn << 2;
const int N = 400000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline T search(const std::vector<Point> &vec, const Point &p) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if(dot(p, vec[lm]) > dot(p, vec[rm])) {
r = rm;
} else {
l = lm;
}
}
T ans = LLONG_MIN;
for(int i = l; i <= r; i ++) {
ans = std::max(ans, dot(p, vec[i]));
}
return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const Point &p) {
if(ql <= L && R <= qr) {
if(p.y > 0LL) {
return search(top[o], p);
} else {
return search(bot[o], p);
}
} else {
int M = (L + R) / 2;
T ans = LLONG_MIN;
if(ql <= M) {
ans = std::max(ans, query(o << 1, L, M, ql, qr, p));
}
if(qr > M) {
ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, p));
}
return ans;
}
}
inline int decode(int x, long long lastans) {
return x ^ (lastans & 0x7fffffff);
}
int main() {
int q; char buf[4]; scanf("%d%s", &q, buf);
bool typ_E = (buf[0] == 'E' && buf[1] == char(0));
T las = 0LL;
int tot = 0;
while(q --) {
char op[4]; scanf("%s", op);
if(op[0] == 'A') {
T x, y; scanf("%lld%lld", &x, &y);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
}
tot ++;
modify(1, 1, N, tot, Point(x, y));
} else {
T x, y, l, r; scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
l = decode(l, las); r = decode(r, las);
}
las = query(1, 1, N, l, r, Point(x, y));
printf("%lld\n", las);
}
}
return 0;
}
[LibreOJ 2142][SHOI2017]相逢是问候
f**********ck我终于肝掉这道题了……在这种辣鸡题上浪费了大量时间
首先一堆\(c\)套起来的幂让我们想到了上帝与集合的正确用法那道题（这题题解我屯到现在没写，还是算了吧就写这题得了）……那让我们试试欧拉降幂公式？
观察欧拉降幂公式
\[a^x\equiv a^{x\mod \varphi(m) + \varphi(m)}\pmod{m}(a\geq m)\]
在多次降幂之后，最后肯定存在一个膜数为1，最后在对这一个地方进行操作的话，虽然\(A[i]\)的位置会被移到更高的次幂上，但是开始出现膜数1的地方一定只能取到1了，所以再对这些地方操作是不合理的。
每次取\(\varphi(x)\)都会使数至少下降一半，所以一个数最多被操作\(\log_2 p\)次。
然后我就跪了（虽然在BZOJ上水过去了），后来手肝gprof发现瓶颈在快速幂（逃
然后这TM怎么优化……膜了一发题解发现正解非常的KBS……
对于一个幂，他的指数肯定可以表示为\(2^{16} a + b\)且\(a\)最大的形式……然后我们可能用到的膜数是很少的，对于每种膜数大力预处理可能的\(b\)的答案和\(a\)的答案，然后求一次幂就\(O(1)\)了……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <utility>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
const int maxn = 50005;
const int maxno = maxn << 2;
const int siz = 65536;
typedef long long ll;
inline ll phi(ll x) {
ll bd = sqrt(x + 0.5);
ll ans = x;
for(ll i = 2; i <= bd; i ++) {
if(x % i == 0LL) {
ans = ans / i * (i - 1LL);
while(x % i == 0LL) {
x /= i;
}
}
}
if(x > 1LL) ans = ans / x * (x - 1LL);
return ans;
}
int n, m;
ll p, c;
ll f[100]; int fn, bd;
ll pow1[70][siz], pow2[70][siz];
inline void process() {
f[0] = p; fn = 1LL;
for(int i = 1; ; i ++) {
f[i] = phi(f[i - 1]);
if(f[i] == 1LL) {
fn = i;
break;
}
}
ll tmp = 1LL; bd = 0;
if(c != 1LL) {
while(tmp * c < p) {
bd ++; tmp *= c;
}
} else {
bd = 0x7fffffff;
}
f[69] = LLONG_MAX;
for(int i = 0; i <= fn; i ++) {
ll c1 = c % f[i]; ll c2 = c1;
int t = 16; while(t --) c2 = (c2 * c2) % f[i];
pow1[i][0] = 1LL; if(i == fn) pow1[i][0] = 0;
for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i];
pow2[i][0] = 1LL; if(i == fn) pow2[i][0] = 0;
for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i];
}
int i = 69;
for(int g = 0; g <= 0; g ++) {
ll c1 = c % f[i]; ll c2 = c1;
int t = 16; while(t --) c2 = (c2 * c2) % f[i];
pow1[i][0] = 1LL;
for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i];
pow2[i][0] = 1LL;
for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i];
}
}
inline ll pow_mod(ll a, ll b, ll p) {
return (pow1[p][b & (siz - 1)] * pow2[p][b >> 16]) % f[p];
}
ll A[maxn];
int be_done[maxn]; ll sumv[maxno];
bool break_down[maxno];
inline void maintain(int o) {
int lc = o << 1, rc = o << 1 | 1;
sumv[o] = (sumv[lc] + sumv[rc]);
if(sumv[o] >= p) sumv[o] -= p;
break_down[o] = (break_down[lc] && break_down[rc]);
}
inline ll get_ans(int i) {
register ll up;
for(int j = be_done[i]; j >= 0; j --) {
if(j == be_done[i]) {
up = A[i];
} else {
if(up > bd) {
up = pow_mod(c % f[j], up, j) + f[j];
} else {
up = pow_mod(c, up, 69);
}
}
}
return up;
}
void build_tree(int o, int L, int R) {
if(L == R) {
be_done[L] = 0;
break_down[o] = 0;
sumv[o] = A[L];
} else {
int M = (L + R) / 2;
build_tree(o << 1, L, M);
build_tree(o << 1 | 1, M + 1, R);
maintain(o);
}
}
int ql, qr;
void modify(int o, int L, int R) {
if(L == R) {
be_done[L] ++;
if(c == 1LL) {
sumv[o] = 1LL;
break_down[o] = true;
} else {
sumv[o] = get_ans(L) % p;
if((A[L] != 0LL && be_done[L] == fn) || (A[L] == 0LL && be_done[L] == fn + 1)) break_down[o] = true;
}
} else {
int M = (L + R) / 2;
if(ql <= M && !break_down[o << 1]) {
modify(o << 1, L, M);
}
if(qr > M && !break_down[o << 1 | 1]) {
modify(o << 1 | 1, M + 1, R);
}
maintain(o);
}
}
ll query(int o, int L, int R) {
if(ql <= L && R <= qr) {
return sumv[o];
} else {
int M = (L + R) / 2;
ll ans = 0;
if(ql <= M) {
ans = (ans + query(o << 1, L, M));
if(ans >= p) ans -= p;
}
if(qr > M) {
ans = (ans + query(o << 1 | 1, M + 1, R));
if(ans >= p) ans -= p;
}
return ans;
}
}
int main() {
// freopen("17.in", "r", stdin);
// freopen("dummy", "w", stdout);
scanf("%d%d%lld%lld", &n, &m, &p, &c);
process();
for(int i = 1; i <= n; i ++) scanf("%lld", &A[i]);
build_tree(1, 1, n);
while(m --) {
int op; scanf("%d%d%d", &op, &ql, &qr);
if(op == 0) {
modify(1, 1, n);
} else {
printf("%lld\n", query(1, 1, n));
// fflush(stdout);
}
}
return 0;
}
[BZOJ 1798]维护序列
万年不更的zzs出现了……
这个题以前竟然没做……近几天做了一下，首交竟然unAC……看样子是我真不会线段树了。
这题不难，唯一需要注意的是乘法标记对加法标记也有影响，而且下传要乘法优先。
代码（警告：此代码exciting）：
/**************************************************************
Problem: 1798
User: danihao123
Language: C++
Result: Accepted
Time:7696 ms
Memory:10980 kb
****************************************************************/
#include <cstdio>
typedef long long ll;
const int maxn=100005;
ll ha;
struct Node{
ll sumv;
int L,R;
ll addv,mulv;
Node *lc,*rc;
Node(ll v,int pos){
sumv=v%ha;
addv=0;
mulv=1;
L=R=pos;
lc=rc=NULL;
}
Node(Node *l,Node *r,int Le,int Ri){
sumv=0;
addv=0;
mulv=1;
L=Le;
R=Ri;
lc=l;
rc=r;
}
void paint_add(ll v){
v=v%ha;
addv=(addv+v)%ha;
ll add_v=(v*((R-L+1)%ha))%ha;
sumv=(sumv+add_v)%ha;
}
void paint_mul(ll v){
v=v%ha;
addv=(addv*v)%ha;
mulv=(mulv*v)%ha;
sumv=(sumv*v)%ha;
}
void maintain(){
if(lc!=NULL && rc!=NULL){
sumv=(lc->sumv+rc->sumv)%ha;
}
}
void pushdown(){
if(mulv!=1){
if(lc!=NULL){
lc->paint_mul(mulv);
}
if(rc!=NULL){
rc->paint_mul(mulv);
}
mulv=1;
}
if(addv!=0){
if(lc!=NULL){
lc->paint_add(addv);
}
if(rc!=NULL){
rc->paint_add(addv);
}
addv=0;
}
}
};
ll A[maxn];
void build_tree(Node* &o,int L,int R){
if(L==R){
o=new Node(A[L],L);
}else{
int M=L+(R-L)/2;
Node *lc,*rc;
build_tree(lc,L,M);
build_tree(rc,M+1,R);
o=new Node(lc,rc,L,R);
o->maintain();
}
}
Node *root;
int ql,qr;
ll v;
ll query_sum(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
return o->sumv;
}else{
int M=L+(R-L)/2;
ll ans=0;
if(ql<=M){
ans=(ans+query_sum(o->lc))%ha;
}
if(qr>M){
ans=(ans+query_sum(o->rc))%ha;
}
return ans;
}
}
void update_add(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_add(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_add(o->lc);
}
if(qr>M){
update_add(o->rc);
}
o->maintain();
}
}
void update_mul(Node *o){
int L=o->L,R=o->R;
o->pushdown();
if(ql<=L && R<=qr){
o->paint_mul(v);
}else{
int M=L+(R-L)/2;
if(ql<=M){
update_mul(o->lc);
}
if(qr>M){
update_mul(o->rc);
}
o->maintain();
}
}
int main(){
register int i;
int n,m,op;
scanf("%d%lld",&n,&ha);
// ha=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%lld",&A[i]);
}
build_tree(root,1,n);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&op,&ql,&qr);
if(ha==1){
if(op==3){
puts("0");
}else{
scanf("%lld",&v);
}
continue;
}
if(op==1){
scanf("%lld",&v);
update_mul(root);
}else{
if(op==2){
scanf("%lld",&v);
update_add(root);
}else{
printf("%lld\n",query_sum(root));
}
}
}
return 0;
}
[BZOJ 3333]排队计划
传说中的大结论题TAT
假设每个数的后面小于它的数的个数为[tex]f[i][/tex]（其位置为[tex]i[/tex]），那么逆序对数显然为[tex]\Sigma f[i][/tex]。
每次操作，只需要将涉及到的数的[tex]f[i][/tex]清为0即可。
为什么呢？任何数的后面比他小的数肯定也被一起拉出来排序了，所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢？因为这之后的比他小的位置，有的可能没被操作，有的可能被操作了。但是就算被操作了，放到后面位置的数照样会比这个数小（因为这个数如果在第一个选定位置的后面（在前面更是不受影响）还没被操作，肯定比那个第一个位置数还大）。
还有一个细节，一个被操作过的数不需要再被操作一遍，操作完了直接设为INF即可。
代码：
/**************************************************************
Problem: 3333
User: danihao123
Language: C++
Result: Accepted
Time:7920 ms
Memory:24264 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=make_pair(A[L],L);
}else{
int M=L+(R-L)/2;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
maintain(o);
}
}
int ql,qr;
pii query_min(int o,int L,int R){
if(ql<=L && R<=qr){
return minv[o];
}else{
int M=L+(R-L)/2;
pii ans=make_pair(INF,INF);
if(ql<=M)
ans=min(ans,query_min(o<<1,L,M));
if(qr>M)
ans=min(ans,query_min(o<<1|1,M+1,R));
return ans;
}
}
int p;
void update(int o,int L,int R){
if(L==R){
minv[o].first=INF;
}else{
int M=L+(R-L)/2;
if(p<=M)
update(o<<1,L,M);
else
update(o<<1|1,M+1,R);
maintain(o);
}
}
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int p){
while(p<=lsh_siz){
C[p]++;
p+=lowbit(p);
}
}
inline int sum(int p){
int ans=0;
while(p>0){
ans+=C[p];
p-=lowbit(p);
}
return ans;
}
inline int readint(){
register int x;
register char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
register int i,p=0;
if(!x){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(bf[i]+'0');
putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
register int i,m,pos;
register ull ans=0;
pii temp;
n=readint();
m=readint();
for(i=1;i<=n;i++){
A[i]=readint();
A2[i]=A[i];
}
sort(A2+1,A2+1+n);
lsh_siz=unique(A2+1,A2+1+n)-A2-1;
for(i=n;i>=1;i--){
pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
f[i]=sum(pos-1);
ans+=f[i];
add(pos);
}
putint(ans);
build_tree(1,1,n);
while(m--){
pos=readint();
ql=pos;
qr=n;
while(true){
temp=query_min(1,1,n);
if(temp.first>A[pos])
break;
p=temp.second;
ans-=f[p];
f[p]=0;
update(1,1,n);
}
putint(ans);
}
return 0;
}
[BZOJ 3306]树
这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。
不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。
代码：
/**************************************************************
Problem: 3306
User: danihao123
Language: C++
Result: Accepted
Time:2308 ms
Memory:17544 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
if(L==R){
minv[o]=A[L];
}else{
MAKE_MID;
build_tree(LCH);
build_tree(RCH);
maintain(o);
}
}
int ql,qr;
int query(SEG_STD){
if(ql<=L && R<=qr){
return minv[o];
}else{
MAKE_MID;
int ans=INF;
if(ql<=M)
ans=min(ans,query(LCH));
if(qr>M)
ans=min(ans,query(RCH));
return ans;
}
}
int p,v;
void update(SEG_STD){
if(L==R){
minv[o]=v;
}else{
MAKE_MID;
if(p<=M)
update(LCH);
else
update(RCH);
maintain(o);
}
}
inline int query(int l,int r){
if(l<1 || l>n || r<1 || r>n)
return INF;
ql=l;
qr=r;
return query(1,1,n);
}
inline void update(int pos,int value){
p=pos;
v=value;
update(1,1,n);
}
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
dfs_clk++;
tid[x]=dfs_clk;
A[dfs_clk]=d[x];
anc[x][0]=fa;
dep[x]=depth;
siz[x]=1;
int i;
for(i=first[x];i;i=next[i]){
dfs(to[i],x,depth+1);
siz[x]+=siz[to[i]];
}
}
void process(){
register int i,j;
for(j=1;(1<<j)<n;j++)
for(i=1;i<=n;i++)
if(anc[i][j-1]!=-1)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
register int p=root,j;
if(dep[p]<dep[x])
return false;
for(j=18;j>=0;j--)
if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
p=anc[p][j];
return p==x;
}
int findAnc(int x,int y){
register int j;
for(j=18;j>=0;j--)
if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
y=anc[y][j];
return y;
}
int getAns(int x){
if(x==root){
return query(1,n);
}else{
if(isAnc(x)){
register int t=findAnc(x,root);
register int l=tid[t],r=tid[t]+siz[t]-1;
return min(query(1,l-1),query(r+1,n));
}else{
return query(tid[x],tid[x]+siz[x]-1);
}
}
}
int main(){
int q,x,f;
register int i;
char buf[3];
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++){
scanf("%d%d",&f,&d[i]);
if(!f){
root=i;
}else{
AddEdge(f,i);
}
}
memset(anc,-1,sizeof(anc));
dfs(root,-1,0);
process();
build_tree(1,1,n);
while(q--){
scanf("%s%d",buf,&x);
if(buf[0]=='V'){
scanf("%d",&f);
update(tid[x],f);
}else{
if(buf[0]=='Q'){
printf("%d\n",getAns(x));
}else{
root=x;
}
}
}
return 0;
}
[BZOJ 3339]Rmq Problem
万恶的标题党啊~
这个题明显扫描线辣……但是怎么扫呢？
我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值，然后用线段树维护。
从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时，需要将[tex][l,next[l]-1][/tex]（[tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置）中的所有大于[tex]A[l][/tex]（[tex]l[/tex]的值）的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats？
答案是否定的。注意到我们真正需要的只是叶子结点，所以其他非叶子结点的最小值全部弄成无限大，然后这样做就可以把最小值当做标记来弄了……非常精巧。
代码：
/**************************************************************
Problem: 3339
User: danihao123
Language: C++
Result: Accepted
Time:1988 ms
Memory:10396 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=A[L];
}else{
int M=L+(R-L)/2;
minv[o]=INF;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
}
}
inline void paint(int o,int v){
minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
paint(o<<1,minv[o]);
paint(o<<1|1,minv[o]);
minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
if(L==R)
return minv[o];
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(pos<=M)
return query(o<<1,L,M);
else
return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
if(ql<=L && R<=qr){
paint(o,v);
}else{
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(ql<=M)
update(o<<1,L,M);
if(qr>M)
update(o<<1|1,M+1,R);
}
}
inline int readint(){
register int x=0;
register char c;
fread(&c,1,1,stdin);
while(!isdigit(c))
fread(&c,1,1,stdin);
while(isdigit(c)){
x=x*10+c-'0';
fread(&c,1,1,stdin);
}
return x;
}
int buf[21];
inline void putint(int x){
register int i,p=0;
if(!x){
buf[p++]=0;
}else{
while(x){
buf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(buf[i]+'0');
putchar('\n');
}
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
int id;
int l,r;
int ans;
};
bool cmp1(const Query& x,const Query& y){
if(x.l==y.l)
return x.r<y.r;
else
return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
int n,q;
register int i,l=1,k=0;
n=readint();
q=readint();
for(i=1;i<=n;i++){
V[i]=readint();
vis[V[i]]=true;
if(k==V[i])
while(vis[k])
k++;
A[i]=k;
}
build_tree(1,1,n);
for(i=n;i>=1;i--){
if(!last[V[i]])
next[i]=n+1;
else
next[i]=last[V[i]];
last[V[i]]=i;
}
for(i=1;i<=q;i++){
QS[i].id=i;
QS[i].l=readint();
QS[i].r=readint();
}
sort(QS+1,QS+1+q,cmp1);
for(i=1;i<=q;i++){
while(l<QS[i].l){
ql=l;
qr=next[l]-1;
v=V[l];
update(1,1,n);
l++;
}
pos=QS[i].r;
QS[i].ans=query(1,1,n);
}
sort(QS+1,QS+1+q,cmp2);
for(i=1;i<=q;i++){
putint(QS[i].ans);
}
return 0;
}
