CYMario

1612

WanderOvO

Arthur_5

Avaritia
Peter_5
Seven1

Catch-22
Asiim0v
limie

zhoumingxuan
Once.

linxudong
w完整z_3
Magic_Zq

tangmmmy

CYMario
1天前
using namespace std;
typedef long long ll;
ll rd()
{
ll k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}
return f > 0 ? k : -k;
}
void wr(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
// 1D Fenwick Tree
template <typename T>
struct BIT
{
int N;
vector<T> data;

BIT() = default;
BIT(int size) { init(size); }

void init(int size)
{
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x)
{
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const
{
if (k <= 0)
return T();
T ret = T();
for (; k; k -= k & -k)
ret += data[k];
return ret;
}

inline T sum(int l, int r) const { return sum(r) - sum(l); }
};

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {

using P = pair<S, S>;
S N, M;
vector<BIT<T>> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);
for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j) ys[j].push_back(ps[i].second);
sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P& a, const P& b) { return a.first < b.first; }) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));
for (++i; i <= N; i += i & -i) bit[i].add(id(i, y), a);
}

T sum(S x, S y) const {
T ret = T();
for (int a = id(x); a; a -= a & -a) ret += bit[a].sum(id(a, y));
return ret;
}

T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
/*
T ret = T();
int a = id(xl), b = id(xr);
while (a != b) {
if (a < b) {
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else {
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
*/
}
};
struct Event
{
bool flag; // 0 : add 1 : query
int xl, yl, xr, yr;
ll w;
};
vector<Event> events;
struct point
{
int x, y;
} a[maxn];
int pos[maxn];
ll inversion;
int main()
{
FenwickRangeTree<int, int> bit;
int n = rd(), m = rd();
for (int i = 1; i <= n; ++i)
a[i].x = i, a[i].y = rd(), pos[a[i].y] = i, bit.add_point(a[i].x, a[i].y);

/*
sort(tmp, tmp + n);
int real_n = unique(tmp, tmp + n) - tmp;
BIT<int> tree(real_n + 1);
*/
BIT<int> tree(n + 1);
for (int i = 1; i <= n; ++i)
{
//int x = lower_bound(tmp, tmp + real_n, a[i]) - tmp + 1;
inversion += tree.sum(a[i].y + 1, n + 1); // left close right open
}

bit.build();
for (int i = 1; i <= n; ++i)
while(m--)
{
wr(inversion), putchar('\n');
int y = rd(), x = pos[y];
//printf("position: (%d, %d)", x, y);
//printf("minus from before : %d after : %d\n", bit.sum(1, y + 1, x, n + 1), bit.sum(x + 1, 1, n + 1, y));
inversion -= (bit.sum(1, y + 1, x, n + 1) + bit.sum(x + 1, 1, n + 1, y));
}

}


CYMario
1天前

using namespace std;
typedef long long ll;
ll rd()
{
ll k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}
return f > 0 ? k : -k;
}
void wr(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
// 1D Fenwick Tree
template <typename T>
struct BIT
{
int N;
vector<T> data;

BIT() = default;
BIT(int size) { init(size); }

void init(int size)
{
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x)
{
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const
{
if (k <= 0)
return T();
T ret = T();
for (; k; k -= k & -k)
ret += data[k];
return ret;
}

inline T sum(int l, int r) const { return sum(r) - sum(l); }
};

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {

using P = pair<S, S>;
S N, M;
vector<BIT<T>> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) { ps.push_back(make_pair(x, y)); }

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);
for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j) ys[j].push_back(ps[i].second);
sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P& a, const P& b) { return a.first < b.first; }) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));
for (++i; i <= N; i += i & -i) bit[i].add(id(i, y), a);
}

T sum(S x, S y) const {
T ret = T();
for (int a = id(x); a; a -= a & -a) ret += bit[a].sum(id(a, y));
return ret;
}

