# [2017-2018 ACM-ICPC Latin American Regional Programming Contest] D. Daunting device

### Statement

Given an array of length $$1 \leq L \leq 10^5$$, initially filled with 1. Define cnt[i] as the number of elements in the array that are equal to i. You should perform no more than $$10^5$$ operations. Each operation is four integers $$P, X, A, B$$, and let $$M_1 = (A + S^2) \bmod L, M_2 = (A + (S + B)^2) \bmod L$$, where S = cnt[P], then assign all elements with indices in $$[min(M_1, M_2), max(M_1, M_2)]$$ with value X. After all operations performed, output the maximum cnt[i] over all possible values of i.

### Solution

The main idea of the solution is just to simulate the operations in a reasonable time complexity. In fact, various possible solutions exist, including segment tree and square root decomposition. However, the fastest solution (at least theoretically) I know is employing balanced binary search trees.

We use the nodes of the balanced binary search tree to represent contiguous intervals of the array with same values. Additionally, we maintain an array “cnt”, which has the meaning as described in problem statement.

When updating an interval [l, r) to value X, we delete all nodes representing the interval [l, r), updating the array “cnt”. Note that this may split the nodes that across the boundaries of given interval. Finally, we inserting a new node which represents [l, r) with value X, and updating “cnt”.

Each operation can be done in amortized $$O(\log L)$$ time, since in each operation, only constant number of nodes are inserted, though it is possible that a great number of nodes are deleted. Hence the total time complexity is $$O(n \log L)$$.

### Source Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

int l, c, n;
int cnt[100005];

typedef tree<int, pair<int, int>, less<int>, rb_tree_tag> rbtree;

#define tree shuorgsrh
rbtree tree;

void update(int l, int r, int c) {
rbtree mpart, rpart;

tree.split(l - 1, mpart);
int dif;
if (tree.size() &&
(dif = tree.rbegin()->first + tree.rbegin()->second.first - l) > 0) {
tree.rbegin()->second.first -= dif;
mpart.insert(make_pair(l, make_pair(dif, tree.rbegin()->second.second)));
}
mpart.split(r, rpart);

if (mpart.size() &&
(dif = mpart.rbegin()->first + mpart.rbegin()->second.first - r) > 0) {
mpart.rbegin()->second.first -= dif;
rpart.insert(make_pair(r, make_pair(dif, mpart.rbegin()->second.second)));
}
for (auto& p : mpart) {
cnt[p.second.second] -= p.second.first;
}
cnt[c] += r - l;
tree.insert(make_pair(l, make_pair(r - l, c)));
tree.join(rpart);
}

int main() {
scanf("%d%d%d", &l, &c, &n);
cnt[1] = l;
tree.insert(make_pair(0, make_pair(l, 1)));
rep (i, n) {
int p, x, a, b;
scanf("%d%d%d%d", &p, &x, &a, &b);
int m1 = (a + 1ll * cnt[p] * cnt[p]) % l;
int m2 = (a + 1ll * (cnt[p] + b) * (cnt[p] + b)) % l;
if (m1 > m2) swap(m1, m2);
m2++;
update(m1, m2, x);
}
cout << *max_element(cnt+1, cnt+c+1) << endl;
return 0;
}


# [2017-2018 ACM-ICPC Latin American Regional Programming Contest] A. Arranging tiles

### 代码

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

constexpr double EPS = 1e-8;

int fcmp(double x, double y = 0.0) {
if (fabs(x - y) < EPS) return 0;
return x < y ? -1 : 1;
}

typedef double T;
typedef struct pt {
T x, y;
T operator,(pt a) { return x * a.x + y * a.y; }  // inner product
T operator*(pt a) { return x * a.y - y * a.x; }  // outer product
pt operator+(pt a) { return {x + a.x, y + a.y}; }
pt operator-(pt a) { return {x - a.x, y - a.y}; }

pt operator*(T k) { return {x * k, y * k}; }
pt operator-() { return {-x, -y}; }
} vec;

typedef pair<pt, pt> seg;

int n;
int height;

