- P64's solution
P64's Solution
- 2025-9-14 20:11:53 @
这是可持久化线段树模板题,粘贴模板即可。
#include <bits/stdc++.h>
using namespace std;
namespace INPUT_SPACE
{
const int S = 1 << 25;
char B[S];
char* H;
char* T;
inline char gc()
{
if (H == T)
{
H = B;
T = B + fread(B, 1, S, stdin);
}
if (H == T) return 0;
char* I = H;
H++;
return *I;
}
inline unsigned int inn()
{
unsigned int x = 0;
char c;
c = gc();
while (c < '0') c = gc();
while (c >= '0')
{
x *= 10;
x += c - '0';
c = gc();
}
return x;
}
};
using INPUT_SPACE::inn;
const int PTD = 30;
struct V
{
int a;
int ll;
int rr;
int l;
int r;
};
struct U
{
V v[8000012];
int roots[200012];
int ts;
int st;
void init(int n)
{
ts = n;
st = n;
for (int i = 1; i <= n; i++)
v[i].rr = (1 << PTD) - 1;
for (int i = 1; i <= n; i++)
roots[i] = i;
}
void expand(int b)
{
if (v[b].ll == v[b].rr) return;
if (v[b].l == 0)
{
ts++;
v[ts] = (V){0, v[b].ll, (v[b].ll + v[b].rr) >> 1, 0, 0};
v[b].l = ts;
}
if (v[b].r == 0)
{
ts++;
v[ts] = (V){0, ((v[b].ll + v[b].rr) >> 1) + 1, v[b].rr, 0, 0};
v[b].r = ts;
}
}
bool create(int x, int b)
{
if(v[b].ll == x && v[b].rr == x) return true;
expand(b);
int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid+1;
if (x <= lmid) return create(x, v[b].l);
if (x >= rmid) return create(x, v[b].r);
}
bool add(int x, int y, int b, int c)
{
v[b].a += v[c].a + y;
if (v[b].ll == x && v[b].rr == x) return true;
int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid + 1;
if (x <= lmid) v[b].r = v[c].r;
if (x >= rmid) v[b].l = v[c].l;
expand(b);
if (x <= lmid) return add(x, y, v[b].l, v[c].l);
if (x >= rmid) return add(x, y, v[b].r, v[c].r);
}
int get(int l, int r, int b)
{
if (!b) return 0;
if (l == v[b].ll && r == v[b].rr) return v[b].a;
int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid + 1;
if (r <= lmid) return get(l, r, v[b].l);
if (l >= rmid) return get(l, r, v[b].r);
return get(l, lmid, v[b].l) + get(rmid, r, v[b].r);
}
};
U t;
int a[200012];
int main()
{
int n = inn(), m = inn();
t.init(n + 1);
for (int i = 1; i <= n; i++)
{
a[i] = inn();
t.create(a[i], t.roots[n + 1]);
}
t.roots[0] = t.roots[n + 1];
for (int i = 1; i <= n; i++)
t.add(a[i], 1, t.roots[i], t.roots[i - 1]);
for (int i = 1; i <= m; i++)
{
int l = inn(), r = inn(), k = inn();
int ll = 0, rr = 1073741823;
while (ll < rr)
{
int mid = (0ll + ll + rr) / 2;
int x = t.get(0, mid, t.roots[r]);
int y = t.get(0, mid, t.roots[l - 1]);
if (x - y >= k) rr = mid;
else ll = mid + 1;
}
int a1 = t.get(0, ll, t.roots[r]) - t.get(0, ll, t.roots[l - 1]);
int a2 = t.get(0, ll - 1, t.roots[r]) - t.get(0, ll - 1, t.roots[l - 1]);
cout << a1 - a2 << endl;
}
return 0;
}