T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
/*
T ret = T();
int a = id(xl), b = id(xr);
while (a != b) {
if (a < b) {
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else {
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
*/
}
};
struct Event
{
bool flag; // 0 : add 1 : query
int xl, yl, xr, yr;
ll w;
};
vector<Event> events;
struct point
{
int x, y;
} a[maxn];
int pos[maxn];
ll inversion;
int main()
{
FenwickRangeTree<int, int> bit;
int n = rd(), m = rd();
for (int i = 1; i <= n; ++i)
a[i].x = i, a[i].y = rd(), pos[a[i].y] = i, bit.add_point(a[i].x, a[i].y);

/*
sort(tmp, tmp + n);
int real_n = unique(tmp, tmp + n) - tmp;
BIT<int> tree(real_n + 1);
*/
BIT<int> tree(n + 1);
for (int i = 1; i <= n; ++i)
{
//int x = lower_bound(tmp, tmp + real_n, a[i]) - tmp + 1;
inversion += tree.sum(a[i].y + 1, n + 1); // left close right open
}

bit.build();
for (int i = 1; i <= n; ++i)
while(m--)
{
wr(inversion), putchar('\n');
int y = rd(), x = pos[y];
//printf("position: (%d, %d)", x, y);
//printf("minus from before : %d after : %d\n", bit.sum(1, y + 1, x, n + 1), bit.sum(x + 1, 1, n + 1, y));
inversion -= (bit.sum(1, y + 1, x, n + 1) + bit.sum(x + 1, 1, n + 1, y));
}

}


CYMario
1天前
// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {
struct BIT {
int N;
vector<T> data;

BIT() = default;
BIT(int size) {
init(size);
}

void init(int size) {
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x) {
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const {
if (k <= 0)
return T();

T ret = T();

for (; k; k -= k & -k)
ret += data[k];

return ret;
}

inline T sum(int l, int r) const {
return sum(r) - sum(l);
}
};

using P = pair<S, S>;
S N, M;
vector<BIT> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) {
ps.push_back(make_pair(x, y));
}

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);

for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j)
ys[j].push_back(ps[i].second);

sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P & a, const P & b) {
return a.first < b.first;
}) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));

for (++i; i <= N; i += i & -i)
}

T sum(S x, S y) const {
T ret = T();

for (int a = id(x); a; a -= a & -a)
ret += bit[a].sum(id(a, y));

return ret;
}

T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
/*
T ret = T();
int a = id(xl), b = id(xr);
while (a != b) {
if (a < b) {
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else {
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
*/
}
};
struct Event {
bool flag; // 0 : add 1 : query
int xl, yl, xr, yr;
ll w;
};
vector<Event> events;
int main() {
//auto f = [](ll a, ll b) {
//    return a + b;
//};
FenwickRangeTree<int, ll> bit;
int n = rd(), q = rd();
events.resize(n + q);

for (int i = 0; i < n; ++i) {
events[i].flag = 0;
events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
}

for (int i = n; i < n + q; ++i) {
events[i].flag = 1;

if (!events[i].flag) {
events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
} else
events[i].xl = rd(), events[i].yl = rd(), events[i].xr = rd() + 1, events[i].yr = rd() + 1;
}

bit.build();

for (int i = 0; i < n + q; ++i) {
if (!events[i].flag)
else
wr(bit.sum(events[i].xl, events[i].yl, events[i].xr, events[i].yr)), putchar('\n');
}
}


CYMario
1天前

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type
template <typename S, typename T>
struct FenwickRangeTree {
struct BIT {
int N;
vector<T> data;

BIT() = default;
BIT(int size) {
init(size);
}

void init(int size) {
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x) {
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const {
if (k <= 0)
return T();

T ret = T();

for (; k; k -= k & -k)
ret += data[k];

return ret;
}

inline T sum(int l, int r) const {
return sum(r) - sum(l);
}
};

using P = pair<S, S>;
S N, M;
vector<BIT> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) {
ps.push_back(make_pair(x, y));
}

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);

for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j)
ys[j].push_back(ps[i].second);

sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P & a, const P & b) {
return a.first < b.first;
}) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));

for (++i; i <= N; i += i & -i)
}

T sum(S x, S y) const {
T ret = T();

for (int a = id(x); a; a -= a & -a)
ret += bit[a].sum(id(a, y));

return ret;
}