struct polygon {
int width;
vector<pair<int, int>> lpart, rpart;

void init(vector<pair<int, int>>& pts) {
int minx = INT_MAX, maxx = INT_MIN;
for (auto& p : pts) {
height = max(height, p.second);
minx = min(minx, p.first);
maxx = max(maxx, p.first);
}
width = maxx - minx;
for (auto& p : pts) p.first -= minx;
int i = 1;
while (pts[i].second < height) rpart.push_back(pts[i++]);
rpart.push_back(pts[i++]);
while (i < pts.size()) lpart.push_back(pts[i++]);
lpart.push_back(pts[0]);
reverse(range(lpart));
}
} poly[16];

pt getMidPoint(pair<int, int> pt1, pair<int, int> pt2, double y) {
pt a { (double) pt1.first, (double) pt1.second },
b { (double) pt2.first, (double) pt2.second };
vec v = (b - a) * (1.0 / (b.y - a.y));
return a + v * (y - a.y);
}

double max_overlap(polygon& polyl, polygon& polyr) {
vector<pair<int, int>> &lpts = polyl.rpart, &rpts = polyr.lpart;
int ln = lpts.size(), rn = rpts.size(), yn;
vector<int> ys;
{
vector<int> yl(ln), yr(rn);
rep (i, ln) yl[i] = lpts[i].second;
rep (i, rn) yr[i] = rpts[i].second;
set_union(range(yl), range(yr), back_inserter(ys));
yn = ys.size();
}
int lptr = 0, rptr = 0;
double min_dif = 0.0;
rep (i, yn) {
pt lp = getMidPoint(lpts[lptr], lpts[lptr+1], ys[i]),
rp = getMidPoint(rpts[rptr], rpts[rptr+1], ys[i]);
min_dif = max(min_dif, lp.x - rp.x);
while (lptr < ln-1 && lpts[lptr+1].second <= ys[i]) lptr++;
while (rptr < rn-1 && rpts[rptr+1].second <= ys[i]) rptr++;
}
return polyl.width - min_dif;
}

double g[16][16];
double dp[1 << 14][16];

int main() {
scanf("%d", &n);
rep (i, n) {
int k; scanf("%d", &k);
vector<pair<int, int>> pts;
rep (j, k) {
int x, y; scanf("%d%d", &x, &y);
pts.emplace_back(x, y);
}
poly[i].init(pts);
}
rep (i, n) {
rep (j, n) {
if (i == j) continue;
g[i][j] = max_overlap(poly[i], poly[j]);
}
}
while (rem) {
unsigned bit = rem & -rem;
int i = __builtin_ctz(bit);
rep (j, n) {
if (j == i || ((1 << j) & mask) == 0) continue;
}
rem -= bit;
}
} else {
rep (j, n) dp[mask][j] = (j == i ? 0.0 : -1e15);
}
}
double ans = *max_element(range(dp[(1<<n)-1]));
double tot = 0.0;
rep (i, n) tot += poly[i].width;
printf("%.3f\n", tot - ans);
return 0;
}


# [2018 Multi-University Training Contest 10] C. Calculate

### Statement：

Given $$1 \leq A, B, C \leq 10^7$$, compute

$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \phi(\gcd(i, j^2, k^3))$

no more than 10 test cases.

### Solution：

Consider the number of triples (i, j, k) such that $$\gcd(i, j^2, k^3) = d$$, denoted as $$f(d)$$. By Mobius inversion,

$f(d) = \sum_{i} \mu(i) g(di)$

where $$g(d)$$ is the number of triples satisfying $$d | \gcd(i, j^2, k^3)$$, and the answer should be

$\sum_{d=1}^A f(d) \phi(d)$

Now we try to compute $$g(d)$$:

$g(d) = \sum_{i = 1}^A [d | i] \sum_{j = 1}^B [d | j^2] \sum_{k = 1}^C [d | k^3]$

Let $$d = \prod {p_i}^{a_i}$$ denote the unique factorization of d. Note that $$d | k^n$$ whenever $$\prod {p_i}^{\lceil a_i / n \rceil} | k$$.

Let $$h_n(d) = \prod {p_i}^{\lceil a_i / n \rceil}$$, which denotes the minimum positive integer whose nth power is divisible by d. Now $$g(d)$$ could be rewritten as

$g(d) = \lfloor \frac{A}{d} \rfloor \lfloor \frac{B}{h_2(d)} \rfloor \lfloor \frac{C}{h_3(d)} \rfloor$

$\sum_{d=1}^A f(d) \phi(d) = \sum_{d=1}^A \phi(d) \sum_{i} \mu(i) g(di) = \sum_{q = 1}^A g(q) \sum_{ij = q} \mu(i) \phi(j)$

where the Dirichlet convolution $$(\mu * \phi)(q) = \sum_{ij = q} \mu(i) \phi(j)$$ is multiplicative and thus could be effectively precomputed (along with $$h_2$$, $$h_3$$) by the sieve of Euler in linear time. Hence each test case could be done in $$O(A)$$ time.

### Source Code:

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

namespace sieve {
constexpr int MAXN = 10000007;
bool p[MAXN];
int prime[MAXN], sz;
int pval[MAXN], pcnt[MAXN];
unsigned h2[MAXN], h3[MAXN], phi[MAXN], muphi[MAXN];

void exec(int N = 10000007) {
p[0] = p[1] = 1;

pval[1] = 1;
pcnt[1] = 0;
h2[1] = h3[1] = phi[1] = muphi[1] = 1;

for (int i = 2; i < N; i++) {
if (!p[i]) {
prime[sz++] = i;
for (LL j = i; j < N; j *= i) {
int b = j / i;
pval[j] = i * pval[b];
pcnt[j] = pcnt[b] + 1;
h2[j] = h2[b] * (pcnt[j] % 2 == 1 ? i : 1);
h3[j] = h3[b] * (pcnt[j] % 3 == 1 ? i : 1);
phi[j] = (i == j ? i-1 : phi[b] * i);
muphi[j] = phi[j] - phi[b];
}
}
for (int j = 0; i * prime[j] < N; j++) {
int x = i * prime[j]; p[x] = 1;
if (i % prime[j] == 0) {
pval[x] = pval[i] * prime[j];
pcnt[x] = pcnt[i] + 1;
} else {
pval[x] = prime[j];
pcnt[x] = 1;
}
if (x != pval[x]) {
int b = x / pval[x];
h2[x] = h2[b] * h2[pval[x]];
h3[x] = h3[b] * h3[pval[x]];
muphi[x] = muphi[b] * muphi[pval[x]];
}
if (i % prime[j] == 0) break;
}
}
}
}

int main() {
using namespace sieve;
exec();
int T; scanf("%d", &T);
while (T--) {
unsigned a, b, c; scanf("%d%d%d", &a, &b, &c);
unsigned res = 0;
for (unsigned i = 1; i <= a; i++)
res += muphi[i] * (a / i) * (b / h2[i]) * (c / h3[i]);
printf("%d\n", res & 0x3fffffff);
}
return 0;
}


# 题解：

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
if (fabs(a - b) < EPS) return 0;
return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
vec v1 = s.first - p, v2 = s.second - p;
return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
int wn = 0;
for (int i = 0; i < n; i++){
if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
int d1 = fcmp(poly[i].imag() - p.imag()),
d2 = fcmp(poly[i+1].imag() - p.imag()),
k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
double x, y;
lhs >> x >> y;
rhs = {x, y};
return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
vector<pt> points;
rep (i, n)
if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
if (fcmp(vec1 * vec2) == 0) {
points.push_back(poly[i]);
points.push_back(poly[i+1]);
} else {
points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
}
}
sort(range(points), [] (pt a, pt b) {
return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
});
points.resize(unique(range(points), [] (pt a, pt b) {
return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
}) - points.begin());
double cur = 0.0;
assert(points.size() > 1);
for (int i = 1; i < points.size(); i++) {
if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
cur += abs(points[i] - points[i-1]);
} else {
cur = 0.0;
if (abs(points.back() - points[i]) <= ans) return;
}
ans = max(ans, cur);
}
}

int main() {
cin >> n; poly.resize(n);
rep (i, n) cin >> poly[i];
poly.push_back(poly[0]);
rep (i, n) {
rep (j, i) {
attempt(poly[i], poly[j]);
}
}
printf("%.8f\n", ans);
return 0;
}


# 2018牛客暑期ACM多校训练营（第一场）题解

### A. Monotonic Matrix

• $$a_{i,j} \in \{0, 1, 2\}$$
• 每一行从左到右和每一列从上到下单调不减

### F. Sum of Maximum

$\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}$