T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
/*
T ret = T();
int a = id(xl), b = id(xr);
while (a != b) {
if (a < b) {
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else {
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
*/
}
};
struct Event {
bool flag; // 0 : add 1 : query
int xl, yl, xr, yr;
ll w;
};
vector<Event> events;
int main() {
//auto f = [](ll a, ll b) {
//    return a + b;
//};
FenwickRangeTree<int, ll> bit;
int n = rd(), q = rd();
events.resize(n + q);

for (int i = 0; i < n; ++i) {
events[i].flag = 0;
events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
}

for (int i = n; i < n + q; ++i) {
events[i].flag = 1;

if (!events[i].flag) {
events[i].xl = rd(), events[i].yl = rd(), events[i].w = rd();
} else
events[i].xl = rd(), events[i].yl = rd(), events[i].xr = rd() + 1, events[i].yr = rd() + 1;
}

bit.build();

for (int i = 0; i < n + q; ++i) {
if (!events[i].flag)
else
wr(bit.sum(events[i].xl, events[i].yl, events[i].xr, events[i].yr)), putchar('\n');
}
}


CYMario
1天前
#include <stdio.h>
#include <string.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define full 114514
#define single 1
#define maxn 1010
#define maxv 200010
#define maxq 200010

char eof_flag;
char rd(int *s)
{
if (eof_flag)
return 0;

int k = 0, f = 1;
char c = getchar();

while (c != '-' && (c < '0' || c > '9'))
{
if (c == EOF)
{
eof_flag = 1;
return 0;
}

c = getchar();
}

f = (c == '-') ? -1 : 1;
k = (c == '-') ? 0 : (c ^ 48);
c = getchar();

while (c >= '0' && c <= '9')
k = (k << 1) + (k << 3) + (c ^ 48), c = getchar();

if (c == EOF)
eof_flag = 1;

(*s) = f > 0 ? k : -k;
return 1;
}

void wr(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + 48);
}

int n, V; // V : size of pack
int cost, value, cnt;
int dp[maxv];
int deq[maxq];  // deque of index
int deqv[maxq]; // deque of value

void buildDP_01Pack(int cost, int value)
{
for (int v = V; v >= cost; --v)
dp[v] = max(dp[v], dp[v - cost] + value);
}

void buildDP_FullPack(int cost, int value)
{
for (int v = cost; v <= V; ++v)
dp[v] = max(dp[v], dp[v - cost] + value);
}

void buildDP_MultiPack(int cost, int value, int count)
{
for (int a = 0; a < cost; ++a)
{
int s = 0, t = 0; // init deque
for (int j = 0; j * cost + a <= V; j++)
{
int val = dp[j * cost + a] - j * value;
while (s < t && deqv[t - 1] <= val)
t--;                     // pop_back
deq[t] = j, deqv[t++] = val; // push_back
dp[j * cost + a] = deqv[s] + j * value;
if (deq[s] == j - count)
++s; // pop_front
}
}
}

void buildDP_CombinedPack(int cost, int value, int count)
{
if (count == single)
buildDP_01Pack(cost, value);
else if (count == full)
buildDP_FullPack(cost, value);
else
buildDP_MultiPack(cost, value, count);
}

int main()
{
while (rd(&n) && rd(&V))
{
memset(dp, 0, (V + 1) * sizeof(dp[0]));
while (n--)
{
rd(&cost), rd(&value), rd(&cnt);
buildDP_CombinedPack(cost, value, cnt);
}
wr(dp[V]), putchar('\n');
}
}


CYMario
1天前
#include <stdio.h>
typedef long long ll;
ll gcd(ll a, ll b) {
//特判
if (a < 0)
a = -a;

if (b < 0)
b = -b;

if (a == 0)
return b;

if (b == 0)
return a;

int r = 0;//a和b的2^r形式的公因子

while (!((a & 1) || (b & 1))) {
//a和b都是偶数的时候
a >>= 1;
b >>= 1;
r++;
}

ll ret = 0;

while (1) {//首次到这里时，至少一奇
while (!(a & 1))
a >>= 1;//剔除a中的因子2

while (!(b & 1))
b >>= 1;//剔除b中的因子2

if (a > b)
a = a - b;
else
b = b - a;//简化为gcd(max(a,b)-min(a,b),min(a,b)) 可以证明这步的正确性

if (0 == a) {
ret = b << r;    //最后这步倒是和欧几里得做法类似
break;
}

if (0 == b) {
ret = a << r;
break;
}
}

return ret;
}
ll solve(ll n, ll m) {
ll ret = 0;

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ret += (n - i + 1) * (m - j + 1) * (6 * i * j - 2 * gcd(i, j));

return ret;
}
ll n, m;
int main() {
scanf("%lld%lld", &n, &m);
printf("%lld\n", solve(n, m));
}


CYMario
1天前
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010
using namespace std;
typedef long long ll;
inline void write(int x) {
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
inline int read() {
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') {
if (c == '-')f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + c - 48;
c = getchar();
}
return k * f;
}
int n, m;
int a[maxn], b[maxn];//原有数组和离散化排序后的数组
int root[maxn];
int l, r, k;
struct P_SegmentTree_KthElement {
struct Node {
int lchild, rchild;
int value_sum;
}nodes[maxn * 30];
int _size;
P_SegmentTree_KthElement() {
_size = 0;
memset(nodes, 0, sizeof(nodes));
}
inline void build(int& root, int l, int r) {
root = ++_size;
if (l == r) { nodes[root].value_sum = 0; return; }
int m = (l + r) >> 1;
build(nodes[root].lchild, l, m);
build(nodes[root].rchild, m + 1, r);
}
//对应的修改点
inline int update(int preVer, int l, int r, int x) {
int rootVer = ++_size;
nodes[rootVer].lchild = nodes[preVer].lchild;
nodes[rootVer].rchild = nodes[preVer].rchild;
nodes[rootVer].value_sum = nodes[preVer].value_sum + 1;
int m = (l + r) >> 1;
if (l < r) {
if (x <= m)nodes[rootVer].lchild = update(nodes[preVer].lchild, l, m, x);
else nodes[rootVer].rchild = update(nodes[preVer].rchild, m + 1, r, x);
}
return rootVer;
}
inline int query(int ver1, int ver2, int l, int r, int k) {
if (l >= r)return l;
int x = nodes[nodes[ver2].lchild].value_sum - nodes[nodes[ver1].lchild].value_sum;
int m = (l + r) >> 1;
if (x >= k)return query(nodes[ver1].lchild, nodes[ver2].lchild, l, m, k);
else return query(nodes[ver1].rchild, nodes[ver2].rchild, m + 1, r, k - x);
}
};
P_SegmentTree_KthElement tree;
int main() {
for (int i = 1; i <= n; ++i)a[i] = read(), b[i] = a[i];
sort(b + 1, b + n + 1);
int realn = unique(b + 1, b + n + 1) - b - 1;
tree.build(root[0], 1, realn);
for (int i = 1; i <= n; ++i) {
int t = lower_bound(b + 1, b + 1 + realn, a[i]) - b;
root[i] = tree.update(root[i - 1], 1, realn, t);
//逐一元素找到离散数组中的对应位置,按这个位置来建树
}
while (m--) {
write(b[tree.query(root[l - 1], root[r], 1, realn, k)]);
putchar('\n');
}
}


CYMario
1天前

分块做法

#include <stdio.h>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
const int INF1 = 100000000, INF2 = 2147483647;

int rd() {
int k = 0, f = 1;
char c = getchar();

while (c < '0' || c > '9') {
if (c == '-')
f = -1;

c = getchar();
}

while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}

return f > 0 ? k : -k;
}
void wr(int x) {
if (x < 0)
putchar('-'), x = -x;

if (x > 9)
wr(x / 10);

putchar(x % 10 + '0');
}

// Data Structure from nzy

namespace Block {
const int N = 50005;
const int block_len = 1000;
int d[N], sd[N], pos[N], l[(N / block_len) + 5], r[(N / block_len) + 5], n, m;

void init(int _n) {
n = _n;

for (int i = 1; i <= n; ++i)
sd[i] = d[i] = rd();

m = (n + block_len - 1) / block_len;

for (int i = 1; i <= m; i++) {
l[i] = block_len * (i - 1) + 1;
r[i] = block_len * i;
}

r[m] = n;

for (int i = 1; i <= m; i++) {
for (int j = l[i]; j <= r[i]; j++)
pos[j] = i;

sort(sd + l[i], sd + r[i] + 1);
}
}

void modify(int p, int val) {
for (int i = l[pos[p]]; i <= r[pos[p]]; i++) {
if (sd[i] == d[p]) {
sd[i] = val;
break;
}
}

sort(sd + l[pos[p]], sd + r[pos[p]] + 1);
d[p] = val;
}
int get_rank_by_num(int left, int right, int val) {
int cnt = 0;

for (int i = pos[left]; i <= pos[right]; i++) {
if (left <= l[i] && r[i] <= right)
cnt += lower_bound(sd + l[i], sd + r[i] + 1, val) - (sd + l[i]);
else {
for (int j = max(l[i], left); j <= min(r[i], right); j++)
if (d[j] < val)
cnt++;
}
}

return cnt + 1;
}

int get_prev(int left, int right, int c) {
int res = -INF2;

for (int i = pos[left]; i <= pos[right]; i++) {
if (left <= l[i] && r[i] <= right) {
int p = lower_bound(sd + l[i], sd + r[i] + 1, c) - sd - 1;

if (left <= p && p <= right && sd[p] < c)
res = max(res, sd[p]);
} else {
for (int j = max(l[i], left); j <= min(r[i], right); j++)
if (d[j] < c)
res = max(res, d[j]);
}
}

return res;
}
int get_next(int left, int right, int c) {
int res = INF2;

for (int i = pos[left]; i <= pos[right]; i++) {
if (left <= l[i] && r[i] <= right) {
int p = upper_bound(sd + l[i], sd + r[i] + 1, c) - sd;

if (left <= p && p <= right && sd[p] > c)
res = min(res, sd[p]);
} else {
for (int j = max(l[i], left); j <= min(r[i], right); j++)
if (d[j] > c)
res = min(res, d[j]);
}
}

return res;
}

int get_num_by_rank(int left, int right, int rk) {
int lo = 0, hi = INF1;

while (lo < hi) {
int mid = (lo + hi) >> 1;

if (get_rank_by_num(left, right, mid) <= rk)
lo = mid + 1;
else
hi = mid;
}

return get_prev(left, right, lo);
}
}
int n, m;
int op, l, r, pos, val, rk;
int main() {
n = rd(), m = rd();
Block::init(n);

while (m--) {
op = rd();

switch (op) {
/*
case 1:
l = rd(), r = rd(), val = rd();
wr(Block::get_rank_by_num(l, r, val)), putchar('\n');
break;

case 2:
l = rd(), r = rd(), rk = rd();
wr(Block::get_num_by_rank(l, r, rk)), putchar('\n');
break;
*/
case 1:
pos = rd(), val = rd();
Block::modify(pos, val);
break;

case 2:
l = rd(), r = rd(), val = rd();
wr(Block::get_prev(l, r, val)), putchar('\n');
break;
/*
case 5:
l = rd(), r = rd(), val = rd();
wr(Block::get_next(l, r, val)), putchar('\n');
break;
*/
default:
break;
}
}
}


CYMario
2天前

1. cdq做法

//一维排序二维cdq三维bittree
#include<cstdio>
#include<ctime>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 200005;
struct ori
{
int a, b, c;
ori(int x = 0, int y = 0, int z = 0)
{
a = x;
b = y;
c = z;
}
bool operator < (const ori& o) const
{
if (a==o.a)
{
if (b==o.b)
{
return c<o.c;
}
return b<o.b;
}
return a<o.a;
}
bool operator == (const ori& o) const
{
return a==o.a&&b==o.b&&c==o.c;
}
}ele[MAXN];
int n, m, k;
struct node
{
int a, b, c, sz, ans;
node(int u = 0, int v = 0, int w = 0, int x = 0, int y = 0)
{
a = u, b = v, c = w, sz = x, ans = y;
}
}o[MAXN], e[MAXN];
int p, q, tot, ans[MAXN];
int bit[MAXN];
void Add(int x, int val)
{
while (x <= k)
{
bit[x] += val;
x += x & -x;
}
}
int Query(int x)
{
int ret = 0;
while (x)
{
ret += bit[x];
x -= x & -x;
}
return ret;
}
void cdq(int L, int R)
{
if (L >= R) return;
int Mid = L + R >> 1;

cdq(L, Mid);
cdq(Mid + 1, R);

p = L, q = Mid + 1, tot = L;
while (p <= Mid && q <= R)
{
if (o[p].b <= o[q].b)
{
e[tot++] = o[p++];
}
else
{
o[q].ans += Query(o[q].c);
e[tot++] = o[q++];
}
}
while (q <= R)
{
o[q].ans += Query(o[q].c);
e[tot++] = o[q++];
}
for (int i = L; i < p; ++i) Add(o[i].c, -o[i].sz);
while (p <= Mid) e[tot++] = o[p++];
for (int i = L; i <= R; ++i) o[i] = e[i];
}
int main()
{
scanf("%d%d", &n, &k);
for (int aa, bb, cc, i = 1; i <= n; ++i)
{
scanf("%d%d%d", &aa, &bb, &cc);
ele[i] = ori(aa, bb, cc);
}
sort(ele+1, ele+1+n);
for (int i = 1; i <= n; ++i)
{
if (ele[i] == ele[i-1] && i > 1)
{
++o[m].sz;
continue;
}
o[++m] = node(ele[i].a, ele[i].b, ele[i].c, 1);
}
cdq(1, m);
for (int i = 1; i <= m; ++i) ans[o[i].ans+o[i].sz-1] += o[i].sz;
for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
return 0;
}


2.2D动态树状数组做法

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <vector>
using namespace std;
int rd() {
int k = 0, f = 1;
char c = getchar();

while (c < '0' || c > '9') {
if (c == '-')
f = -1;

c = getchar();
}

while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}

return f > 0 ? k : -k;
}
void wr(int x) {
if (x < 0)
putchar('-'), x = -x;

if (x > 9)
wr(x / 10);

putchar(x % 10 + '0');
}
// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type

template <typename S, typename T>
struct FenwickRangeTree {
struct BIT {
int N;
vector<T> data;

BIT() = default;
BIT(int size) {
init(size);
}

void init(int size) {
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x) {
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const {
if (k <= 0)
return T();

T ret = T();

for (; k; k -= k & -k)
ret += data[k];

return ret;
}

inline T sum(int l, int r) const {
return sum(r) - sum(l);
}
};

using P = pair<S, S>;
S N, M;
vector<BIT> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) {
ps.push_back(make_pair(x, y));
}

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);

for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j)
ys[j].push_back(ps[i].second);

sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P & a, const P & b) {
return a.first < b.first;
}) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));

for (++i; i <= N; i += i & -i)
}

T sum(S x, S y) const {
T ret = T();

for (int a = id(x); a; a -= a & -a)
ret += bit[a].sum(id(a, y));

return ret;
}
// x : [xl, xr)  y : [yl, yr)
T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
}
};
struct item {
int a, b, c;
bool operator == (const item &o) const {
return a == o.a && b == o.b && c == o.c;
}
bool operator <(const item &o) const {
if (a != o.a)
return a < o.a;
else if (b != o.b)
return b < o.b;
else
return c < o.c;
}
} a[100010];
FenwickRangeTree<int, int> bit;
int ans[100010], cnt[100010];//cnt 记录和当前自己属性值完全一样的个数
int main() {
int n = rd(), k = rd();

for (int i = 0; i < n; ++i)
a[i].a = rd(), a[i].b = rd(), a[i].c = rd();

sort(a, a + n);

for (int i = 0; i < n; ++i) {
if (i != (n - 1) && a[i] == a[i + 1])
continue;
else
}

bit.build();

for (int i = 0; i < n; ++i) {
if (i != (n - 1) && a[i] == a[i + 1])
cnt[i + 1] = cnt[i] + 1;
else {
int tmp = bit.sum(0, 0, a[i].b + 1, a[i].c + 1) + cnt[i];
ans[tmp] += cnt[i] + 1;
bit.add(a[i].b, a[i].c, cnt[i] + 1);
}
}

for (int i = 0; i < n; ++i)
wr(ans[i]), putchar('\n');
}


CYMario
2天前

二维动态树状数组做法(性质–半离线预处理)

通过代码

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type

template <typename S, typename T>
struct FenwickRangeTree {
struct BIT {
int N;
vector<T> data;

BIT() = default;
BIT(int size) {
init(size);
}

void init(int size) {
N = size;
data.assign(N + 1, 0);
}

// data[k] += x
void add(int k, T x) {
for (++k; k <= N; k += k & -k)
data[k] += x;
}

T sum(int k) const {
if (k <= 0)
return T();

T ret = T();

for (; k; k -= k & -k)
ret += data[k];

return ret;
}

inline T sum(int l, int r) const {
return sum(r) - sum(l);
}
};

using P = pair<S, S>;
S N, M;
vector<BIT> bit;
vector<vector<S>> ys;
vector<P> ps;

FenwickRangeTree() = default;

void add_point(S x, S y) {
ps.push_back(make_pair(x, y));
}

void build() {
sort(begin(ps), end(ps));
ps.erase(unique(begin(ps), end(ps)), end(ps));
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);

for (int i = 0; i <= N; ++i) {
for (int j = i + 1; j <= N; j += j & -j)
ys[j].push_back(ps[i].second);

sort(begin(ys[i]), end(ys[i]));
ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
bit[i].init(ys[i].size());
}
}

int id(S x) const {
return lower_bound(
begin(ps), end(ps), make_pair(x, S()),
[](const P & a, const P & b) {
return a.first < b.first;
}) -
begin(ps);
}

int id(int i, S y) const {
return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
}

void add(S x, S y, T a) {
int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
assert(ps[i] == make_pair(x, y));

for (++i; i <= N; i += i & -i)
}

T sum(S x, S y) const {
T ret = T();

for (int a = id(x); a; a -= a & -a)
ret += bit[a].sum(id(a, y));

return ret;
}
// x : [xl, xr)  y : [yl, yr)
T sum(S xl, S yl, S xr, S yr) const {
return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
}
};
struct item {
int a, b, c;
bool operator == (const item &o) const {
return a == o.a && b == o.b && c == o.c;
}
bool operator <(const item &o) const {
if (a != o.a)
return a < o.a;
else if (b != o.b)
return b < o.b;
else
return c < o.c;
}
} a[100010];
FenwickRangeTree<int, int> bit;
int ans[100010], cnt[100010];// cnt 记录和当前自己属性值完全一样的个数(除自身之外)
int main() {
int n = rd(), k = rd();

for (int i = 0; i < n; ++i)
a[i].a = rd(), a[i].b = rd(), a[i].c = rd();

sort(a, a + n);// 按照 a 维度 从小到大排序

//第一遍过程 : 仅是模拟验算，只把该加的点加进去
for (int i = 0; i < n; ++i) {
if (i != (n - 1) && a[i] == a[i + 1])
continue;
else
}
//得到所有点之后，二维动态树状数组统一建树，这也就是所谓的半离线方法(预处理离线，而非全程离线)
bit.build();

for (int i = 0; i < n; ++i) {
// 如果和后一个相同，则该点不做计算，并将自己的重复个数传递给后面
if (i != (n - 1) && a[i] == a[i + 1])
cnt[i + 1] = cnt[i] + 1;
else {
// 查询与自己不一样且满足条件的 g(i) 与和自己完全一样的 h(i) 对应的f(i)=g(i)+h(i)
int tmp = bit.sum(0, 0, a[i].b + 1, a[i].c + 1) + cnt[i];
// 对答案 f(i) 个数的贡献为 h(i) + 1
ans[tmp] += cnt[i] + 1;
// 这部分计算完毕之后，所有 h(i)+1 个重合的点加进树中，将 h(i)+1视为对该点的点权贡献
bit.add(a[i].b, a[i].c, cnt[i] + 1);
}
}

for (int i = 0; i < n; ++i)
wr(ans[i]), putchar('\n');
}